OKlibrary  0.2.1.6
general.hpp File Reference

On investigations into Gasarch problems (including Gasarch numbers) More...

Go to the source code of this file.


Detailed Description

On investigations into Gasarch problems (including Gasarch numbers)

Problems generated by output_gasarch_stdname(r,p,q).

Todo:
Basic notions
  • Let gasarch(r) by the smallest d such that gasarch_nbfclud(r,d,d) is unsatisfiable.
  • Since the problems are special bipartite Ramsey problems, we better introduce bipartite Ramsey problems in general, and then consider the Gasarch problems as finding a monochromatic 2x2-subgraph.
Todo:
Best local search algorithms
  • Evaluating
    E = run_ubcsat("Gasarch_4-17-17.cnf")
       
    by plot(E$alg,E$best) shows that adaptnovelty+ is clearly strongest (default values, that is, cutoff=10^5).
  • More thorough evaluation of satisfiable sub-instance Gasarch_4_17_17_39310.cnf (see below):
    > E = run_ubcsat("Gasarch_4_17_17_39310.cnf",runs=100,cutoff=1000000)
    > eval_ubcsat_dataframe(E)
    1. anovpp:
     5  6  7  8  9
     1  2 28 66  3
    fps: 309665
    2. anovp:
     6  7  8  9
     6 36 50  8
    fps: 312120
    3. dano:
     6  7  8  9 10
     3 38 49  9  1
    fps: 313067
    
    > E = run_ubcsat("Gasarch_4_17_17_39310.cnf",runs=100,cutoff=10000000, include_algs=list("anovpp","anovp","dano"))
    > eval_ubcsat_dataframe(E)
    1. dano:
     5  6  7  8
     1 31 66  2
    fps: 305142
    2. anovpp:
     6  7  8
    23 76  1
    fps: 308147
    3. anovp:
     6  7  8
    23 76  1
    fps: 307063
    
    > E = run_ubcsat("Gasarch_4_17_17_39310.cnf",runs=100,cutoff=100000000, include_algs=list("anovpp","anovp","dano"))
    1. anovp:
     5  6  7
    10 89  1
    fps: 309343
    2. dano:
     5  6  7
     9 90  1
    fps: 308107
    3. anovpp:
     5  6  7
     8 86  6
    fps: 310298
       
    So between anovp, dano, anovpp there appear not to exist substantial differences.
Todo:
Investigating the 16 x 16 case
  • Problem generation by output_gasarch_stdname(4,16,16).
  • With cutoff=10^5 a solution was found in run 8.
Todo:
Investigating the 16 x 17 case
  • Problem generation by output_gasarch_stdname(4,16,17).
  • cutoff=10^5:
    > ubcsat-okl -alg adaptnovelty+ -cutoff 100000 -runs 100 -i Gasarch_4-16-17.cnf -solve | tee Gasarch_4-16-17.cnf_OUT
    > E = read_ubcsat("Gasarch_4-16-17.cnf_OUT");
     4  5  6  7  8
     4 31 44 20  1
    100
    > summary(E$osteps)
       Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
       3534   14390   40630   41660   64290   98750
         
  • cutoff=10^6:
    > E = read_ubcsat("Gasarch_4-16-17.cnf_OUT2");
     4  5  6
    42 57  1
    100
    > summary(E$osteps)
       Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
       6984  116100  267100  324700  490500  998400
       
  • cutoff=10^7
    > ubcsat-okl -alg adaptnovelty+ -cutoff 10000000 -runs 100 -i Gasarch_4-16-17.cnf -solve | tee Gasarch_4-16-17.cnf_OUT3
    > E = read_ubcsat("Gasarch_4-16-17.cnf_OUT3");
     3  4
    22 78
    100
    > summary(E$osteps)
       Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
      73910  647600 1763000 2432000 3618000 9801000
    > ubcsat-okl -alg adaptnovelty+ -cutoff 10000000 -runs 2000 -i Gasarch_4-16-17.cnf -solve | tee Gasarch_4-16-17.cnf_OUT5
    Clauses = 67184
    Variables = 1088
    TotalLiterals = 265472
    FlipsPerSecond = 170466
    BestStep_Mean = 2394165.637000
    Steps_Mean = 10000000.000000
    Steps_Max = 10000000.000000
    PercentSuccess = 0.00
    BestSolution_Mean = 3.765000
    BestSolution_Median = 4.000000
    BestSolution_Min = 2.000000
    BestSolution_Max = 5.000000
    > E=read_ubcsat("Gasarch_4-16-17.cnf_OUT5")
       2    3    4    5
       4  467 1524    5
    2000
    > summary(E$osteps)
       Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
      26330  641300 1540000 2394000 3291000 9990000
    > E[E$min==2,]
         sat min  osteps msteps       seed
    529    0   2 9152422  1e+07 3103656038
    550    0   2 3109812  1e+07 2805697975
    1846   0   2 7230811  1e+07  356507595
    1987   0   2 2546463  1e+07 1382936908
       
    Running these four seeds with 4*10^9 steps still yields only min=2.
  • cutoff=10^8:
    >  ubcsat-okl -alg adaptnovelty+ -cutoff 100000000 -runs 100 -i Gasarch_4-16-17.cnf -solve | tee Gasarch_4-16-17.cnf_OUT4
    > E = read_ubcsat("Gasarch_4-16-17.cnf_OUT4");
     3  4
    39  4
    43
    > summary(E$osteps)
        Min.  1st Qu.   Median     Mean  3rd Qu.     Max.
       92170  8709000 23920000 31800000 50790000 93420000
       
  • With minisat2-preprocessing:
    1. cutoff=10^6 (adaptnovelty+):
       5  6  7  8  9 10
       3 14 38 28 12  5
      100
           
    2. cutoff=10^7
      > ubcsat-okl -alg adaptnovelty+ -cutoff 10000000 -runs 100 -i Gasarch_4-16-17-m2pp.cnf -solve | tee Gasarch_4-16-17-m2pp.cnf_OUT2
      Clauses = 66096
      Variables = 1088
      TotalLiterals = 393312
      FlipsPerSecond = 30907
      BestStep_Mean = 3805127.530000
      Steps_Mean = 10000000.000000
      Steps_Max = 10000000.000000
      PercentSuccess = 0.00
      BestSolution_Mean = 5.830000
      BestSolution_Median = 6.000000
      BestSolution_Min = 4.000000
      BestSolution_Max = 7.000000
      > E=read_ubcsat("Gasarch_4-16-17-m2pp.cnf_OUT2")
       4  5  6  7
       2 26 59 13
      100
           
      So here again it seems that the preprocessing doesn't help; and furthermore the flips-per-second seem to be drastically reduced compared to without preprocessing (the number of literal occurrences has just been increased by a factor of 393312/265472 = 1.481557).
    3. One needs to consider whether other algorithms might be better on this instance:
      > E = run_ubcsat("Gasarch_4-16-17-m2pp.cnf", cutoff=1000000,runs=100)
      plot(E$alg,E$best)
      > table(E$best[E$alg=="adaptnoveltyp"])
       5  6  7  8  9 10
       2 19 34 27 15  3
      > table(E$best[E$alg=="hwsat"])
       6  7  8  9 10
      16 26 34 23  1
           
      shows clearly that also here adaptnovelty+ is best, followed by hwsat.
  • Complete solvers:
    1. march_pl doesn't make progress at all.
    2. minisat2 and picosat apparently also don't make progress.
    3. Hard to say about satz215, but also nothing happens.
    4. OKsolver with or without minisat2-preprocessing doesn't complete a node at level 30 within a day:
      > OKsolver_2002-m2pp -M -D30 Gasarch_4-16-17.cnf
      s UNKNOWN
      c sat_status                            2
      c initial_maximal_clause_length         12
      c initial_number_of_variables           816
      c initial_number_of_clauses             66096
      c initial_number_of_literal_occurrences 393312
      c number_of_initial_unit-eliminations   0
      c reddiff_maximal_clause_length         0
      c reddiff_number_of_variables           0
      c reddiff_number_of_clauses             0
      c reddiff_number_of_literal_occurrences 0
      c number_of_2-clauses_after_reduction   816
      c running_time(sec)                     37419.5
      c number_of_nodes                       244589
      c number_of_single_nodes                24758
      c number_of_quasi_single_nodes          0
      c number_of_2-reductions                889054
      c number_of_pure_literals               0
      c number_of_autarkies                   0
      c number_of_missed_single_nodes         16367
      c max_tree_depth                        194
      c number_of_table_enlargements          0
      c number_of_1-autarkies                 0
      c number_of_new_2-clauses               0
      c maximal_number_of_added_2-clauses     0
      c file_name                             Gasarch_4-16-17.cnf_m2pp_8228
      > OKsolver_2002-O3-DNDEBUG -M -D30 Gasarch_4-16-17.cnf
      s UNKNOWN
      c sat_status                            2
      c initial_maximal_clause_length         4
      c initial_number_of_variables           1088
      c initial_number_of_clauses             67184
      c initial_number_of_literal_occurrences 265472
      c number_of_initial_unit-eliminations   0
      c reddiff_maximal_clause_length         0
      c reddiff_number_of_variables           0
      c reddiff_number_of_clauses             0
      c reddiff_number_of_literal_occurrences 0
      c number_of_2-clauses_after_reduction   1632
      c running_time(sec)                     10937.1
      c number_of_nodes                       700231
      c number_of_single_nodes                37899
      c number_of_quasi_single_nodes          0
      c number_of_2-reductions                5878849
      c number_of_pure_literals               0
      c number_of_autarkies                   302
      c number_of_missed_single_nodes         30075
      c max_tree_depth                        233
      c number_of_table_enlargements          0
      c number_of_1-autarkies                 147596107
      c number_of_new_2-clauses               0
      c maximal_number_of_added_2-clauses     0
      c file_name                             Gasarch_4-16-17.cnf
           
      Unclear whether preprocessing helps or not.
Todo:
Investigating the 17 x 17 case
  • This was shown to be 4-colorable in "Most Complex Four-Colored Rectangle-free Grids - Solution of an Open Multiple-Valued Problem" at ISMVL 2012 by Christian Posthoff and Bernd Steinbach (to appear).
  • A 4-coloring is available at http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17.txt
    S17 : [
    [2,2,1,3,3,4,2,1,4,1,3,2,2,3,4,4,3],
    [2,4,2,1,1,2,3,3,4,4,3,4,1,1,3,2,2],
    [3,1,3,4,4,4,1,1,1,4,3,2,4,1,2,3,2],
    [4,1,2,3,1,3,2,3,4,1,2,1,4,4,1,3,4],
    [3,1,1,1,2,3,2,4,2,3,4,4,4,3,2,2,1],
    [1,3,3,2,4,3,1,4,4,1,2,2,1,2,3,2,3],
    [3,1,4,2,4,2,2,3,3,2,1,4,1,4,4,1,3],
    [4,3,1,2,1,1,1,3,2,4,4,3,2,3,4,1,2],
    [4,4,3,3,4,2,4,2,3,1,2,3,2,1,2,1,1],
    [1,2,2,2,1,3,4,4,1,4,3,3,3,4,2,4,1],
    [4,2,3,4,3,2,1,3,2,3,1,4,3,2,1,4,1],
    [4,2,4,1,2,4,1,4,3,2,2,1,3,3,3,3,2],
    [1,3,2,1,2,4,4,1,3,3,3,4,2,2,1,1,4],
    [1,4,1,4,3,3,3,4,3,2,1,1,2,1,4,2,4],
    [2,4,1,2,2,4,3,2,1,3,4,3,1,4,1,3,3],
    [3,3,2,3,4,1,3,2,2,2,4,2,3,1,1,4,4],
    [2,3,4,4,3,1,4,1,4,2,4,1,1,2,2,3,1]
    ];
       
    with discussion at http://blog.computationalcomplexity.org/2012/02/17x17-problem-solved-also-18x18.html .
  • Corresponding partial assignment:
    phi17 : setify(standardise_gasarch(17,17)(create_list(4*(sqv(i,j)-1)+S17[i][j], i,1,17, j,1,17)));
    output_pa(phi17,"Solution_Gasarch_17x17.pa");
    
    # Checking the created CNF:
    > cat Gasarch_4-17-17.cnf | ApplyPass-O3-DNDEBUG Solution_Gasarch_17x17.pa | UnitClausePropagation-O3-DNDEBUG
    c UCP determines satisfiability after processing 867 assignments.
    p cnf 0 0
       
  • Problem generation by output_gasarch_stdname(4,17,17) (as "Gasarch_4-17-17.cnf").
  • adaptnovelty+ with cutoff=10^7:
    > ubcsat-okl -alg adaptnovelty+ -cutoff 10000000 -runs 100 -i Gasarch_4-17-17.cnf -solve
    Clauses = 76007
    Variables = 1156
    TotalLiterals = 300560
    FlipsPerSecond = 119833
    BestStep_Mean = 2985189.990000
    Steps_Mean = 10000000.000000
    Steps_Max = 10000000.000000
    PercentSuccess = 0.00
    BestSolution_Mean = 6.450000
    BestSolution_Median = 6.500000
    BestSolution_Min = 5.000000
    BestSolution_Max = 7.000000
       
  • cutoff=10^8:
    > E = read_ubcsat("Gasarch_4-17-17.cnf_OUT");
     5  6
     8 39
    47
    > summary(E$osteps)
        Min.  1st Qu.   Median     Mean  3rd Qu.     Max.
       40950  6445000 13800000 17590000 21600000 66880000
       
    Looks as if 5 would be the global minimum.
  • OKsolver_2002 looks hopeless:
    > OKsolver_2002-O3-DNDEBUG -M -D30 Gasarch_4-17-17.cnf
    s UNKNOWN
    c sat_status                            2
    c initial_maximal_clause_length         4
    c initial_number_of_variables           1156
    c initial_number_of_clauses             76007
    c initial_number_of_literal_occurrences 300560
    c number_of_initial_unit-eliminations   0
    c reddiff_maximal_clause_length         0
    c reddiff_number_of_variables           0
    c reddiff_number_of_clauses             0
    c reddiff_number_of_literal_occurrences 0
    c number_of_2-clauses_after_reduction   1734
    c running_time(sec)                     286.8
    c number_of_nodes                       2184
    c number_of_single_nodes                79
    c number_of_quasi_single_nodes          0
    c number_of_2-reductions                7789
    c number_of_pure_literals               0
    c number_of_autarkies                   16
    c number_of_missed_single_nodes         124
    c max_tree_depth                        243
    c number_of_table_enlargements          0
    c number_of_1-autarkies                 668409
    c number_of_new_2-clauses               0
    c maximal_number_of_added_2-clauses     0
    c file_name                             Gasarch_4-17-17.cnf
       
    without reaching a monitoring node.
  • Also with m2pp-preprocessing it looks hopeless:
    s UNKNOWN
    c sat_status                            2
    c initial_maximal_clause_length         12
    c initial_number_of_variables           867
    c initial_number_of_clauses             74851
    c initial_number_of_literal_occurrences 445638
    c number_of_initial_unit-eliminations   0
    c reddiff_maximal_clause_length         0
    c reddiff_number_of_variables           0
    c reddiff_number_of_clauses             0
    c reddiff_number_of_literal_occurrences 0
    c number_of_2-clauses_after_reduction   867
    c running_time(sec)                     283.9
    c number_of_nodes                       596
    c number_of_single_nodes                47
    c number_of_quasi_single_nodes          0
    c number_of_2-reductions                2397
    c number_of_pure_literals               0
    c number_of_autarkies                   0
    c number_of_missed_single_nodes         10
    c max_tree_depth                        177
    c number_of_table_enlargements          0
    c number_of_1-autarkies                 0
    c number_of_new_2-clauses               0
    c maximal_number_of_added_2-clauses     0
    c file_name                             Gasarch_4-17-17.cnf_m2pp_22254
       
  • minisat2 also looks hopeless, and aborted after 25 restarts (average length of clauses learned around 140).
  • SplittingViaOKsolver:
    1. D=20:
      > SplittingViaOKsolver -D20 Gasarch_4-17-17.cnf
      > cat Md5sum
      43170ff1da700a279752e92676e850c4
      > cat Statistics
      > E=read.table("Data")
      > summary(E$n)
         Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
        20.00   20.00   20.00   20.04   20.00   21.00
      > table(E$n)
       20  21
      988  36
      > summary(E$d)
         Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
         5.00   10.00   11.00   11.25   13.00   15.00
      > table(E$d)
        5   6   7   8   9  10  11  12  13  14  15
        1   5  20  50 105 161 210 200 160  80  32
      > cat Result
      c initial_maximal_clause_length         4
      c initial_number_of_variables           1156
      c initial_number_of_clauses             76007
      c initial_number_of_literal_occurrences 300560
      c number_of_initial_unit-eliminations   0
      c reddiff_maximal_clause_length         0
      c reddiff_number_of_variables           0
      c reddiff_number_of_clauses             0
      c reddiff_number_of_literal_occurrences 0
      c number_of_2-clauses_after_reduction   1734
      c running_time(sec)                     230.5
      c number_of_nodes                       2047
      c number_of_quasi_single_nodes          0
      c number_of_2-reductions                0
      c number_of_pure_literals               0
      c number_of_autarkies                   0
      c max_tree_depth                        15
      c proportion_searched                   0.000000e+00
      c proportion_single                     0.000000e+00
      c total_proportion                      0
      c number_of_table_enlargements          0
      c number_of_1-autarkies                 2329087
      c file_name                             Gasarch_4-17-17.cnf
      c splitting_cases                       1024
      
      > SplittingViaOKsolver -D30 Gasarch_4-17-17.cnf
      > cat Md5sum
      94da248dd6e7706144efaa752bb6e684
      > cat Statistics
      > E=read.table("Data")
      > summary(E$n)
         Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
        30.00   30.00   32.00   31.37   32.00   34.00
      > table(E$n)
         30    32    33    34
      16120 29376  2144    48
      > summary(E$d)
         Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
         8.00   16.00   17.00   17.39   19.00   23.00
      > table(E$d)
         8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23
         1    9   50  192  574 1406 2803 4671 6602 7906 7960 6842 4760 2632 1024  256
      > cat Result
      c running_time(sec)                     10632.3
      c number_of_nodes                       95375
      c number_of_quasi_single_nodes          0
      c number_of_2-reductions                0
      c number_of_pure_literals               0
      c number_of_autarkies                   0
      c max_tree_depth                        23
      c proportion_searched                   0.000000e+00
      c proportion_single                     0.000000e+00
      c total_proportion                      0
      c number_of_table_enlargements          0
      c number_of_1-autarkies                 107432983
      c splitting_cases                       47688
      
      > solver="minisat-2.2.0 -cpu-lim=20" ProcessSplitViaOKsolver SplitViaOKsolver_D30Gasarch_41717cnf_2012-02-10-212452
      # csltok, aborted:
      > E=read_processsplit_minisat()
      4225: 23.238h, sum-cfs=1.753738e+09, mean-t=19.800s, mean-cfs=415086
      $t:
         Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
        19.59   19.79   19.80   19.80   19.82   19.90
      sd= 0.0249258
         95%    96%    97%    98%    99%   100%
      19.831 19.833 19.835 19.838 19.847 19.896
      sum= 83656.92
      $cfs:
         Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
       189900  397200  417900  415100  432400  501400
      sd= 23391.93
           95%      96%      97%      98%      99%     100%
      448530.4 450512.0 453157.8 456775.6 465139.9 501414.0
      sum= 1753737822
      $t ~ $cfs:
                     Estimate  Std. Error   t value  Pr(>|t|)
      (Intercept)  1.9822e+01  6.8087e-03 2911.3501 < 2.2e-16 ***
      E$cfs       -5.2934e-08  1.6377e-08   -3.2322  0.001238 **
      R-squared: 0.002468
      > range(E$sat)
      [1] 2 2
      
      > for x in Instances/*; do PassClashes-O3-DNDEBUG Solution_Gasarch_17x17.pa ${x}; if [[ $? != 0 ]]; then echo ${x}; fi; done
      Instances/39310
      > cat Gasarch_4-17-17.cnf | ApplyPass-O3-DNDEBUG Instances/39310 > Gasarch_4_17_17_39310.cnf
      > cat Gasarch_4_17_17_39310.cnf | ExtendedDimacsFullStatistics-O3-DNDEBUG
           pn      pc      n    nmi       c        l     n0   n0mi      c0       l0  cmts
         1156   76007   1126   1156   70615   277699     NA     NA   70615   277699  1159
       length   count
            2    1719
            3    1323
            4   67573
      > ManipParam-O3-DNDEBUG Gasarch_4_17_17_39310.cnf "1156" "70615"
      
      > ubcsat-okl -alg adaptnovelty+ -cutoff 10000000 -runs 100 -i Gasarch_4_17_17_39310.cnf
      Clauses = 70615
      Variables = 1156
      TotalLiterals = 277699
      FlipsPerSecond = 352116
      BestStep_Mean = 3357811.22
      Steps_Mean = 10000000
      Steps_Max = 10000000
      PercentSuccess = 0.00
      BestSolution_Mean = 6.75
      BestSolution_Median = 7
      BestSolution_Min = 6
      BestSolution_Max = 7
      > ubcsat-okl -alg adaptnovelty+ -cutoff 100000000 -runs 100 -i Gasarch_4_17_17_39310.cnf
      Clauses = 70615
      Variables = 1156
      TotalLiterals = 277699
      FlipsPerSecond = 360058
      BestStep_Mean = 29853791.68
      Steps_Mean = 100000000
      Steps_Max = 100000000
      PercentSuccess = 0.00
      BestSolution_Mean = 5.97
      BestSolution_Median = 6
      BestSolution_Min = 5
      BestSolution_Max = 7
           
      Looks as if SplittingViaOKsolver doesn't make a big difference.
  • The "direct encoding" seems useless, and the other encodings must be tried out. See "Implement other translations" in Satisfiability/Lisp/Generators/RamseyTheory/plans/GasarchProblems.hpp.
Todo:
Investigating the 18 x 18 case
Todo:
Investigating the transversals
  • The full transversal hypergraph:
    fGh(d) := block([G : gasarch_hg(d,d), T],
     T : transversal_hg_rs(G),
     print(d, statistics_fcs(G), statistics_fcs(T),  ncl_list_fcs(T)),
     T
    )$
    
    fGh(1)$
    1 [1,0,0,-1,inf] [1,1,0,0,0] [[0,1]]
    
    fGh(2)$
    2 [4,1,4,4,4] [4,4,4,1,1] [[1,4]]
    
    
    fGh(3)$
    3 [9,9,36,4,4] [9,51,198,4,3] [[3,6],[4,45]]
    
    fGh(4)$
    4 [16,36,144,4,4] [16,1240,10320,9,7] [[7,96],[8,648],[9,496]]
       
  • Now just the sizes and the numbers of minimum hyperedges; first at Maxima/Lisp level, then at C++ level. The generator here needs to be written so that only one vertex is added at a time.
    gasarch_sqatomic_ohg(n) := block([d : ceiling(n^(1/2)), G, V, VS, E],
     G : gasarch_ohg(d,d),
     V : take_elements(n,G[1]),
     VS : setify(V),
     E : sublist(G[2], lambda([H], subsetp(H, VS))),
     [V,E])$
    gasarch_sqatomic_hg(n) := ohg2hg(gasarch_sqatomic_ohg(n))$
    
    oklib_monitor : true$
    Gh_36 : minimum_transversals_mongen(36,gasarch_sqatomic_hg,[{}])$
       1 0 1
    2 0 1
    3 0 1
       4 1 4
    5 1 4
    6 2 12
    7 2 12
    8 2 2
       9 3 6
    10 3 6
    11 4 30
    12 5 72
    13 5 72
    14 5 12
    15 6 42
       16 7 96
    17 7 96
    18 8 504
    19 9 1320
    20 10 2640
    21 10 2640
    22 10 480
    23 11 1728
    24 12 4056
       25 13 7800
    26 13 7800
    27 13 720
    28 14 2520
    29 15 5760
    30 16 10800
    31 16 10800
    32 16 1440
    33 17 6480
    34 18 17280
    35 19 36000
    36 20 64800
    
    gasarch_sqatomic_stdohg(n) := block([d : ceiling(n^(1/2)), G, V, VS, E],
     G : gasarch_stdohg(d,d),
     V : take_elements(n,G[1]),
     VS : setify(V),
     E : sublist(G[2], lambda([H], subsetp(H, VS))),
     [V,E])$
    gasarch_sqatomic_stdhg(n) := ohg2hg(gasarch_sqatomic_stdohg(n))$
    
    oklib_monitor : true$
    Gh_64 : minimum_transversals_mongen(64,gasarch_sqatomic_stdhg,[{}])$
    1 0 1
    2 0 1
    3 0 1
        4 1 4
    5 1 3
    6 2 11
    7 2 11
    8 2 2
        9 3 6
    10 3 1
    11 4 23
    12 5 65
    13 5 65
    14 5 12
    15 6 42
        16 7 96
    17 7 3
    18 8 399
    19 9 1179
    20 10 2499
    21 10 2499
    22 10 480
    23 11 1728
    24 12 4056
        25 13 7800
    26 13 20
       
    so d in [1,2,3,4,5,6] -> tau(d) = 0, 1, 3, 7, 13, 20 yielding densities 0, 0.25, 0.33, 0.4375, 0.52, 0.5{period}, where the numbers of minimum transversals are 1, 4, 6, 96, 7800, 64800, with 4=2^2, 6=2 * 3, 96=2^5 * 3, 7800=2^3 * 3 * 5^2 * 13, 64800=2^6 * 3^4 * 5^3.

Definition in file general.hpp.