×

Induced Ramsey-type theorems. (English) Zbl 1152.05054

Summary: We present a unified approach to proving Ramsey-type theorems for graphs with a forbidden induced subgraph which can be used to extend and improve the earlier results of Rödl, Erdős-Hajnal, Prömel-Rödl, Nikiforov, Chung-Graham, and Łuczak-Rödl. The proofs are based on a simple lemma (generalizing one by Graham, Rödl, and Ruciński) that can be used as a replacement for Szemerédi’s regularity lemma, thereby giving much better bounds. The same approach can be also used to show that pseudo-random graphs have strong induced Ramsey properties. This leads to explicit constructions for upper bounds on various induced Ramsey numbers.

MSC:

05D10 Ramsey theory
05C55 Generalized Ramsey theory
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N., The Shannon capacity of a union, Combinatorica, 18, 301-310 (1998) · Zbl 0921.05039
[2] Alon, N.; Krivelevich, M.; Sudakov, B., Induced subgraphs of prescribed size, J. Graph Theory, 43, 239-251 (2003) · Zbl 1025.05043
[3] Alon, N.; Pach, J.; Pinchasi, R.; Radoičić, R.; Sharir, M., Crossing patterns of semi-algebraic sets, J. Combin. Theory Ser. A, 111, 310-326 (2005) · Zbl 1099.14048
[4] Alon, N.; Pach, J.; Solymosi, J., Ramsey-type theorems with forbidden subgraphs, Combinatorica, 21, 155-170 (2001) · Zbl 0989.05124
[5] Alon, N.; Spencer, J. H., The Probabilistic Method (2000), Wiley: Wiley New York
[6] B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, A. Wigderson, Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors, in: Proceedings of the 37th ACM STOC, 2005, pp. 1-10; B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, A. Wigderson, Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors, in: Proceedings of the 37th ACM STOC, 2005, pp. 1-10 · Zbl 1192.68468
[7] B. Barak, A. Rao, R. Shaltiel, A. Wigderson, 2-Source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction, in: Proceedings of 38th ACM STOC, 2006, pp. 671-680; B. Barak, A. Rao, R. Shaltiel, A. Wigderson, 2-Source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction, in: Proceedings of 38th ACM STOC, 2006, pp. 671-680 · Zbl 1301.68191
[8] Beck, J., On size Ramsey number of paths, trees and circuits II, (Mathematics of Ramsey Theory. Mathematics of Ramsey Theory, Algorithms Combin., vol. 5 (1990), Springer: Springer Berlin), 34-45 · Zbl 0735.05056
[9] Bourgain, J., More on the sum-product phenomenon in prime fields and its applications, Int. J. Number Theory, 1, 1-32 (2005) · Zbl 1173.11310
[10] Bukh, B.; Sudakov, B., Induced subgraphs of Ramsey graphs with many distinct degrees, J. Combin. Theory Ser. B, 97, 612-619 (2007) · Zbl 1120.05057
[11] Burr, S. A.; Erdős, P., On the magnitude of generalized Ramsey numbers for graphs, (Infinite and Finite Sets, vol. 1. Infinite and Finite Sets, vol. 1, Colloquia Mathematica Societatis János Bolyai, vol. 10 (1975), North-Holland: North-Holland Amsterdam/London), 214-240
[12] M. Chudnovsky, S. Safra, The Erdős-Hajnal conjecture for bull-free graphs, J. Combin. Theory Ser. B (2008), doi:10.1016/j.jctb.2008.02.005; M. Chudnovsky, S. Safra, The Erdős-Hajnal conjecture for bull-free graphs, J. Combin. Theory Ser. B (2008), doi:10.1016/j.jctb.2008.02.005 · Zbl 1168.05317
[13] Chung, F. R.K.; Graham, R. L., On graphs not containing prescribed induced subgraphs, (Baker, A.; Bollobás, B.; Hajnal, A., A Tribute to Paul Erdős (1990), Cambridge University Press), 111-120 · Zbl 0743.05028
[14] Chung, F. R.K.; Graham, R. L.; Wilson, R. M., Quasi-random graphs, Combinatorica, 9, 345-362 (1989) · Zbl 0715.05057
[15] D. Conlon, A new upper bound for diagonal Ramsey numbers, Ann. of Math., in press; D. Conlon, A new upper bound for diagonal Ramsey numbers, Ann. of Math., in press · Zbl 1188.05087
[16] Deuber, W., A generalization of Ramsey’s theorem, (Infinite and Finite Sets, vol. 1. Infinite and Finite Sets, vol. 1, Colloquia Mathematica Societatis János Bolyai, vol. 10 (1975), North-Holland: North-Holland Amsterdam/London), 323-332 · Zbl 0301.05103
[17] Diestel, R., Graph Theory (1997), Springer
[18] Erdős, P., Some remarks on the theory of graphs, Bull. Amer. Math. Soc., 53, 292-294 (1947) · Zbl 0032.19203
[19] Erdős, P., On some problems in graph theory, combinatorial analysis and combinatorial number theory, (Bollobás, B., Graph Theory and Combinatorics. Graph Theory and Combinatorics, Cambridge, 1983 (1984), Academic Press: Academic Press London, New York), 1-17
[20] Erdős, P., Problems and results on finite and infinite graphs, (Recent Advances in Graph Theory, Proc. Second Czechoslovak Sympos.. Recent Advances in Graph Theory, Proc. Second Czechoslovak Sympos., Prague, 1974 (1975), Academia: Academia Prague), 183-192
[21] Erdős, P.; Goldberg, M.; Pach, J.; Spencer, J., Cutting a graph into two dissimilar halves, J. Graph Theory, 12, 121-131 (1988) · Zbl 0655.05059
[22] Erdős, P.; Hajnal, A., Ramsey-type theorems, Discrete Appl. Math., 25, 37-52 (1989) · Zbl 0715.05052
[23] Erdős, P.; Hajnal, A.; Pach, J., Ramsey-type theorem for bipartite graphs, Geombinatorics, 10, 64-68 (2000) · Zbl 0978.05052
[24] Erdős, P.; Hajnal, A.; Pósa, L., Strong embeddings of graphs into colored graphs, (Infinite and Finite Sets, vol. 1. Infinite and Finite Sets, vol. 1, Colloquia Mathematica Societatis János Bolyai, vol. 10 (1975), North-Holland: North-Holland Amsterdam/London), 585-595 · Zbl 0312.05123
[25] Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470 (1935) · Zbl 0012.27010
[26] Erdős, P.; Szemerédi, E., On a Ramsey type theorem, Period. Math. Hungar., 2, 295-299 (1972) · Zbl 0242.05122
[27] J. Fox, J. Pach, Cs.D. Tóth, Intersection patterns of curves, Israel J. Math., in press; J. Fox, J. Pach, Cs.D. Tóth, Intersection patterns of curves, Israel J. Math., in press
[28] J. Fox, B. Sudakov, Density theorems for bipartite graphs and related Ramsey-type results, preprint; J. Fox, B. Sudakov, Density theorems for bipartite graphs and related Ramsey-type results, preprint · Zbl 1212.05261
[29] Frankl, P.; Wilson, R., Intersection theorems with geometric consequences, Combinatorica, 1, 357-368 (1981) · Zbl 0498.05048
[30] Gorgol, I.; Łuczak, T., On induced Ramsey numbers, Discrete Math., 251, 87-96 (2002) · Zbl 1004.05042
[31] Gowers, W. T., Lower bounds of tower type for Szemerédi’s uniformity lemma, Geom. Funct. Anal., 7, 322-337 (1997) · Zbl 0876.05053
[32] Gowers, W. T., Rough structure and classification, GAFA 2000. GAFA 2000, Tel Aviv, 1999. GAFA 2000. GAFA 2000, Tel Aviv, 1999, Geom. Funct. Anal. (Special Volume, Part I), 79-117 (2000) · Zbl 0989.01020
[33] Graham, R.; Rödl, V.; Ruciński, A., On graphs with linear Ramsey numbers, J. Graph Theory, 35, 176-192 (2000) · Zbl 0965.05073
[34] Haxell, P. E.; Kohayakawa, Y.; Łuczak, T., The induced size-Ramsey number of cycles, Combin. Probab. Comput., 4, 217-240 (1995) · Zbl 0839.05073
[35] Kohayakawa, Y.; Prömel, H.; Rödl, V., Induced Ramsey numbers, Combinatorica, 18, 373-404 (1998) · Zbl 0913.05074
[36] Komlós, J.; Simonovits, M., Szemerédi’s regularity lemma and its applications in graph theory, (Combinatorics, Paul Erdős is Eighty, vol. 2. Combinatorics, Paul Erdős is Eighty, vol. 2, Keszthely, 1993. Combinatorics, Paul Erdős is Eighty, vol. 2. Combinatorics, Paul Erdős is Eighty, vol. 2, Keszthely, 1993, Bolyai Soc. Math. Stud., vol. 2 (1996), János Bolyai Math. Soc.: János Bolyai Math. Soc. Budapest), 295-352 · Zbl 0851.05065
[37] Krivelevich, M.; Sudakov, B., Pseudo-random graphs, (More Sets, Graphs and Numbers. More Sets, Graphs and Numbers, Bolyai Soc. Math. Stud., vol. 15 (2006), Springer), 199-262 · Zbl 1098.05075
[38] Larman, D.; Matoušek, J.; Pach, J.; Törőcsik, J., A Ramsey-type result for convex sets, Bull. London Math. Soc., 26, 132-136 (1994) · Zbl 0809.05090
[39] Łuczak, T.; Rödl, V., On induced Ramsey numbers for graphs with bounded maximum degree, J. Combin. Theory Ser. B, 66, 324-333 (1996) · Zbl 0855.05084
[40] Nikiforov, V., Edge distribution of graphs with few copies of a given graph, Combin. Probab. Comput., 15, 895-902 (2006) · Zbl 1120.05072
[41] Prömel, H.; Rödl, V., Non-Ramsey graphs are \(c \log n\)-universal, J. Combin. Theory Ser. A, 88, 379-384 (1999) · Zbl 0934.05090
[42] Ramsey, F. P., On a problem of formal logic, Proc. London Math. Soc., 30, 264-286 (1930) · JFM 55.0032.04
[43] V. Rödl, The dimension of a graph and generalized Ramsey theorems, Master’s thesis, Charles University, 1973; V. Rödl, The dimension of a graph and generalized Ramsey theorems, Master’s thesis, Charles University, 1973
[44] Rödl, V., On universality of graphs with uniformly distributed edges, Discrete Math., 59, 125-134 (1986) · Zbl 0619.05035
[45] Schaefer, M.; Shah, P., Induced graph Ramsey theory, Ars Combin., 66, 3-21 (2003) · Zbl 1075.05568
[46] Shelah, S., Erdős and Rényi conjecture, J. Combin. Theory Ser. A, 82, 179-185 (1998) · Zbl 0906.05048
[47] E. Szemerédi, Regular partitions of graphs, in: Colloques Internationaux CNRS 260—Problémes Combinatoires et Théorie des Graphes, Orsay, 1976, pp. 399-401; E. Szemerédi, Regular partitions of graphs, in: Colloques Internationaux CNRS 260—Problémes Combinatoires et Théorie des Graphes, Orsay, 1976, pp. 399-401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.