Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T09:25:47.349Z Has data issue: false hasContentIssue false
  • English
  • Français

Hypergraph Packing and Sparse Bipartite Ramsey Numbers

Published online by Cambridge University Press:  22 June 2009

DAVID CONLON
DAVID CONLON*
Affiliation:
St John's College, Cambridge CB2 1TP, UK (e-mail: D.Conlon@dpmms.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We prove that there exists a constant c such that, for any integer Δ, the Ramsey number of a bipartite graph on n vertices with maximum degree Δ is less than 2cΔn. A probabilistic argument due to Graham, Rödl and Ruciński implies that this result is essentially sharp, up to the constant c in the exponent. Our proof hinges upon a quantitative form of a hypergraph packing result of Rödl, Ruciński and Taraz.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 6 , November 2009 , pp. 913 - 923
Copyright
Copyright © Cambridge University Press 2009

References

[1]Alon, N. (1994) Subdivided graphs have linear Ramsey numbers. J. Graph Theory 18 343–347.CrossRefGoogle Scholar
[2]Alon, N., Krivelevich, M. and Sudakov, B. (2003) Turán numbers of bipartite graphs and related Ramsey-type questions. Combin. Probab. Comput. 12 477–494.CrossRefGoogle Scholar
[3]Beck, J. (1983) An upper bound for diagonal Ramsey numbers. Studia Sci. Math. Hungar. 18 401–406.Google Scholar
[4]Burr, S. A. and Erdős, P. (1975) On the magnitude of generalized Ramsey numbers for graphs. In Infinite and Finite Combinatorics 1, Vol. 10 of Colloq. Math. Soc. János Bolyai, pp. 214–240.Google Scholar
[5]Chen, G. and Schelp, R. (1993) Graphs with linearly bounded Ramsey numbers. J. Combin. Theory Ser. B 57 138–149.CrossRefGoogle Scholar
[6]Chung, F. and Graham, R. L. (1998) Erdős on Graphs: His Legacy of Unsolved Problems, A. K. Peters, Wellesley, MA.CrossRefGoogle Scholar
[7]Chvátal, V., Rödl, V., Szemerédi, E. and Trotter, W. T. Jr., (1983) The Ramsey number of a graph with bounded maximum degree. J. Combin. Theory Ser. B 34 239–243.CrossRefGoogle Scholar
[8]Eaton, N. (1998) Ramsey numbers for sparse graphs. Discrete Math. 185 63–75.CrossRefGoogle Scholar
[9]Erdős, P. (1984) On some problems in graph theory, combinatorial analysis and combinatorial number theory. In Graph Theory and Combinatorics (Cambridge 1983), Academic Press, London, pp. 1–17.Google Scholar
[10]Erdős, P. and Szekeres, G. (1935) A combinatorial problem in geometry. Compositio Mathematica 2 463–470.Google Scholar
[11]Fox, J. and Sudakov, B. Density theorems for bipartite graphs and related Ramsey-type results. Combinatorica, to appear.Google Scholar
[12]Gowers, W. T. (1997) Lower bounds of tower type for Szemerédi's uniformity lemma. Geom. Funct. Anal. 7 322–337.CrossRefGoogle Scholar
[13]Gowers, W. T. (1998) A new proof of Szemerédi's theorem for arithmetic progressions of length 4. Geom. Funct. Anal. 8 529–551.CrossRefGoogle Scholar
[14]Graham, R. L., Rödl, V. and Ruciński, A. (2000) On graphs with linear Ramsey numbers. J. Graph Theory 35 176–192.3.0.CO;2-C>CrossRefGoogle Scholar
[15]Graham, R. L., Rödl, V. and Ruciński, A. (2001) On bipartite graphs with linear Ramsey numbers. Combinatorica 21 199–209.CrossRefGoogle Scholar
[16]Komlós, J. and Simonovits, M. (1996) Szemerédi's regularity lemma and its applications in graph theory. In Combinatorics: Paul Erdős is Eighty, Vol. 2 (Keszthely 1993), Budapest, pp. 295–352.Google Scholar
[17]Kostochka, A. and Rödl, V. (2001) On graphs with small Ramsey numbers. J. Graph Theory 37 198–204.CrossRefGoogle Scholar
[18]Kostochka, A. and Rödl, V. (2004) On graphs with small Ramsey numbers II. Combinatorica 24 389–401.CrossRefGoogle Scholar
[19]Kostochka, A. and Sudakov, B. (2003) On Ramsey numbers of sparse graphs. Combin. Probab. Comput. 12 627–641.CrossRefGoogle Scholar
[20]Ramsey, F. P. (1930) On a problem of formal logic. Proc. London Math. Soc. Ser. 2 30 264–286.CrossRefGoogle Scholar
[21]Rödl, V., Ruciński, A. and Taraz, A. (1999) Hypergraph packing and graph embedding. Combin. Probab. Comput. 8 363–376.CrossRefGoogle Scholar
[22]Sauer, N. and Spencer, J. (1978) Edge disjoint placement of graphs. J. Combin. Theory Ser. B 25 295–302.CrossRefGoogle Scholar
[23]Shi, L. (2001) Cube Ramsey numbers are polynomial. Random Struct. Alg. 19 99–101.Google Scholar
[24]Shi, L. (2007) The tail is cut for Ramsey numbers of cubes. Discrete Math. 307 290–292.CrossRefGoogle Scholar
[25]Sudakov, B. (2003) A few remarks on Ramsey–Turán-type problems. J. Combin. Theory Ser. B 88 99–106.CrossRefGoogle Scholar