Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-23T23:23:29.107Z Has data issue: false hasContentIssue false
  • English
  • Français

Short Proofs of Some Extremal Results

Published online by Cambridge University Press:  04 November 2013

DAVID CONLON ,
JACOB FOX  and
BENNY SUDAKOV
DAVID CONLON
Affiliation:
Mathematical Institute, Oxford OX1 3LB, UK (e-mail: [email protected])
JACOB FOX
Affiliation:
Department of Mathematics, MIT, Cambridge, MA 02139-4307, USA (e-mail: [email protected])
BENNY SUDAKOV
Affiliation:
Department of Mathematics, UCLA, Los Angeles, CA 90095, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove several results from different areas of extremal combinatorics, giving complete or partial solutions to a number of open problems. These results, coming from areas such as extremal graph theory, Ramsey theory and additive combinatorics, have been collected together because in each case the relevant proofs are quite short.

Keywords

Primary 05C35Secondary 05C5511B30
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 1 , January 2014 , pp. 8 - 28
Copyright
Copyright © Cambridge University Press 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Akiyama, J. and Watanabe, M. (1987) Maximum induced forests of planar graphs. Graphs Combin. 3 201–202.CrossRefGoogle Scholar
[2]Albertson, M. and Haas, R. (1998) A problem raised at the DIMACS Graph Coloring Week.Google Scholar
[3]Alon, N. (2003) Problems and results in extremal combinatorics I. Discrete Math. 273 31–53.CrossRefGoogle Scholar
[4]Alon, N. (2008) Problems and results in extremal combinatorics II. Discrete Math. 308 4460–4472.CrossRefGoogle Scholar
[5]Alon, N. and Krivelevich, M. (1997) Constructive bounds for a Ramsey-type problem. Graphs Combin. 13 217–225.CrossRefGoogle Scholar
[6]Alon, N., Mubayi, D. and Thomas, R. (2001) Large induced forests in sparse graphs. J. Graph Theory 38 113–123.CrossRefGoogle Scholar
[7]Balister, P., Lehel, J. and Schelp, R. H. (2006) Ramsey unsaturated and saturated graphs. J. Graph Theory 51 22–32.CrossRefGoogle Scholar
[8]Beck, J. (1993) Achievement games and the probabilistic method. In Combinatorics: Paul Erdős is Eighty, Vol. 1, Bolyai Mathematical Society, pp. 51–78.Google Scholar
[9]Brown, T. C., Chung, F. R. K., Erdős, P. and Graham, R. L. (1985) Quantitative forms of a theorem of Hilbert. J. Combin. Theory Ser. A 38 210–216.CrossRefGoogle Scholar
[10]Butterfield, J., Grauman, T., Kinnersley, W. B., Milans, K. G., Stocker, C. and West, D. B. (2011) On-line Ramsey theory for bounded degree graphs. Electron. J. Combin. 18 #136.CrossRefGoogle Scholar
[11]Cavers, M. and Verstraëte, J. (2008) Clique partitions of complements of forests and bounded degree graphs. Discrete Math. 308 2011–2017.CrossRefGoogle Scholar
[12]Chang, Y. (1996) A bound for Wilson's theorem III. J. Combin. Des. 4 83–93.3.0.CO;2-V>CrossRefGoogle Scholar
[13]Conlon, D. (2009) Hypergraph packing and sparse bipartite Ramsey numbers. Combin. Probab. Comput. 18 913–923.CrossRefGoogle Scholar
[14]Conlon, D. (2009/10) On-line Ramsey numbers. SIAM J. Discrete Math. 23 1954–1963.CrossRefGoogle Scholar
[15]Conlon, D. (2013) The Ramsey number of dense graphs. Bull. London Math. Soc. 45 483–496.CrossRefGoogle Scholar
[16]Conlon, D., Fox, J. and Sudakov, B. (2010) Hypergraph Ramsey numbers. J. Amer. Math. Soc. 23 247–266.CrossRefGoogle Scholar
[17]Dudek, A. and Mubayi, D. On generalized Ramsey numbers for 3-uniform hypergraphs. J. Graph Theory. Preprint.Google Scholar
[18]Dudek, A., Retter, T. and Rödl, V. On generalized Ramsey numbers of Erdős and Rogers. Preprint.Google Scholar
[19]Dudek, A. and Rödl, V. (2011) On Ks-free subgraphs in Ks+k-free graphs and vertex Folkman numbers. Combinatorica 31 39–53.CrossRefGoogle Scholar
[20]Erdős, P. and Gallai, T. (1961) On the minimal number of vertices representing the edges of a graph. Publ. Math. Inst. Hungar. Acad. Sci. 6 181–202.Google Scholar
[21]Erdős, P. and Rado, R. (1952) Combinatorial theorems on classifications of subsets of a given set. Proc. London Math. Soc. 3 417–439.CrossRefGoogle Scholar
[22]Erdős, P. and Rogers, C. A. (1962) The construction of certain graphs. Canad. J. Math. 14 702–707.CrossRefGoogle Scholar
[23]Fox, J. and Sudakov, B. (2009) Density theorems for bipartite graphs and related Ramsey-type results. Combinatorica 29 153–196.CrossRefGoogle Scholar
[24]Friedgut, E., Kohayakawa, Y., Rödl, V., Ruciński, A. and Tetali, P. (2003) Ramsey games against a one-armed bandit. Combin. Probab. Comput. 12 515–545.CrossRefGoogle Scholar
[25]Gregory, D. A., McGuinness, S. and Wallis, W. (1986) Clique partitions of the cocktail party graph. Discrete Math. 59 267–273.CrossRefGoogle Scholar
[26]Grytczuk, J. A., Hałuszczak, M. and Kierstead, H. A. (2004) On-line Ramsey theory. Electron. J. Combin. 11 #57.CrossRefGoogle Scholar
[27]Gunderson, D. S., Rödl, V. and Sidorenko, A. (1999) Extremal problems for sets forming Boolean algebras and complete partite hypergraphs. J. Combin. Theory Ser. A 88 342–367.CrossRefGoogle Scholar
[28]Hegyvári, N. (1996) On representation problems in the additive number theory. Acta Math. Hungar. 72 35–44.CrossRefGoogle Scholar
[29]Hegyvári, N. (1999) On the dimension of the Hilbert cubes. J. Number Theory 77 326–330.CrossRefGoogle Scholar
[30]Hilbert, D. (1892) Über die Irreduzibilität ganzer rationaler Funktionen mit ganzzahligen Koeffizienten. J. Reine Angew. Math. 110 104–129.CrossRefGoogle Scholar
[31]Kierstead, H. A. and Konjevod, G. (2009) Coloring number and on-line Ramsey theory for graphs and hypergraphs. Combinatorica 29 49–64.CrossRefGoogle Scholar
[32]Kowalik, Ł, Lužar, B. and Škrekovski, R. (2010) An improved bound on the largest induced forests for triangle-free planar graphs. Discrete Math. Theor. Comput. Sci. 12 87–100.Google Scholar
[33]Krivelevich, M. (1994) Ks-free graphs without large Kr-free subgraphs. Combin. Probab. Comput. 3 349–354.CrossRefGoogle Scholar
[34]Krivelevich, M. (1995) Bounding Ramsey numbers through large deviation inequalities. Random Struct. Alg. 7 145–155.CrossRefGoogle Scholar
[35]Kurek, A. and Ruciński, A. (2005) Two variants of the size Ramsey number. Discuss. Math. Graph Theory 25 141–149.CrossRefGoogle Scholar
[36]Marciniszyn, M., Spöhel, R. and Steger, A. (2009) Online Ramsey games in random graphs. Combin. Probab. Comput. 18 271–300.Google Scholar
[37]Marciniszyn, M., Spöhel, R. and Steger, A. (2009) Upper bounds for online Ramsey games in random graphs. Combin. Probab. Comput. 18 259–270.CrossRefGoogle Scholar
[38]Nguyen, H. and Vu, V. (2011) Optimal inverse Littlewood–Offord theorems. Adv. Math. 226 5298–5319.CrossRefGoogle Scholar
[39]Orlin, J. (1977) Contentment in graph theory. Indag. Math. 39 406–424.CrossRefGoogle Scholar
[40]Ramsey, F. P. (1930) On a problem of formal logic. Proc. London Math. Soc. Ser. 2 30 264–286.CrossRefGoogle Scholar
[41]Salavatipour, M. R. (2006) Large induced forests in triangle-free planar graphs. Graphs Combin. 22 113–126.CrossRefGoogle Scholar
[42]Shearer, J. B. (1995) On the independence number of sparse graphs. Random Struct. Alg. 7 269–271.CrossRefGoogle Scholar
[43]Skokan, J. and Stein, M. Cycles are strongly Ramsey-unsaturated. Combin. Probab. Comput., to appear.Google Scholar
[44]Sudakov, B. (2005) A new lower bound for a Ramsey-type problem. Combinatorica 25 487–498.CrossRefGoogle Scholar
[45]Sudakov, B. (2005) Large Kr-free subgraphs in Ks-free graphs and some other Ramsey-type problems. Random Struct. Alg. 26 253–265.CrossRefGoogle Scholar
[46]Sudakov, B. (2011) A conjecture of Erdős on graph Ramsey numbers. Adv. Math. 227 601–609.CrossRefGoogle Scholar
[47]Szemerédi, E. (1969) On sets of integers containing no four elements in arithmetic progression. Acta Math. Acad. Sci. Hungar. 20 199–245.CrossRefGoogle Scholar
[48]Tao, T. and Vu, V. (2009) Inverse Littlewood–Offord theorems and the condition number of random discrete matrices. Ann. of Math. 169 595–632.CrossRefGoogle Scholar
[49]Tao, T. and Vu, V. (2010) A sharp inverse Littlewood–Offord theorem. Random Struct. Alg. 37 525–539.CrossRefGoogle Scholar
[50]Wallis, W. D. (1985) Clique partitions of the complement of a one-factor. Congr. Numer. 46 317–319.Google Scholar
[51]Wallis, W. D. (1990) Finite planes and clique partitions. Contemp. Math. 111 279–285.CrossRefGoogle Scholar
[52]Wilson, R. M. (1974) Constructions and uses of pairwise balanced designs. In Combinatorics: Proc. NATO Advanced Study Inst., Breukelen, 1974, Part 1: Theory of Designs, Finite Geometry and Coding Theory, No. 55 of Math. Centre Tracts, Math Centrum, Amsterdam, pp. 18–41.Google Scholar
[53]Wolfovitz, G.K 4-free graphs without large induced triangle-free subgraphs. Combinatorica, to appear.Google Scholar