OKlibrary  0.2.1.6
Datak4.hpp File Reference

Investigating the transversal hypergraph of Green-Tao hypergraphs for k = 4 (length of arithmetic progressions) More...

Go to the source code of this file.

## Detailed Description

Investigating the transversal hypergraph of Green-Tao hypergraphs for k = 4 (length of arithmetic progressions)

Todo:
Elementary statistics
• Investigating tr_arithprog_hg(4,n).
• Staticstics:
```block([G0 : [{},{}]],
for n: 1 thru 30 do block([G : arithprog_primes_hg(4,n), T],
if G[2]=G0[2] then print(n)
else {
T : transversal_hg_rs(G), G0 : G,
print(n, statistics_fcs(G), statistics_fcs(T), ncl_list_fcs(T))
}))\$
1
2
3
4
5
6
7
8
9 [9,1,4,4,4] [9,4,4,1,1] [[1,4]]
10 [10,2,8,4,4] [10,4,5,2,1] [[1,3],[2,1]]
11
12
13 [13,3,12,4,4] [13,8,15,2,1] [[1,1],[2,7]]
14 [14,4,16,4,4] [14,32,92,3,2] [[2,4],[3,28]]
15
16 [16,5,20,4,4] [16,32,100,4,2] [[2,4],[3,20],[4,8]]
17 [17,7,28,4,4] [17,72,272,4,3] [[3,16],[4,56]]
18
19
20
21
22 [22,8,32,4,4] [22,288,1376,5,4] [[4,64],[5,224]]
23 [23,9,36,4,4] [23,592,3232,6,4] [[4,16],[5,288],[6,288]]
24
25 [25,11,44,4,4] [25,1036,6581,7,4] [[4,3],[5,79],[6,504],[7,450]]
26 [26,12,48,4,4] [26,1512,10226,8,5] [[5,48],[6,487],[7,752],[8,225]]
27 [27,13,52,4,4] [27,3078,23145,9,5] [[5,16],[6,317],[7,1139],[8,1264],[9,342]]
```
• The numbers of minimum hyperedges:
```L4 : [];
minimum_transversals_decomp_gen(inf,lambda([n],arithprog_primes_hg(4,n)), 'L4)\$

1 1 0 [0,1,1]
9 9 1 [1,4,6]
10 10 2 [1,3,6]
13 13 3 [1,1,8]
14 14 4 [2,4,6]
16 16 5 [2,4,7]
17 17 7 [3,16,6]
22 22 8 [4,64,8]
23 23 9 [4,16,7]
25 25 11 [4,3,6]
26 26 12 [5,48,6]
27 27 13 [5,16,5]
28 28 14 [5,4,4]
30 30 15 [5,1,5]
31 31 16 [5,1,5]
32 32 19 [6,6,5]
34 34 20 [6,6,6]
35 35 21 [7,116,6]
36 36 22 [8,464,6]
37 37 24 [9,3248,5]
38 38 25 [9,1044,5]
39 39 27 [9,171,5]
40 40 28 [9,153,5]
42 42 29 [9,85,6]
43 43 31 [9,15,5]
44 44 32 [9,12,5]
45 45 34 [10,132,5]
46 46 35 [11,1254,5]
48 48 38 [11,33,6]
49 49 41 [11,12,5]
50 50 42 [11,12,5]
51 51 44 [12,87,5]
52 52 45 [12,62,5]
53 53 46 [12,62,4]
54 54 47 [12,52,4]
55 55 50 [12,1,4]
56 56 51 [13,35,4]
57 57 52 [13,6,4]
58 58 53 [14,78,4]
60 60 55 [14,13,5]
61 61 59 [15,60,5]
62 62 62 [16,2280,5]
63 63 63 [16,912,5]
64 64 64 [16,840,5]
65 65 65 [16,315,5]
66 66 67 [16,252,5]
67 67 69 [16,224,5]
69 69 71 [16,152,6]
70 70 72 [16,38,5]
71 71 76 [17,58,5]
```
• Using the incremental approach as in minimum_transversals_mongen, and implementing it in C++, should be much faster.
• At C++ level:
```> MinimumTransversals_GreenTao-O3-DNDEBUG 100 4
56 13 35
57 13 6
58 14 78
59 14 78
60 14 13
61 15 60
62 16 2280
63 16 912
64 16 840
65 16 315
66 16 252
67 16 224
68 16 224
69 16 152
70 16 38
71 17 58
72 18 416
73 19 416
74 19 416
75 19 416
76 19 104
77 19 2
78 20 55
```
So we are not far off what minisat2 can compute (see below).
Todo:
Only computing the transversal numbers
• Just computing the transversal numbers, using minisat2 and the direct translation (as provided by "GTTransversalsInc 4 1 0 OutputFile"):
```k n tau
4 1 0
4 2 0
4 3 0
4 4 0
4 5 0
4 6 0
4 7 0
4 8 0
4 9 1
4 10 1
4 11 1
4 12 1
4 13 1
4 14 2
4 15 2
4 16 2
4 17 3
4 18 3
4 19 3
4 20 3
4 21 3
4 22 4
4 23 4
4 24 4
4 25 4
4 26 5
4 27 5
4 28 5
4 29 5
4 30 5
4 31 5
4 32 6
4 33 6
4 34 6
4 35 7
4 36 8
4 37 9
4 38 9
4 39 9
4 40 9
4 41 9
4 42 9
4 43 9
4 44 9
4 45 10
4 46 11
4 47 11
4 48 11
4 49 11
4 50 11
4 51 12
4 52 12
4 53 12
4 54 12
4 55 12
4 56 13
4 57 13
4 58 14
4 59 14
4 60 14
4 61 15
4 62 16
4 63 16
4 64 16
4 65 16
4 66 16
4 67 16
4 68 16
4 69 16
4 70 16
4 71 17
4 72 18
4 73 19
4 74 19
4 75 19
4 76 19
4 77 19
4 78 20
4 79 21
4 80 21
4 81 21
4 82 21
4 83 22
```

Definition in file Datak4.hpp.