Description

Mean Ramsey-Turán numbers Raphael Yuster Department of Mathematics University of Haifa at Oranim Tivon 36006, Israel Abstract A ρ-mean coloring of a graph is a coloring of the edges such that the average

Information

Category:
## Entertainment

Publish on:

Views: 120 | Pages: 9

Extension: PDF | Download: 0

Share

Transcript

Mean Ramsey-Turán numbers Raphael Yuster Department of Mathematics University of Haifa at Oranim Tivon 36006, Israel Abstract A ρ-mean coloring of a graph is a coloring of the edges such that the average number of colors incident with each vertex is at most ρ. For a graph H and for ρ 1, the mean Ramsey- Turán number RT (n, H, ρ mean) is the maximum number of edges a ρ-mean colored graph with n vertices can have under the condition it does not have a monochromatic copy of H. It is conjectured that RT (n, K m, mean) = RT (n, K m, ) where RT (n, H, k) is the maximum number of edges a k edge-colored graph with n vertices can have under the condition it does not have a monochromatic copy of H. We prove the conjecture holds for K 3. We also prove that RT (n, H, ρ mean) RT (n, K χ(h), ρ mean) + o(n ). This result is tight for graphs H whose clique number equals their chromatic number. In particular we get that if H is a 3-chromatic graph having a triangle then RT (n, H, mean) = RT (n, K 3, mean) + o(n ) = RT (n, K 3, ) + o(n ) = 0.4n (1 + o(1)). 1 Introduction All graphs considered are finite, undirected and simple. For standard graph-theoretic terminology see [1]. Ramsey and Turán type problems are central problems in extremal graph theory. These two topics intersect in Ramsey-Turán Theory which is now a wide field of research with many interesting results and open problems. The survey of Simonovits and Sós [11] is an excellent reference for Ramsey-Turán Theory. The Ramsey number R(H, k) is the minimum integer n such that in any k-coloring of the edges of K n there is a monochromatic H. An edge coloring is called k-local if every vertex is incident with at most k colors. The local Ramsey number R(H, k loc) is the minimum integer n such that in any k-local coloring of the edges of K n there is a monochromatic H. An edge coloring is called ρ-mean if the average number of colors incident with each every vertex is at most ρ. The mean Ramsey number R(H, ρ mean) is the minimum integer n such that in any ρ-mean coloring of the edges of K n World Wide Web: raphy 1 there is a monochromatic H. Clearly, R(H, k) R(H, k loc) R(H, k mean). The relationship between these three parameters has been studied by various researchers. See, e.g., [, 4, 7, 10]. In particular, Gyárfás et. al. [7] proved that R(K m, ) = R(K m, loc). Caro and Tuza proved that R(K m, loc) = R(K m, mean) and Schelp [10] proved that R(K m, k loc) = R(K m, k mean). The Ramsey-Turán number RT (n, H, k) is the maximum number of edges a k-colored graph with n vertices can have under the condition it does not have a monochromatic copy of H. We analogously define the local and mean Ramsey-Turán numbers, denoted RT (n, H, k loc) and RT (n, H, ρ mean) respectively, to be the maximum number of edges a k-local (resp. ρ-mean) colored graph with n vertices can have under the condition it does not have a monochromatic copy of H. Clearly, RT (n, H, k) RT (n, H, k loc) RT (n, H, k mean). The relationship between RT (n, H, k), Ramsey numbers and Turán numbers is well-known. The Turán graph T (n, k) is the complete k-partite graph with n vertices whose vertex classes are as equal as possible. Let t(n, k) be the number of edges of T (n, k). Burr, Erdős and Lovász [3] introduced the Ramsey function r(h, k) which is the smallest integer r for which there exists a complete r-partite graph having the property that any k edge-coloring of it has a monochromatic H. For example, r(k m, k) = R(K m, k) and r(c 5, ) = 5. Clearly, RT (n, K m, k) = t(n, R(K m, k) 1). As shown in Theorem 13 in [11], it follows from the Erdős-Stone Theorem [6] that ( ) ( ) 1 n RT (n, H, k) = 1 + o(n ). r(h, k) 1 Clearly, a similar relationship holds between RT (n, H, k loc) and the analogous Ramsey function r(h, k loc). However, no such relationship is known for RT (n, H, k mean). We conjecture that such a relationship holds. Conjecture 1.1 RT (n, H, k mean) = ( 1 1 r(h, k mean) 1 ) ( ) n + o(n ). Combining this with the fact that R(K m, ) = R(K m, loc) = R(K m, mean) we have the following stronger conjecture for complete graphs and k =. Conjecture 1. RT (n, K m, mean) = RT (n, K m, ) = t(n, R(K m, ) 1). For non-integral values of ρ is is not even clear what the right conjecture for RT (n, H, ρ mean) should be. The first result of this paper shows that Conjecture 1. holds for K 3. Theorem 1.3 RT (n, K 3, mean) = RT (n, K 3, ) = t(n, R(K 3, ) 1) = t(n, 5) = 0.4n. The second result of this paper asserts that RT (n, H, ρ mean) is bounded by a function of the chromatic number of H. In fact, for graphs whose clique number equals their chromatic number, RT (n, H, ρ mean) is essentially determined by the chromatic number of H. Theorem 1.4 For all ρ 1 and for all graphs H, RT (n, H, ρ mean) RT (n, K χ(h), ρ mean)+ o(n ). In particular, if the chromatic number of H equals its clique number then RT (n, H, ρ mean) = RT (n, K χ(h), ρ mean) + o(n ). The proof of Theorem 1.4 uses a colored version of Szemerédi s Regularity Lemma together with several additional ideas. Notice that the trivial case ρ = 1 in Theorem 1.4 is equivalent to the Erdős-Stone Theorem. Combining Theorem 1.3 with Theorem 1.4 we obtain: Corollary 1.5 Let H be a 3-chromatic graph. Then, RT (n, H, mean) 0.4n (1 + o(1)). If H contains a triangle then RT (n, H, mean) = 0.4n (1 + o(1)). The next section contains the proof of Theorem 1.3. Section 3 contains the proof of Theorem 1.4. Proof of Theorem 1.3 We need to prove that RT (n, K 3, mean) = t(n, 5). Since K 5 has a -coloring with no monochromatic triangle, so does T (n, 5). Hence, RT (n, K 3, mean) t(n, 5). We will show that RT (n, K 3, mean) t(n, 5). Clearly, the result is trivially true for n 6, so we assume n 6. Our proof proceeds by induction on n. Let G have n 6 vertices and more than t(n, 5) edges. Clearly we may assume that G has precisely t(n, 5) + 1 edges. Consider any given -mean coloring of G. If n = 6 then G = K 6. Recall from the introduction that R(K 3, mean) = R(K 3, ) = 6. As a -mean coloring of K 6 contains a monochromatic triangle this base case of the induction holds. If n = 7 then G is K7. Again, it is trivial to check that any -mean coloring of K 7 contains a monochromatic triangle. Similarly, if n = 8 then G is a K 8 missing two edges and it is straightforward to verify that any -mean coloring of such a G contains a monochromatic triangle. Assume the theorem holds for all 6 n n and n 9. For a vertex v, let c(v) denote the number of colors incident with v and let d(v) denote the degree of v. If some v has c(v) and d(v) 4n/5 then G v is also -mean colored and has more than t(n 1, 5) edges. Hence, by the induction hypothesis, G v has a monochromatic triangle. Otherwise, if some v has c(v) = 1 and d(v) 3n/5 then let w be a vertex with maximum c(w). Then, G {v, w} is also -mean colored and has more than t(n, 5) edges. Hence, by the induction hypothesis, G {v, w} has a monochromatic triangle. Otherwise, if v is an isolated vertex of G then let u and w be two distinct vertices having maximum c(u) + c(w). Then, G {v, u, w} is -mean colored and has more than t(n 3, 5) edges. Hence, by the induction hypothesis, G {v, u, w} has a monochromatic triangle. 3 We are left with the case where δ(g) 3n/5 and whenever c(v) then also d(v) 4n/5. Let v be with c(v) = 1 (if no such v exists then the graph is -local colored and hence contains a monochromatic triangle as, trivially, RT (n, K 3, loc) = t(n, 5)). We may assume that 3n/5 d(v) 4n/5, since otherwise we would have δ(g) 4n/5 which is impossible for a graph with t(n, 5) + 1 edges. Consider the neighborhood of v, denoted N(v). Clearly, if w N(v) then c(w) 1 otherwise (because d(w) 3n/5) there must be some w N(v) for which (v, w, w ) is a monochromatic triangle and we are done. Thus, the minimum degree of G[N(v)] is greater than d(v) n/5. Since d(v) 3n/5 it follows that G[N(v)] has minimum degree greater than N(v) /3. If N(v) is divisible by 3 then the theorem of Corrádi and Hajnal [5] implies that G[N(v)] has a triangle factor. If N(v) 1 is divisible by 3 then the theorem of Hajnal and Szemerédi [8] implies that G[N(v)] has a factor into ( N(v) 4)/3 triangles and one K 4. If N(v) is divisible by 3 then, similarly, G[N(v)] has a factor into ( N(v) 8)/3 triangles and two K 4 or ( N(v) 5)/3 triangles and one K 5. Assume that G has no monochromatic triangle. The sum of colors incident with the vertices of any non-monochromatic triangle is at least 5 = 3 (5/3). The sum of colors incident with the vertices of any K 4 having no monochromatic triangle is at least 8 4 (5/3). The sum of colors incident with the vertices of any K 5 having no monochromatic triangle is at least 10 5 (5/3). Thus, a contradiction. n v V c(v) n d(v) n n = n 3 Proof of Theorem 1.4 Before we prove Theorem 1.4 we need several to establish several lemmas. Lemma 3.1 For every ɛ 0 there exists α = α(ɛ) 0 such that for all m sufficiently large, if a graph has m vertices and more than RT (m, K s, ρ mean) + ɛm /4 edges and is (ρ + α)-mean colored, then it has a monochromatic K s. Proof: Pick α such that ɛm /4 (αm+1)(m 1) for all sufficiently large m. Given a graph G with m vertices and more than RT (m, K s, ρ mean) + ɛm /4 edges, consider a (ρ + α)-mean coloring of G. By picking αm non-isolated vertices of G and deleting all edges incident with them we obtain a spanning subgraph of G with m vertices, more than RT (m, K s, ρ mean)+ɛm /4 (αn+1)(n 1) RT (m, K s, ρ mean) edges, and which is ρ-mean colored. By definition, it has a monochromatic K s. Lemma 3. If n is a multiple of m then RT (n, K s, ρ mean) RT (m, K s, ρ mean)n /m. 4 Proof: Let G be a graph with m vertices and RT (m, K s, ρ mean) edges having a ρ-mean coloring without a monochromatic K s. Let G be obtained from G by replacing each vertex v with an independent set X v of size n/m. For u v, we connect a vertex from X u with a vertex from X v if and only if uv is an edge of G, and we color this edge with the same color of uv. Clearly, G has RT (m, K s, ρ mean)n /m edges, the corresponding coloring is also ρ-mean, and there is no monochromatic K s in G. As G has n vertices we have that RT (n, K s, ρ mean) RT (m, K s, ρ mean)n /m. As mentioned in the introduction, our main tool in proving Theorem 1.4 is a colored version of Szemerédi s Regularity Lemma. We now give the necessary definitions and the statement of the lemma. Let G = (V, E) be a graph, and let A and B be two disjoint subsets of V. If A and B are non-empty, let e(a, B) denote the number of edges with one endpoint in A and another endpoint in B and define the density of edges between A and B by d(a, B) = e(a, B) A B. For γ 0 the pair (A, B) is called γ-regular if for every X A and Y B satisfying X γ A and Y γ B we have d(x, Y ) d(a, B) γ. An equitable partition of a set V is a partition of V into pairwise disjoint classes V 1,..., V m of almost equal size, i.e., V i V j 1 for all i, j. An equitable partition of the set of vertices V of G into the classes V 1,..., V m is called γ-regular if V i γ V for every i and all but at most γ ( ) m of the pairs (V i, V j ) are γ-regular. Szemerédi [1] proved the following. Lemma 3.3 For every γ 0, there is an integer M(γ) 0 such that for every graph G of order n M there is a γ-regular partition of the vertex set of G into m classes, for some 1/γ m M. To prove Theorem 1.4 we will need a colored version of the Regularity Lemma. straightforward modification of the proof of the original result (see, e.g., [9] for details). Its proof is a Lemma 3.4 For every γ 0 and integer r, there exists an M(γ, r) such that if the edges of a graph G of order n M are r-colored E(G) = E 1 E r, then there is a partition of the vertex set V (G) = V 1 V m, with 1/γ m M, which is γ-regular simultaneously with respect to all graphs G i = (V, E i ) for 1 i r. A useful notion associated with a γ-regular partition is that of a cluster graph. Suppose that G is a graph with a γ-regular partition V = V 1 V m, and η 0 is some fixed constant (to be thought of as small, but much larger than γ.) The cluster graph C(η) is defined on the vertex 5 set {1,..., m} by declaring ij to be an edge if (V i, V j ) is a γ-regular pair with edge density at least η. From the definition, one might expect that if a cluster graph contains a copy of a fixed clique then so does the original graph. This is indeed the case, as established in the following well-known lemma (see [9]), which says more generally that if the cluster graph contains a K s then, for any fixed t, the original graph contains the Turán graph T (st, s). Lemma 3.5 For every η 0 and positive integers s, t there exist a positive γ = γ(η, s, t) and a positive integer n 0 = n 0 (η, s, t) with the following property. Suppose that G is a graph of order n n 0 with a γ-regular partition V = V 1 V m. Let C(η) be the cluster graph of the partition. If C(η) contains a K s then G contains a T (st, s). Proof of Theorem 1.4: Fix an s-chromatic graph H and fix a real ρ 1. We may assume s 3 as the theorem is trivially true (and meaningless) for bipartite graphs. Let ɛ 0. We prove that there exists N = N(H, ρ, ɛ) such that for all n N, if G is a graph with n vertices and more than RT (n, K s, ρ mean) + ɛn edges then any ρ-mean coloring of G contains a monochromatic copy of H. We shall use the following parameters. Let t be the smallest integer for which T (st, s) contains H. Let r = 18ρ /ɛ. In the proof we shall choose η to be sufficiently small as a function of ɛ alone. Let α = α(ɛ) be as in lemma 3.1. Let γ be chosen such that (i) γ η/r, (ii) ρ/(1 γr) ρ + α, (iii) 1/γ is larger than the minimal m for which Lemma 3.1 holds. (iv) γ γ(η, s, t) where γ(η, s, t) is the function from Lemma 3.5. In the proof we shall assume, whenever necessary, that n is sufficiently large w.r.t. all of these constants, and hence N = N(H, ρ, ɛ) exists. In particular, N n 0 (η, s, t) where n 0 (η, s, t) is the function from Lemma 3.5 and also N M(γ, r) where M(γ, r) is the function from Lemma 3.4. Let G = (V, E) be a graph with n vertices and with E RT (n, K s, ρ mean) + ɛn. Notice that since s 3 and since RT (n, K s, ρ mean) RT (n, K 3, 1) = t(n, ) = n /4 we have that n / E n /4. Fix a ρ-mean coloring of G. Assume the colors are {1,..., q} for some q and let c i denote the number of edges colored with i. Without loss of generality we assume that c i c i+1. We first show that the first r colors already satisfy c 1 + c + + c r E ɛn /. Indeed, assume otherwise. Since, trivially, c r+1 E /r, let us partition the colors {r + 1,..., q} into parts such that for each part (except, perhaps, the last part) the total number of edges colored with a color belonging to the part is between E /r and E /r. The number of edges colored by a color from the last part is at most E /r. The number of parts is, therefore, at least ɛ n E r ɛ r. 6 Since any set of z edges is incident with at least z vertices we have that the total number of vertices incident with colors r + 1 and higher is at least ( ɛ r 1 ) E /r ɛ 3 r n r = ɛ r 18 n ρn, a contradiction to the fact that G is ρ-mean colored. Let E i be the set of edges colored i, let G i = (V, E i ), let E = E 1 E r and let G = (V, E ). By the argument above, E RT (n, K s, ρ mean) + ɛn / and G is ρ-mean colored. It suffices to show that G has a copy of H. We apply Lemma 3.4 to G and obtain a partition of V into m classes V 1 V m where 1/γ m M which is γ-regular simultaneously with respect to all graphs G i = (V, E i ) for 1 i r. Consider the cluster graph C(η). By choosing η sufficiently small as a function of ɛ we are guaranteed that C(η) has at least RT (m, K s, ρ mean) + ɛm /4 edges. To see this, notice that if C(η) had less edges then, by Lemma 3., by the definition of γ-regularity and by the definition of C(η), the number of edges of G would have been at most (RT (m, K s, ρ mean) + ɛ 4 m ) n m + η n m ( ) m + γ ( ) m n m + ( n/m RT (m, K s, ρ mean) n m + ɛ n RT (n, K s, ρ mean) + ɛ n contradicting the cardinality of E. In the last inequality we assume each color class has size n/m precisely. This may clearly be assumed since floors and ceilings may be dropped due to the asymptotic nature of our result. We define a coloring of the edges of C(η) as follows. The edge ij is colored by the color whose frequency in E (V i, V j ) is maximal. Notice that this frequency is at least (n /m )η/r. Let ρ be the average number of colors incident with each vertex in this coloring of C(η). We will show that ρ ρ + α. For i = 1,..., m let c(j) denote the number of colors incident with vertex j in our coloring of C(η). Clearly, c(1) + + c(m) = ρ m. For v V, let c(v) denote the number of colors incident with vertex v in the coloring of G. Clearly, v V c(v) ρn. We will show that almost all vertices v V j have c(v) c(j). Assume that color i appears in vertex j of C(η). Let V j,i V j be the set of vertices of V j incident with color i in G. We claim that V j V j,i γn/m. Indeed, if this was not the case then by letting Y = V j V j,i and letting X = V j ) m where j is any class for which jj is colored i we have that d(x, Y ) = 0 with respect to color i, while d(v j, V j ) η/r with respect to color i. Since η/r γ this contradicts the γ-regularity of the pair (V j, V j ) with respect to color i. Now, let W j = {v V j : c(v) c(j)}. We have therefore shown that W j V j γrn/m. Hence, ρn v V c(v) m j=1 v W j c(v) m c(j) n m (1 γr) = ρ n(1 γr). j=1 7 It follows that ρ ρ 1 γr ρ + α. We may now apply Lemma 3.1 to C(η) and obtain that C(η) has a monochromatic K s, say with color j. By Lemma 3.5 (applied to the spanning subgraph of C(η) induced by the edges colored j) this implies that G j = (V, E j ) contains a copy of T (st, s). In particular, there is a monochromatic copy of H in G. We have therefore proved that RT (n, H, ρ mean) RT (n, K s, ρ mean) + ɛn. Now, if H contains a K s then we also trivially have RT (n, H, ρ mean) RT (n, K s, ρ mean). This completes the proof of Theorem Acknowledgment The author thanks Y. Caro for useful discussions. References [1] B. Bollobás, Extremal Graph Theory, Academic Press, [] B. Biollobás, A. Kostochka and R. Schelp, Local and mean Ramsey numbers for trees, J. Combin. Theory Ser. B 79 (000), [3] S. Burr, P. Erdős and L. Lovász, On graphs of Ramsey type, Ars Combin. 1 (1976), [4] Y. Caro and Z. Tuza, On k-local and k-mean colorings of graphs and hypergraphs, Q. J. Math., Oxf. II. Ser. 44, No.176 (1993), [5] K. Corrádi and A. Hajnal, On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hungar. 14 (1963), [6] P. Erdős and A.H. Stone On the structure of linear graphs, Bull. Amer. Math. Soc. 5 (1946), [7] A. Gyárfás, J. Lehel, R. Schelp and Z. Tuza, Ramsey numbers for local colorings. Graphs Combin. 3 (1987), no. 3, [8] A. Hajnal and E. Szemerédi, Proof of a conjecture of Erdös, in: Combinatorial Theory and its Applications, Vol. II (P. Erdös, A. Renyi and V. T. Sós eds.), Colloq. Math. Soc. J. Bolyai 4, North Holland, Amsterdam 1970, [9] J. Komlós and M. Simonovits, Szemerédi Regularity lemma and its application in Graph Theory, in: Paul Erdős is 80, Proc. Coll. Bolyai Math. Soc. Vol. (Keszthely, 1993), [10] R. Schelp, Local and mean k-ramsey numbers for complete graphs, J. Graph Theory 4 (1997), [11] M. Simonovits and V.T. Sós, Ramsey-Turán theory, Discrete Math. 9, No.1-3 (001), [1] E. Szemerédi, Regular partitions of graphs, in: Proc. Colloque Inter. CNRS 60, CNRS, Paris, 1978,

Related Search

Similar documents

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks