Ramsey numbers of degenerate graphs

Pages 791-829 from Volume 185 (2017), Issue 3 by Choongbum Lee

Abstract

A graph is $d$-degenerate if all its subgraphs have a vertex of degree at most $d$. We prove that there exists a constant $c$ such that for all natural numbers $d$ and $r$, every $d$-degenerate graph $H$ of chromatic number $r$ with $|V(H)| \ge 2^{d^22^{cr}}$ has Ramsey number at most $2^{d2^{cr}} |V(H)|$. This solves a conjecture of Burr and Erdős from 1973.

  • [Alon] Go to document N. Alon, "Subdivided graphs have linear Ramsey numbers," J. Graph Theory, vol. 18, iss. 4, pp. 343-347, 1994.
    @ARTICLE{Alon, mrkey = {1277513},
      number = {4},
      issn = {0364-9024},
      author = {Alon, Noga},
      mrclass = {05C55},
      doi = {10.1002/jgt.3190180406},
      journal = {J. Graph Theory},
      zblnumber = {0811.05046},
      volume = {18},
      mrnumber = {1277513},
      fjournal = {Journal of Graph Theory},
      mrreviewer = {R. H. Schelp},
      coden = {JGTHDO},
      title = {Subdivided graphs have linear {R}amsey numbers},
      year = {1994},
      pages = {343--347},
      }
  • [AlKrSu] N. Alon, M. Krivelevich, and B. Sudakov, "Turán numbers of bipartite graphs and related Ramsey-type questions," Combin. Probab. Comput., vol. 12, iss. 5-6, pp. 477-494, 2003.
    @ARTICLE{AlKrSu, mrkey = {2037065},
      number = {5-6},
      issn = {0963-5483},
      author = {Alon, Noga and Krivelevich, Michael and Sudakov, Benny},
      mrclass = {05C35 (05C55 05D10 05D40)},
      journal = {Combin. Probab. Comput.},
      zblnumber = {1060.05050},
      volume = {12},
      mrnumber = {2037065},
      fjournal = {Combinatorics, Probability and Computing},
      mrreviewer = {Sheshayya A. Choudum},
      title = {Turán numbers of bipartite graphs and related {R}amsey-type questions},
      year = {2003},
      pages = {477--494},
      }
  • [BoScTa] Go to document J. Böttcher, M. Schacht, and A. Taraz, "Proof of the bandwidth conjecture of Bollobás and Komlós," Math. Ann., vol. 343, iss. 1, pp. 175-205, 2009.
    @ARTICLE{BoScTa, mrkey = {2448444},
      number = {1},
      issn = {0025-5831},
      author = {B{ö}ttcher, Julia and Schacht, Mathias and Taraz, Anusch},
      mrclass = {05C35 (05C15 05C70 05C78)},
      doi = {10.1007/s00208-008-0268-6},
      journal = {Math. Ann.},
      zblnumber = {1229.05132},
      volume = {343},
      mrnumber = {2448444},
      fjournal = {Mathematische Annalen},
      mrreviewer = {Deryk Osthus},
      coden = {MAANA},
      title = {Proof of the bandwidth conjecture of {B}ollobás and {K}omlós},
      year = {2009},
      pages = {175--205},
      }
  • [BuEr] S. A. Burr and P. ErdHos, "On the magnitude of generalized Ramsey numbers for graphs," in Infinite and Finite Sets, Vol. 1, Amsterdam: North-Holland, 1975, vol. 10, pp. 215-240.
    @INCOLLECTION{BuEr, mrkey = {0371701},
      author = {Burr, S. A. and Erd{ő}s, P.},
      mrclass = {05C10},
      series = {Colloq. Math. Soc. János Bolyai},
      address = {Amsterdam},
      publisher = {North-Holland},
      volume = {10},
      mrnumber = {0371701},
      booktitle = {Infinite and Finite Sets, {V}ol. 1},
      mrreviewer = {D. J. Kleitman},
      venue = {{C}olloq., {K}eszthely, 1973; dedicated to {P}. {E}rdős on his 60th birthday},
      title = {On the magnitude of generalized {R}amsey numbers for graphs},
      pages = {215--240},
      year = {1975},
      zblnumber = {0316.05110},
      }
  • [ChRoSzTr] Go to document C. Chvatál, V. Rödl, E. Szemerédi, and W. T. Trotter Jr., "The Ramsey number of a graph with bounded maximum degree," J. Combin. Theory Ser. B, vol. 34, iss. 3, pp. 239-243, 1983.
    @ARTICLE{ChRoSzTr, mrkey = {0714447},
      number = {3},
      issn = {0095-8956},
      author = {Chvat{á}l, C. and R{ö}dl, V. and Szemer{é}di, E. and Trotter, Jr., W. T.},
      mrclass = {05C55},
      doi = {10.1016/0095-8956(83)90037-0},
      journal = {J. Combin. Theory Ser. B},
      zblnumber = {0547.05044},
      volume = {34},
      mrnumber = {0714447},
      fjournal = {Journal of Combinatorial Theory. Series B},
      mrreviewer = {Stefan A. Burr},
      coden = {JCBTB8},
      title = {The {R}amsey number of a graph with bounded maximum degree},
      year = {1983},
      pages = {239--243},
      }
  • [ChSc] Go to document G. Chen and R. H. Schelp, "Graphs with linearly bounded Ramsey numbers," J. Combin. Theory Ser. B, vol. 57, iss. 1, pp. 138-149, 1993.
    @ARTICLE{ChSc, mrkey = {1198403},
      number = {1},
      issn = {0095-8956},
      author = {Chen, Guantao and Schelp, R. H.},
      mrclass = {05C55},
      doi = {10.1006/jctb.1993.1012},
      journal = {J. Combin. Theory Ser. B},
      zblnumber = {0725.05076},
      volume = {57},
      mrnumber = {1198403},
      fjournal = {Journal of Combinatorial Theory. Series B},
      mrreviewer = {J. E. Graver},
      coden = {JCBTB8},
      title = {Graphs with linearly bounded {R}amsey numbers},
      year = {1993},
      pages = {138--149},
      }
  • [Conlon_diag] Go to document D. Conlon, "A new upper bound for diagonal Ramsey numbers," Ann. of Math., vol. 170, iss. 2, pp. 941-960, 2009.
    @ARTICLE{Conlon_diag, mrkey = {2552114},
      number = {2},
      issn = {0003-486X},
      author = {Conlon, David},
      mrclass = {05C55},
      doi = {10.4007/annals.2009.170.941},
      journal = {Ann. of Math.},
      zblnumber = {1188.05087},
      volume = {170},
      mrnumber = {2552114},
      fjournal = {Annals of Mathematics. Second Series},
      coden = {ANMAAH},
      title = {A new upper bound for diagonal {R}amsey numbers},
      year = {2009},
      pages = {941--960},
      }
  • [Conlon] Go to document D. Conlon, "Hypergraph packing and sparse bipartite Ramsey numbers," Combin. Probab. Comput., vol. 18, iss. 6, pp. 913-923, 2009.
    @ARTICLE{Conlon, mrkey = {2550376},
      number = {6},
      issn = {0963-5483},
      author = {Conlon, David},
      mrclass = {05C55 (05C35 05C65)},
      doi = {10.1017/S0963548309990174},
      journal = {Combin. Probab. Comput.},
      zblnumber = {1191.05064},
      volume = {18},
      mrnumber = {2550376},
      fjournal = {Combinatorics, Probability and Computing},
      mrreviewer = {A. G. Thomason},
      title = {Hypergraph packing and sparse bipartite {R}amsey numbers},
      year = {2009},
      pages = {913--923},
      }
  • [CoFoSu] Go to document D. Conlon, J. Fox, and B. Sudakov, "On two problems in graph Ramsey theory," Combinatorica, vol. 32, iss. 5, pp. 513-535, 2012.
    @ARTICLE{CoFoSu, mrkey = {3004807},
      number = {5},
      issn = {0209-9683},
      author = {Conlon, David and Fox, Jacob and Sudakov, Benny},
      mrclass = {05C55 (05D10)},
      DOI = {10.1007/s00493-012-2710-3},
      journal = {Combinatorica},
      zblnumber = {1289.05332},
      volume = {32},
      mrnumber = {3004807},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      mrreviewer = {Maria A. Axenovich},
      title = {On two problems in graph {R}amsey theory},
      year = {2012},
      pages = {513--535},
      }
  • [CoFoSu_survey] Go to document D. Conlon, J. Fox, and B. Sudakov, "Recent developments in graph Ramsey theory," in Surveys in Combinatorics 2015, Cambridge: Cambridge Univ. Press, 2015, vol. 424, pp. 49-118.
    @INCOLLECTION{CoFoSu_survey, mrkey = {3497267},
      author = {Conlon, David and Fox, Jacob and Sudakov, Benny},
      mrclass = {05-02 (05C55)},
      series = {London Math. Soc. Lecture Note Ser.},
      address = {Cambridge},
      publisher = {Cambridge Univ. Press},
      volume = {424},
      mrnumber = {3497267},
      booktitle = {Surveys in Combinatorics 2015},
      title = {Recent developments in graph {R}amsey theory},
      pages = {49--118},
      year = {2015},
      zblnumber = {1352.05123},
      doi = {10.1017/CBO9781316106853},
     }
  • [CoFoSu_ext] Go to document D. Conlon, J. Fox, and B. Sudakov, "Short proofs of some extremal results II," J. Combin. Theory Ser. B, vol. 121, pp. 173-196, 2016.
    @ARTICLE{CoFoSu_ext, mrkey = {3548291},
      issn = {0095-8956},
      author = {Conlon, David and Fox, Jacob and Sudakov, Benny},
      mrclass = {05C35 (05C55)},
      doi = {10.1016/j.jctb.2016.03.005},
      journal = {J. Combin. Theory Ser. B},
      zblnumber = {1348.05209},
      volume = {121},
      mrnumber = {3548291},
      fjournal = {Journal of Combinatorial Theory. Series B},
      coden = {JCBTB8},
      title = {Short proofs of some extremal results {II}},
      year = {2016},
      pages = {173--196},
      }
  • [Eaton] Go to document N. Eaton, "Ramsey numbers for sparse graphs," Discrete Math., vol. 185, iss. 1-3, pp. 63-75, 1998.
    @ARTICLE{Eaton, mrkey = {1614289},
      number = {1-3},
      issn = {0012-365X},
      author = {Eaton, Nancy},
      mrclass = {05C55},
      doi = {10.1016/S0012-365X(97)00184-2},
      journal = {Discrete Math.},
      zblnumber = {0955.05071},
      volume = {185},
      mrnumber = {1614289},
      fjournal = {Discrete Mathematics},
      coden = {DSMHA4},
      title = {Ramsey numbers for sparse graphs},
      year = {1998},
      pages = {63--75},
      }
  • [Erdos] Go to document P. Erdös, "Some remarks on the theory of graphs," Bull. Amer. Math. Soc., vol. 53, pp. 292-294, 1947.
    @ARTICLE{Erdos, mrkey = {0019911},
      issn = {0002-9904},
      author = {Erd{ö}s, P.},
      mrclass = {56.0X},
      doi = {10.1090/S0002-9904-1947-08785-1},
      journal = {Bull. Amer. Math. Soc.},
      zblnumber = {0032.19203},
      volume = {53},
      mrnumber = {0019911},
      fjournal = {Bulletin of the American Mathematical Society},
      mrreviewer = {H. S. M. Coxeter},
      title = {Some remarks on the theory of graphs},
      year = {1947},
      pages = {292--294},
      }
  • [ErSz] Go to document P. Erdös and G. Szekeres, "A combinatorial problem in geometry," Compositio Math., vol. 2, pp. 463-470, 1935.
    @ARTICLE{ErSz, mrkey = {1556929},
      issn = {0010-437X},
      author = {Erd{ö}s, P. and Szekeres, G.},
      mrclass = {Contributed Item},
      url = {http://www.numdam.org/item?id=CM_1935__2__463_0},
      journal = {Compositio Math.},
      zblnumber = {0012.27010},
      volume = {2},
      mrnumber = {1556929},
      fjournal = {Compositio Mathematica},
      title = {A combinatorial problem in geometry},
      year = {1935},
      pages = {463--470},
      }
  • [FoSu09] Go to document J. Fox and B. Sudakov, "Density theorems for bipartite graphs and related Ramsey-type results," Combinatorica, vol. 29, iss. 2, pp. 153-196, 2009.
    @ARTICLE{FoSu09, mrkey = {2520279},
      number = {2},
      issn = {0209-9683},
      author = {Fox, Jacob and Sudakov, Benny},
      mrclass = {05C55 (05C35 05D10 05D40)},
      journal = {Combinatorica},
      zblnumber = {1212.05261},
      volume = {29},
      mrnumber = {2520279},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      title = {Density theorems for bipartite graphs and related {R}amsey-type results},
      year = {2009},
      pages = {153--196},
      DOI = {10.1007/s00493-009-2475-5},
     }
  • [FoSu09-2] Go to document J. Fox and B. Sudakov, "Two remarks on the Burr-Erdős conjecture," European J. Combin., vol. 30, iss. 7, pp. 1630-1645, 2009.
    @ARTICLE{FoSu09-2, mrkey = {2548655},
      number = {7},
      issn = {0195-6698},
      author = {Fox, Jacob and Sudakov, Benny},
      mrclass = {05C55},
      doi = {10.1016/j.ejc.2009.03.004},
      journal = {European J. Combin.},
      zblnumber = {1223.05185},
      volume = {30},
      mrnumber = {2548655},
      fjournal = {European Journal of Combinatorics},
      mrreviewer = {Lingsheng Shi},
      title = {Two remarks on the {B}urr-{E}rdős conjecture},
      year = {2009},
      pages = {1630--1645},
      }
  • [FoSu11] Go to document J. Fox and B. Sudakov, "Dependent random choice," Random Structures Algorithms, vol. 38, iss. 1-2, pp. 68-99, 2011.
    @ARTICLE{FoSu11, mrkey = {2768884},
      number = {1-2},
      issn = {1042-9832},
      author = {Fox, Jacob and Sudakov, Benny},
      mrclass = {05D40 (05C35 05C55 05D10 60C05)},
      doi = {10.1002/rsa.20344},
      journal = {Random Structures Algorithms},
      zblnumber = {1215.05159},
      volume = {38},
      mrnumber = {2768884},
      fjournal = {Random Structures \& Algorithms},
      mrreviewer = {Hamed Hatami},
      title = {Dependent random choice},
      year = {2011},
      pages = {68--99},
      }
  • [GrRoRu00] R. L. Graham, V. Rödl, and A. Ruciński, "On graphs with linear Ramsey numbers," J. Graph Theory, vol. 35, iss. 3, pp. 176-192, 2000.
    @ARTICLE{GrRoRu00, mrkey = {1788033},
      number = {3},
      issn = {0364-9024},
      author = {Graham, R. L. and R{ö}dl, V. and Ruci{ń}ski, A.},
      mrclass = {05C55},
      journal = {J. Graph Theory},
      zblnumber = {0965.05073},
      volume = {35},
      mrnumber = {1788033},
      fjournal = {Journal of Graph Theory},
      mrreviewer = {R. H. Schelp},
      coden = {JGTHDO},
      title = {On graphs with linear {R}amsey numbers},
      year = {2000},
      pages = {176--192},
      }
  • [GrRoRu01] Go to document R. L. Graham, V. Rödl, and A. Ruciński, "On bipartite graphs with linear Ramsey numbers," Combinatorica, vol. 21, iss. 2, pp. 199-209, 2001.
    @ARTICLE{GrRoRu01, mrkey = {1832445},
      number = {2},
      issn = {0209-9683},
      author = {Graham, R. L. and R{ö}dl, V. and Ruci{ń}ski, A.},
      mrclass = {05C55 (05C80 05D40)},
      doi = {10.1007/s004930100018},
      journal = {Combinatorica},
      zblnumber = {0989.05078},
      volume = {21},
      mrnumber = {1832445},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      mrreviewer = {C. C. Rousseau},
      title = {On bipartite graphs with linear {R}amsey numbers},
      year = {2001},
      pages = {199--209},
      }
  • [GrRoSp] R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey Theory, Second ed., New York: John Wiley & Sons, 1990.
    @BOOK{GrRoSp, mrkey = {1044995},
      author = {Graham, Ronald L. and Rothschild, Bruce L. and Spencer, Joel H.},
      mrclass = {05-02 (04A20 05A99 05C55 54H20)},
      series = {Wiley-Intersci. Ser. Discrete Math. Optim.},
      edition = {Second},
      isbn = {0-471-50046-1},
      address = {New York},
      publisher = {John Wiley \& Sons},
      zblnumber = {0705.05061},
      mrnumber = {1044995},
      title = {Ramsey Theory},
      year = {1990},
      pages = {xii+196},
      }
  • [HaJe] Go to document A. W. Hales and R. I. Jewett, "Regularity and positional games," Trans. Amer. Math. Soc., vol. 106, pp. 222-229, 1963.
    @ARTICLE{HaJe, mrkey = {0143712},
      issn = {0002-9947},
      author = {Hales, A. W. and Jewett, R. I.},
      mrclass = {05.55},
      doi = {10.1090/S0002-9947-1963-0143712-1},
      journal = {Trans. Amer. Math. Soc.},
      zblnumber = {0113.14802},
      volume = {106},
      mrnumber = {0143712},
      fjournal = {Transactions of the American Mathematical Society},
      mrreviewer = {J. W. Moon},
      title = {Regularity and positional games},
      year = {1963},
      pages = {222--229},
      }
  • [JaLuRu] Go to document S. Janson, T. Łuczak, and A. Rucinski, Random Graphs, New York: John Wiley & Sons, 2000.
    @BOOK{JaLuRu, mrkey = {1782847},
      author = {Janson, Svante and {\L}uczak, Tomasz and Rucinski, Andrzej},
      mrclass = {05C80 (60C05 82B41)},
      series = {Wiley-Intersci. Ser. Discrete Math. Optim.},
      isbn = {0-471-17541-2},
      address = {New York},
      publisher = {John Wiley \& Sons},
      doi = {10.1002/9781118032718},
      zblnumber = {0968.05003},
      mrnumber = {1782847},
      mrreviewer = {Mark R. Jerrum},
      title = {Random Graphs},
      pages = {xii+333},
      YEAR={2000},
      }
  • [KoSaSz] Go to document J. Komlós, G. N. Sárközy, and E. Szemerédi, "Blow-up lemma," Combinatorica, vol. 17, iss. 1, pp. 109-123, 1997.
    @ARTICLE{KoSaSz, mrkey = {1466579},
      number = {1},
      issn = {0209-9683},
      author = {Koml{ó}s, J{á}nos and S{á}rk{ö}zy, G{á}bor N. and Szemer{é}di, Endre},
      mrclass = {05C35},
      doi = {10.1007/BF01196135},
      journal = {Combinatorica},
      zblnumber = {0880.05049},
      volume = {17},
      mrnumber = {1466579},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      mrreviewer = {Lane Clark},
      title = {Blow-up lemma},
      year = {1997},
      pages = {109--123},
      }
  • [KoRo01] Go to document A. V. Kostochka and V. Rödl, "On graphs with small Ramsey numbers," J. Graph Theory, vol. 37, iss. 4, pp. 198-204, 2001.
    @ARTICLE{KoRo01, mrkey = {1834850},
      number = {4},
      issn = {0364-9024},
      author = {Kostochka, A. V. and R{ö}dl, V.},
      mrclass = {05C55},
      doi = {10.1002/jgt.1014},
      journal = {J. Graph Theory},
      zblnumber = {0994.05094},
      volume = {37},
      mrnumber = {1834850},
      fjournal = {Journal of Graph Theory},
      mrreviewer = {R. H. Schelp},
      coden = {JGTHDO},
      title = {On graphs with small {R}amsey numbers},
      year = {2001},
      pages = {198--204},
      }
  • [KoRo04] Go to document A. V. Kostochka and V. Rödl, "On graphs with small Ramsey numbers. II," Combinatorica, vol. 24, iss. 3, pp. 389-401, 2004.
    @ARTICLE{KoRo04, mrkey = {2085363},
      number = {3},
      issn = {0209-9683},
      author = {Kostochka, A. V. and R{ö}dl, V.},
      mrclass = {05C55 (05C35)},
      doi = {10.1007/s00493-004-0024-9},
      journal = {Combinatorica},
      zblnumber = {1063.05101},
      volume = {24},
      mrnumber = {2085363},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      mrreviewer = {R. H. Schelp},
      title = {On graphs with small {R}amsey numbers. {II}},
      year = {2004},
      pages = {389--401},
      }
  • [KoSu] A. Kostochka and B. Sudakov, "On Ramsey numbers of sparse graphs," Combin. Probab. Comput., vol. 12, iss. 5-6, pp. 627-641, 2003.
    @ARTICLE{KoSu, mrkey = {2037075},
      number = {5-6},
      issn = {0963-5483},
      author = {Kostochka, Alexandr and Sudakov, Benny},
      mrclass = {05C55},
      journal = {Combin. Probab. Comput.},
      zblnumber = {1062.05099},
      volume = {12},
      mrnumber = {2037075},
      fjournal = {Combinatorics, Probability and Computing},
      mrreviewer = {R. H. Schelp},
      title = {On {R}amsey numbers of sparse graphs},
      year = {2003},
      pages = {627--641},
      }
  • [Lee] C. Lee, Embedding degenerate graphs of small bandwidth, 2015.
    @MISC{Lee,
      author = {Lee, C},
      arxiv = {1501.05350},
      title = {Embedding degenerate graphs of small bandwidth},
      year = {2015},
      }
  • [Lee2] C. Lee, A transference principle for Ramsey numbers of bounded degree graphs, 2015.
    @MISC{Lee2,
      author = {Lee, C},
      arxiv = {1504.06285},
      title = {A transference principle for {R}amsey numbers of bounded degree graphs},
      year = {2015},
      }
  • [McDiarmid] Go to document C. McDiarmid, "Concentration," in Probabilistic Methods for Algorithmic Discrete Mathematics, New York: Springer-Verlag, 1998, vol. 16, pp. 195-248.
    @INCOLLECTION{McDiarmid, mrkey = {1678578},
      author = {McDiarmid, Colin},
      mrclass = {60E15 (68R01)},
      series = {Algorithms Combin.},
      address = {New York},
      publisher = {Springer-Verlag},
      doi = {10.1007/978-3-662-12788-9_6},
      zblnumber = {0927.60027},
      volume = {16},
      mrnumber = {1678578},
      booktitle = {Probabilistic Methods for Algorithmic Discrete Mathematics},
      mrreviewer = {G. Schechtman},
      title = {Concentration},
      pages = {195--248},
      year = {1998},
      }
  • [Ramsey] Go to document F. P. Ramsey, "On a Problem of Formal Logic," Proc. London Math. Soc., vol. S2-30, iss. 1, p. 264, 1928.
    @ARTICLE{Ramsey, mrkey = {1576401},
      number = {1},
      issn = {0024-6115},
      author = {Ramsey, F. P.},
      mrclass = {Contributed Item},
      doi = {10.1112/plms/s2-30.1.264},
      journal = {Proc. London Math. Soc.},
      zblnumber = {55.0032.04},
      volume = {S2-30},
      mrnumber = {1576401},
      fjournal = {Proceedings of the London Mathematical Society},
      title = {On a {P}roblem of {F}ormal {L}ogic},
      pages = {264},
      YEAR={1928},
      }
  • [RoTh] Go to document V. Rödl and R. Thomas, "Arrangeability and clique subdivisions," in The Mathematics of Paul Erdős, II, New York: Springer-Verlag, 1997, vol. 14, pp. 236-239.
    @INCOLLECTION{RoTh, mrkey = {1425217},
      author = {R{ö}dl, Vojt{ě}ch and Thomas, Robin},
      mrclass = {05C55 (05C15)},
      series = {Algorithms Combin.},
      address = {New York},
      publisher = {Springer-Verlag},
      doi = {10.1007/978-3-642-60406-5_20},
      zblnumber = {0864.05073},
      volume = {14},
      mrnumber = {1425217},
      booktitle = {The Mathematics of {P}aul {E}rdős, {II}},
      mrreviewer = {R. H. Schelp},
      title = {Arrangeability and clique subdivisions},
      pages = {236--239},
      year = {1997},
      }
  • [Spencer] Go to document J. Spencer, "Ramsey’s theorem—a new lower bound," J. Combinatorial Theory Ser. A, vol. 18, pp. 108-115, 1975.
    @ARTICLE{Spencer, mrkey = {0366726},
      author = {Spencer, Joel},
      mrclass = {05C15},
      journal = {J. Combinatorial Theory Ser. A},
      zblnumber = {0296.05003},
      volume = {18},
      mrnumber = {0366726},
      fjournal = {Journal of Combinatorial Theory. Series A},
      mrreviewer = {R. L. Graham},
      title = {Ramsey's theorem---a new lower bound},
      year = {1975},
      pages = {108--115},
      doi = {10.1016/0097-3165(75)90071-0},
     }
  • [Sudakov] Go to document B. Sudakov, "A conjecture of Erdős on graph Ramsey numbers," Adv. Math., vol. 227, iss. 1, pp. 601-609, 2011.
    @ARTICLE{Sudakov, mrkey = {2782204},
      number = {1},
      issn = {0001-8708},
      author = {Sudakov, Benny},
      mrclass = {05C55 (05D10)},
      doi = {10.1016/j.aim.2011.02.004},
      journal = {Adv. Math.},
      zblnumber = {1213.05178},
      volume = {227},
      mrnumber = {2782204},
      fjournal = {Advances in Mathematics},
      mrreviewer = {Stanis{\l}aw P. Radziszowski},
      coden = {ADMTA4},
      title = {A conjecture of {E}rdős on graph {R}amsey numbers},
      year = {2011},
      pages = {601--609},
      }
  • [Szemeredi] E. Szemerédi, "On sets of integers containing no $k$ elements in arithmetic progression," Acta Arith., vol. 27, pp. 199-245, 1975.
    @ARTICLE{Szemeredi, mrkey = {0369312},
      issn = {0065-1036},
      author = {Szemer{é}di, E.},
      mrclass = {10L10},
      zblnumber = {0303.10056},
      volume = {27},
      mrnumber = {0369312},
      journal={Acta Arith.},
      fjournal = {Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica},
      mrreviewer = {S. L. G. Choi},
      title = {On sets of integers containing no {$k$} elements in arithmetic progression},
      year = {1975},
      pages = {199--245},
      }
  • [vdw] B. Van der Waerden, "Beweis einer baudetschen vermutung," Nieuw Arch. Wisk, vol. 15, pp. 212-216, 1927.
    @ARTICLE{vdw, zblnumber = {53.0073.12},
      volume = {15},
      author = {Van der Waerden, B.},
      title = {Beweis einer baudetschen vermutung},
      pages = {212--216},
      year = {1927},
      journal = {Nieuw Arch. Wisk},
      }

Keywords
, ,
Mathematical Subject Classification
Primary: , ,
DOI
https://doi.org/10.4007/annals.2017.185.3.2
MR
3664811
zbMATH
1365.05193
Milestones
Received: 25 May 2015
Revised: 21 November 2016
Accepted: 28 November 2016
Published online: 12 April 2017

Authors

Choongbum Lee

Massachusetts Institute of Technology, Cambridge, MA