Combinatorial theorems in sparse random sets

Abstract

We develop a new technique that allows us to show in a unified way that many well-known combinatorial theorems, including Turán’s theorem, Szemerédi’s theorem and Ramsey’s theorem, hold almost surely inside sparse random sets. For instance, we extend Turán’s theorem to the random setting by showing that for every $\epsilon > 0$ and every positive integer $t \geq 3$ there exists a constant $C$ such that, if $G$ is a random graph on $n$ vertices where each edge is chosen independently with probability at least $C n^{-2/(t+1)}$, then, with probability tending to 1 as $n$ tends to infinity, every subgraph of $G$ with at least $\left(1 – \frac{1}{t-1} + \epsilon\right) e(G)$ edges contains a copy of $K_t$. This is sharp up to the constant $C$. We also show how to prove sparse analogues of structural results, giving two main applications, a stability version of the random Turán theorem stated above and a sparse hypergraph removal lemma. Many similar results have recently been obtained independently in a different way by Schacht and by Friedgut, Rödl and Schacht.

Note: To view the article, click on the URL link for the DOI number.

  • [BMS14] Go to document J. Balogh, R. Morris, and W. Samotij, "Independent sets in hypergraphs," J. Amer. Math. Soc., vol. 28, iss. 3, pp. 669-709, 2015.
    @ARTICLE{BMS14, mrkey = {3327533},
      number = {3},
      issn = {0894-0347},
      author = {Balogh, J{ó}zsef and Morris, Robert and Samotij, Wojciech},
      mrclass = {05C65 (05D40)},
      doi = {10.1090/S0894-0347-2014-00816-X},
      journal = {J. Amer. Math. Soc.},
      volume = {28},
      mrnumber = {3327533},
      fjournal = {Journal of the American Mathematical Society},
      mrreviewer = {Vladimir D. Samodivkin},
      title = {Independent sets in hypergraphs},
      year = {2015},
      pages = {669--709},
      zblnumber = {1310.05154},
      }
  • [BL96] Go to document V. Bergelson and A. Leibman, "Polynomial extensions of van der Waerden’s and Szemerédi’s theorems," J. Amer. Math. Soc., vol. 9, iss. 3, pp. 725-753, 1996.
    @ARTICLE{BL96, mrkey = {1325795},
      number = {3},
      issn = {0894-0347},
      author = {Bergelson, V. and Leibman, A.},
      mrclass = {11B25 (05D10 28D05 54H20)},
      doi = {10.1090/S0894-0347-96-00194-4},
      journal = {J. Amer. Math. Soc.},
      volume = {9},
      mrnumber = {1325795},
      fjournal = {Journal of the American Mathematical Society},
      mrreviewer = {Pierre Michel},
      title = {Polynomial extensions of van der {W}aerden's and {S}zemerédi's theorems},
      year = {1996},
      pages = {725--753},
      zblnumber = {0870.11015},
      }
  • [B78] B. Bollobás, Extremal Graph Theory, Mineola, NY: Dover Publications, 2004.
    @BOOK{B78, mrkey = {2078877},
      author = {Bollob{á}s, B{é}la},
      mrclass = {05C35 (05-02)},
      isbn = {0-486-43596-2},
      address = {Mineola, NY},
      publisher = {Dover Publications},
      mrnumber = {2078877},
      note = {reprint of the 1978 original},
      title = {Extremal Graph Theory},
      year = {2004},
      pages = {xx+488},
      zblnumber = {1099.05044},
      }
  • [DCF00] Go to document D. De Caen and Z. Füredi, "The maximum size of 3-uniform hypergraphs not containing a Fano plane," J. Combin. Theory Ser. B, vol. 78, iss. 2, pp. 274-276, 2000.
    @ARTICLE{DCF00, mrkey = {1750899},
      number = {2},
      issn = {0095-8956},
      author = {De Caen, Dominique and F{ü}redi, Zolt{á}n},
      mrclass = {05C65 (05B25)},
      doi = {10.1006/jctb.1999.1938},
      journal = {J. Combin. Theory Ser. B},
      volume = {78},
      mrnumber = {1750899},
      fjournal = {Journal of Combinatorial Theory. Series B},
      title = {The maximum size of 3-uniform hypergraphs not containing a {F}ano plane},
      year = {2000},
      pages = {274--276},
      zblnumber = {1027.05073},
      }
  • [C14] Go to document D. Conlon, "Combinatorial theorems relative to a random set," in Proceedings of the International Congress of Mathematicians 2014, Vol. 4, , pp. 303-328.
    @incollection{C14,
      author = {Conlon, D.},
      booktitle={Proceedings of the International Congress of Mathematicians 2014, Vol. 4},
      title = {Combinatorial theorems relative to a random set},
      pages={303--328},
      url={http://www.icm2014.org/download/Proceedings_Volume_IV.pdf},
     }
  • [CGSS14] Go to document D. Conlon, W. T. Gowers, W. Samotij, and M. Schacht, "On the KŁR conjecture in random graphs," Israel J. Math., vol. 203, iss. 1, pp. 535-580, 2014.
    @ARTICLE{CGSS14, mrkey = {3273450},
      number = {1},
      issn = {0021-2172},
      author = {Conlon, D. and Gowers, W. T. and Samotij, W. and Schacht, M.},
      mrclass = {05C80},
      doi = {10.1007/s11856-014-1120-1},
      journal = {Israel J. Math.},
      volume = {203},
      mrnumber = {3273450},
      fjournal = {Israel Journal of Mathematics},
      title = {On the {K}{{\L}}{R} conjecture in random graphs},
      year = {2014},
      pages = {535--580},
      zblnumber = {1303.05175},
      }
  • [E62] P. ErdHos, "On the number of complete subgraphs contained in certain graphs," Magyar Tud. Akad. Mat. Kutató Int. Közl., vol. 7, pp. 459-464, 1962.
    @ARTICLE{E62, mrkey = {0151956},
      volume = {7},
      mrnumber = {0151956},
      author = {Erd{ő}s, P.},
      mrclass = {55.10 (05.65)},
      mrreviewer = {J. W. Moon},
      title = {On the number of complete subgraphs contained in certain graphs},
      pages = {459--464},
      year = {1962},
      journal = {Magyar Tud. Akad. Mat. Kutató Int. Közl.},
      zblnumber = {0116.01202},
      }
  • [ES83] Go to document P. ErdHos and M. Simonovits, "Supersaturated graphs and hypergraphs," Combinatorica, vol. 3, iss. 2, pp. 181-192, 1983.
    @ARTICLE{ES83, mrkey = {0726456},
      number = {2},
      issn = {0209-9683},
      author = {Erd{ő}s, Paul and Simonovits, Mikl{ó}s},
      mrclass = {05C55 (05C65)},
      doi = {10.1007/BF02579292},
      journal = {Combinatorica},
      volume = {3},
      mrnumber = {0726456},
      fjournal = {Combinatorica. An International Journal of the János Bolyai Mathematical Society},
      mrreviewer = {E. Rodney Canfield},
      coden = {COMBDI},
      title = {Supersaturated graphs and hypergraphs},
      year = {1983},
      pages = {181--192},
      zblnumber = {0529.05027},
      }
  • [FR86] Go to document P. Frankl and V. Rödl, "Large triangle-free subgraphs in graphs without $K_4$," Graphs Combin., vol. 2, iss. 2, pp. 135-144, 1986.
    @ARTICLE{FR86, mrkey = {0932121},
      number = {2},
      issn = {0911-0119},
      author = {Frankl, P. and R{ö}dl, V.},
      mrclass = {05C55},
      doi = {10.1007/BF01788087},
      journal = {Graphs Combin.},
      volume = {2},
      mrnumber = {0932121},
      fjournal = {Graphs and Combinatorics},
      mrreviewer = {J. Spencer},
      coden = {GRCOE5},
      title = {Large triangle-free subgraphs in graphs without {$K\sb 4$}},
      year = {1986},
      pages = {135--144},
      zblnumber = {0596.05037},
      }
  • [F99] Go to document E. Friedgut, "Sharp thresholds of graph properties, and the $k$-SAT problem," J. Amer. Math. Soc., vol. 12, iss. 4, pp. 1017-1054, 1999.
    @ARTICLE{F99, mrkey = {1678031},
      number = {4},
      issn = {0894-0347},
      author = {Friedgut, Ehud},
      mrclass = {05C80 (42C10)},
      doi = {10.1090/S0894-0347-99-00305-7},
      journal = {J. Amer. Math. Soc.},
      volume = {12},
      mrnumber = {1678031},
      fjournal = {Journal of the American Mathematical Society},
      mrreviewer = {Mark R. Jerrum},
      title = {Sharp thresholds of graph properties, and the {$k$}-{S}{A}{T} problem},
      year = {1999},
      pages = {1017--1054},
      zblnumber = {0932.05084},
      }
  • [FRRT06] Go to document E. Friedgut, V. Rödl, A. Ruciński, and P. Tetali, "A sharp threshold for random graphs with a monochromatic triangle in every edge coloring," Mem. Amer. Math. Soc., vol. 179, iss. 845, p. vi, 2006.
    @ARTICLE{FRRT06, mrkey = {2183532},
      number = {845},
      issn = {0065-9266},
      author = {Friedgut, Ehud and R{ö}dl, Vojtech and Ruci{ń}ski, Andrzej and Tetali, Prasad},
      mrclass = {05C80 (05-02 05C55)},
      doi = {10.1090/memo/0845},
      journal = {Mem. Amer. Math. Soc.},
      volume = {179},
      mrnumber = {2183532},
      fjournal = {Memoirs of the American Mathematical Society},
      mrreviewer = {A. G. Thomason},
      coden = {MAMCAU},
      title = {A sharp threshold for random graphs with a monochromatic triangle in every edge coloring},
      year = {2006},
      pages = {vi+66},
      zblnumber = {1087.05052},
      }
  • [FRS09] Go to document E. Friedgut, V. Rödl, and M. Schacht, "Ramsey properties of random discrete structures," Random Structures Algorithms, vol. 37, iss. 4, pp. 407-436, 2010.
    @ARTICLE{FRS09, mrkey = {2760356},
      number = {4},
      issn = {1042-9832},
      author = {Friedgut, Ehud and R{ö}dl, Vojt{ě}ch and Schacht, Mathias},
      mrclass = {05C80 (05D10 05D40 60C05)},
      doi = {10.1002/rsa.20352},
      journal = {Random Structures Algorithms},
      volume = {37},
      mrnumber = {2760356},
      fjournal = {Random Structures \& Algorithms},
      mrreviewer = {Dmitry A. Shabanov},
      title = {Ramsey properties of random discrete structures},
      year = {2010},
      pages = {407--436},
      zblnumber = {1228.05284},
      }
  • [F94] Go to document Z. Füredi, "Random Ramsey graphs for the four-cycle," Discrete Math., vol. 126, iss. 1-3, pp. 407-410, 1994.
    @ARTICLE{F94, mrkey = {1264510},
      number = {1-3},
      issn = {0012-365X},
      author = {F{ü}redi, Zolt{á}n},
      mrclass = {05C55 (05C35)},
      doi = {10.1016/0012-365X(94)90287-9},
      journal = {Discrete Math.},
      volume = {126},
      mrnumber = {1264510},
      fjournal = {Discrete Mathematics},
      mrreviewer = {Ralph Faudree},
      coden = {DSMHA4},
      title = {Random {R}amsey graphs for the four-cycle},
      year = {1994},
      pages = {407--410},
      zblnumber = {0792.05128},
      }
  • [FS05] Go to document Z. Füredi and M. Simonovits, "Triple systems not containing a Fano configuration," Combin. Probab. Comput., vol. 14, iss. 4, pp. 467-484, 2005.
    @ARTICLE{FS05, mrkey = {2160414},
      number = {4},
      issn = {0963-5483},
      author = {F{ü}redi, Zolt{á}n and Simonovits, Mikl{ó}s},
      mrclass = {05B07 (05C65)},
      doi = {10.1017/S0963548305006784},
      journal = {Combin. Probab. Comput.},
      volume = {14},
      mrnumber = {2160414},
      fjournal = {Combinatorics, Probability and Computing},
      mrreviewer = {Yi Zhao},
      title = {Triple systems not containing a {F}ano configuration},
      year = {2005},
      pages = {467--484},
      zblnumber = {1075.05062},
      }
  • [FK78] Go to document H. Furstenberg and Y. Katznelson, "An ergodic Szemerédi theorem for commuting transformations," J. Analyse Math., vol. 34, pp. 275-291 (1979), 1978.
    @ARTICLE{FK78, mrkey = {0531279},
      issn = {0021-7670},
      author = {Furstenberg, H. and Katznelson, Y.},
      mrclass = {28D05 (10K50 10L02 10L20)},
      doi = {10.1007/BF02790016},
      journal = {J. Analyse Math.},
      volume = {34},
      mrnumber = {0531279},
      fjournal = {Journal d'Analyse Mathématique},
      mrreviewer = {J. H. B. Kemperman},
      coden = {JOAMAV},
      title = {An ergodic {S}zemerédi theorem for commuting transformations},
      year = {1978},
      pages = {275--291 (1979)},
      zblnumber = {0426.28014},
      }
  • [GKRS07] Go to document S. Gerke, Y. Kohayakawa, V. Rödl, and A. Steger, "Small subsets inherit sparse $\epsilon$-regularity," J. Combin. Theory Ser. B, vol. 97, iss. 1, pp. 34-56, 2007.
    @ARTICLE{GKRS07, mrkey = {2278123},
      number = {1},
      issn = {0095-8956},
      author = {Gerke, Stefanie and Kohayakawa, Yoshiharu and R{ö}dl, Vojt{ě}ch and Steger, Angelika},
      mrclass = {05C35},
      doi = {10.1016/j.jctb.2006.03.004},
      journal = {J. Combin. Theory Ser. B},
      volume = {97},
      mrnumber = {2278123},
      fjournal = {Journal of Combinatorial Theory. Series B},
      mrreviewer = {G{á}bor N. S{á}rk{ö}zy},
      coden = {JCBTB8},
      title = {Small subsets inherit sparse {$\epsilon$}-regularity},
      year = {2007},
      pages = {34--56},
      zblnumber = {1111.05090},
      }
  • [GPSST07] Go to document S. Gerke, H. J. Prömel, T. Schickinger, A. Steger, and A. Taraz, "$K_4$-free subgraphs of random graphs revisited," Combinatorica, vol. 27, iss. 3, pp. 329-365, 2007.
    @ARTICLE{GPSST07, mrkey = {2345813},
      number = {3},
      issn = {0209-9683},
      author = {Gerke, S. and Pr{ö}mel, H. J. and Schickinger, T. and Steger, A. and Taraz, A.},
      mrclass = {05C80 (05C35)},
      doi = {10.1007/s00493-007-2010-5},
      journal = {Combinatorica},
      volume = {27},
      mrnumber = {2345813},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      mrreviewer = {Yoshiharu Kohayakawa},
      title = {{$K\sb 4$}-free subgraphs of random graphs revisited},
      year = {2007},
      pages = {329--365},
      zblnumber = {1136.05067},
      }
  • [GSS04] Go to document S. Gerke, T. Schickinger, and A. Steger, "$K_5$-free subgraphs of random graphs," Random Structures Algorithms, vol. 24, iss. 2, pp. 194-232, 2004.
    @ARTICLE{GSS04, mrkey = {2035876},
      number = {2},
      issn = {1042-9832},
      author = {Gerke, S. and Schickinger, T. and Steger, A.},
      mrclass = {05C80 (60C05)},
      doi = {10.1002/rsa.20000},
      journal = {Random Structures Algorithms},
      volume = {24},
      mrnumber = {2035876},
      fjournal = {Random Structures \& Algorithms},
      mrreviewer = {Michael Krivelevich},
      title = {{$K\sb 5$}-free subgraphs of random graphs},
      year = {2004},
      pages = {194--232},
      zblnumber = {1035.05084},
      }
  • [G01] Go to document W. T. Gowers, "A new proof of Szemerédi’s theorem," Geom. Funct. Anal., vol. 11, iss. 3, pp. 465-588, 2001.
    @ARTICLE{G01, mrkey = {1844079},
      number = {3},
      issn = {1016-443X},
      author = {Gowers, W. T.},
      mrclass = {11B25 (11K38 11K45)},
      doi = {10.1007/s00039-001-0332-9},
      journal = {Geom. Funct. Anal.},
      volume = {11},
      mrnumber = {1844079},
      fjournal = {Geometric and Functional Analysis},
      mrreviewer = {Hillel Furstenberg},
      coden = {GFANFB},
      title = {A new proof of {S}zemerédi's theorem},
      year = {2001},
      pages = {465--588},
      zblnumber = {1028.11005},
      }
  • [G06] Go to document W. T. Gowers, "Quasirandomness, counting and regularity for 3-uniform hypergraphs," Combin. Probab. Comput., vol. 15, iss. 1-2, pp. 143-184, 2006.
    @ARTICLE{G06, mrkey = {2195580},
      number = {1-2},
      issn = {0963-5483},
      author = {Gowers, W. T.},
      mrclass = {05D05 (05C35 05C65)},
      doi = {10.1017/S0963548305007236},
      journal = {Combin. Probab. Comput.},
      volume = {15},
      mrnumber = {2195580},
      fjournal = {Combinatorics, Probability and Computing},
      mrreviewer = {J{ó}zsef Solymosi},
      title = {Quasirandomness, counting and regularity for 3-uniform hypergraphs},
      year = {2006},
      pages = {143--184},
      zblnumber = {1082.05081},
      }
  • [G07] Go to document W. T. Gowers, "Hypergraph regularity and the multidimensional Szemerédi theorem," Ann. of Math., vol. 166, iss. 3, pp. 897-946, 2007.
    @ARTICLE{G07, mrkey = {2373376},
      number = {3},
      issn = {0003-486X},
      author = {Gowers, W. T.},
      mrclass = {05D10 (05C30 05C35 05C55 05C80 28D15)},
      doi = {10.4007/annals.2007.166.897},
      journal = {Ann. of Math.},
      volume = {166},
      mrnumber = {2373376},
      fjournal = {Annals of Mathematics. Second Series},
      mrreviewer = {G{á}bor N. S{á}rk{ö}zy},
      coden = {ANMAAH},
      title = {Hypergraph regularity and the multidimensional {S}zemerédi theorem},
      year = {2007},
      pages = {897--946},
      zblnumber = {1159.05052},
      }
  • [G08] Go to document W. T. Gowers, "Decompositions, approximate structure, transference, and the Hahn-Banach theorem," Bull. Lond. Math. Soc., vol. 42, iss. 4, pp. 573-606, 2010.
    @ARTICLE{G08, mrkey = {2669681},
      number = {4},
      issn = {0024-6093},
      author = {Gowers, W. T.},
      mrclass = {11B30 (05D99 11P32)},
      doi = {10.1112/blms/bdq018},
      journal = {Bull. Lond. Math. Soc.},
      volume = {42},
      mrnumber = {2669681},
      fjournal = {Bulletin of the London Mathematical Society},
      mrreviewer = {Julia Wolf},
      title = {Decompositions, approximate structure, transference, and the {H}ahn-{B}anach theorem},
      year = {2010},
      pages = {573--606},
      zblnumber = {1233.05198},
      }
  • [GRR96] Go to document R. Graham, V. Rödl, and A. Ruciński, "On Schur properties of random subsets of integers," J. Number Theory, vol. 61, iss. 2, pp. 388-408, 1996.
    @ARTICLE{GRR96, mrkey = {1423060},
      number = {2},
      issn = {0022-314X},
      author = {Graham, Ronald and R{ö}dl, Vojtech and Ruci{ń}ski, Andrzej},
      mrclass = {05A18 (11K99)},
      doi = {10.1006/jnth.1996.0155},
      journal = {J. Number Theory},
      volume = {61},
      mrnumber = {1423060},
      fjournal = {Journal of Number Theory},
      mrreviewer = {Colin J. H. McDiarmid},
      coden = {JNUTA9},
      title = {On {S}chur properties of random subsets of integers},
      year = {1996},
      pages = {388--408},
      zblnumber = {0880.05081},
      }
  • [GT08] Go to document B. Green and T. Tao, "The primes contain arbitrarily long arithmetic progressions," Ann. of Math., vol. 167, iss. 2, pp. 481-547, 2008.
    @ARTICLE{GT08, mrkey = {2415379},
      number = {2},
      issn = {0003-486X},
      author = {Green, Ben and Tao, Terence},
      mrclass = {11N13 (11A41 11B25 37A45)},
      doi = {10.4007/annals.2008.167.481},
      journal = {Ann. of Math.},
      volume = {167},
      mrnumber = {2415379},
      fjournal = {Annals of Mathematics. Second Series},
      mrreviewer = {Tamar Ziegler},
      coden = {ANMAAH},
      title = {The primes contain arbitrarily long arithmetic progressions},
      year = {2008},
      pages = {481--547},
      zblnumber = {1191.11025},
      }
  • [HL08] M. Hamel and I. Łaba, "Arithmetic structures in random sets," Integers, vol. 8, p. 04, 2008.
    @ARTICLE{HL08, mrkey = {2373088},
      issn = {1867-0652},
      author = {Hamel, Mariah and {\L}aba, Izabella},
      mrclass = {11B75 (11B25)},
      journal = {Integers},
      volume = {8},
      mrnumber = {2373088},
      fjournal = {Integers. Electronic Journal of Combinatorial Number Theory},
      mrreviewer = {Mei Chu Chang},
      title = {Arithmetic structures in random sets},
      year = {2008},
      pages = {A04, 21},
      zblnumber = {1195.11037},
      }
  • [HKL95] Go to document P. E. Haxell, Y. Kohayakawa, and T. Łuczak, "Turán’s extremal problem in random graphs: forbidding even cycles," J. Combin. Theory Ser. B, vol. 64, iss. 2, pp. 273-287, 1995.
    @ARTICLE{HKL95, mrkey = {1339852},
      number = {2},
      issn = {0095-8956},
      author = {Haxell, P. E. and Kohayakawa, Y. and {\L}uczak, T.},
      mrclass = {05C80 (60C05)},
      doi = {10.1006/jctb.1995.1035},
      journal = {J. Combin. Theory Ser. B},
      volume = {64},
      mrnumber = {1339852},
      fjournal = {Journal of Combinatorial Theory. Series B},
      mrreviewer = {Lyuben R. Mutafchiev},
      coden = {JCBTB8},
      title = {Turán's extremal problem in random graphs: forbidding even cycles},
      year = {1995},
      pages = {273--287},
      zblnumber = {0828.05056},
      }
  • [HKL96] Go to document P. E. Haxell, Y. Kohayakawa, and T. Łuczak, "Turán’s extremal problem in random graphs: forbidding odd cycles," Combinatorica, vol. 16, iss. 1, pp. 107-122, 1996.
    @ARTICLE{HKL96, mrkey = {1394514},
      number = {1},
      issn = {0209-9683},
      author = {Haxell, P. E. and Kohayakawa, Y. and {\L}uczak, T.},
      mrclass = {05C80 (05C35 05C38)},
      doi = {10.1007/BF01300129},
      journal = {Combinatorica},
      volume = {16},
      mrnumber = {1394514},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      mrreviewer = {Lyuben R. Mutafchiev},
      coden = {COMBDI},
      title = {Turán's extremal problem in random graphs: forbidding odd cycles},
      year = {1996},
      pages = {107--122},
      zblnumber = {0853.05072},
      }
  • [J90] Go to document S. Janson, "Poisson approximation for large deviations," Random Structures Algorithms, vol. 1, iss. 2, pp. 221-229, 1990.
    @ARTICLE{J90, mrkey = {1138428},
      number = {2},
      issn = {1042-9832},
      author = {Janson, Svante},
      mrclass = {60F10 (05C80 60C05)},
      doi = {10.1002/rsa.3240010209},
      journal = {Random Structures Algorithms},
      volume = {1},
      mrnumber = {1138428},
      fjournal = {Random Structures \& Algorithms},
      mrreviewer = {Andrew D. Barbour},
      title = {Poisson approximation for large deviations},
      year = {1990},
      pages = {221--229},
      zblnumber = {0747.05079},
      }
  • [JOR04] Go to document S. Janson, K. Oleszkiewicz, and A. Ruciński, "Upper tails for subgraph counts in random graphs," Israel J. Math., vol. 142, pp. 61-92, 2004.
    @ARTICLE{JOR04, mrkey = {2085711},
      issn = {0021-2172},
      author = {Janson, Svante and Oleszkiewicz, Krzysztof and Ruci{ń}ski, Andrzej},
      mrclass = {05C80},
      doi = {10.1007/BF02771528},
      journal = {Israel J. Math.},
      volume = {142},
      mrnumber = {2085711},
      fjournal = {Israel Journal of Mathematics},
      mrreviewer = {David B. Penman},
      coden = {ISJMAP},
      title = {Upper tails for subgraph counts in random graphs},
      year = {2004},
      pages = {61--92},
      zblnumber = {1055.05136},
      }
  • [JR02] Go to document S. Janson and A. Ruciński, "The infamous upper tail," Random Structures Algorithms, vol. 20, iss. 3, pp. 317-342, 2002.
    @ARTICLE{JR02, mrkey = {1900611},
      number = {3},
      issn = {1042-9832},
      author = {Janson, Svante and Ruci{ń}ski, Andrzej},
      mrclass = {60C05 (90C27)},
      doi = {10.1002/rsa.10031},
      journal = {Random Structures Algorithms},
      volume = {20},
      mrnumber = {1900611},
      fjournal = {Random Structures \& Algorithms},
      title = {The infamous upper tail},
      year = {2002},
      pages = {317--342},
      zblnumber = {0996.60023},
      }
  • [JR04] Go to document S. Janson and A. Ruciński, "The deletion method for upper tail estimates," Combinatorica, vol. 24, iss. 4, pp. 615-640, 2004.
    @ARTICLE{JR04, mrkey = {2096818},
      number = {4},
      issn = {0209-9683},
      author = {Janson, Svante and Ruci{ń}ski, Andrzej},
      mrclass = {60C05 (05C80 60F05)},
      doi = {10.1007/s00493-004-0038-3},
      journal = {Combinatorica},
      volume = {24},
      mrnumber = {2096818},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      mrreviewer = {Dudley Stark},
      title = {The deletion method for upper tail estimates},
      year = {2004},
      pages = {615--640},
      zblnumber = {1074.60006},
      }
  • [JR09] Go to document S. Janson and A. Ruciński, "Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs," Ark. Mat., vol. 49, iss. 1, pp. 79-96, 2011.
    @ARTICLE{JR09, mrkey = {2784258},
      number = {1},
      issn = {0004-2080},
      author = {Janson, Svante and Ruci{ń}ski, Andrzej},
      mrclass = {05C80 (05C20 05C65 05D40 60C05)},
      doi = {10.1007/s11512-009-0117-1},
      journal = {Ark. Mat.},
      volume = {49},
      mrnumber = {2784258},
      fjournal = {Arkiv för Matematik},
      mrreviewer = {David B. Penman},
      coden = {AKMTAJ},
      title = {Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs},
      year = {2011},
      pages = {79--96},
      zblnumber = {1223.05201},
      }
  • [KS05] Go to document P. Keevash and B. Sudakov, "The Turán number of the Fano plane," Combinatorica, vol. 25, iss. 5, pp. 561-574, 2005.
    @ARTICLE{KS05, mrkey = {2176425},
      number = {5},
      issn = {0209-9683},
      author = {Keevash, Peter and Sudakov, Benny},
      mrclass = {05C35},
      doi = {10.1007/s00493-005-0034-2},
      journal = {Combinatorica},
      volume = {25},
      mrnumber = {2176425},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      mrreviewer = {Yi Zhao},
      title = {The {T}urán number of the {F}ano plane},
      year = {2005},
      pages = {561--574},
      zblnumber = {1089.05074},
      }
  • [K97] Y. Kohayakawa, "Szemerédi’s regularity lemma for sparse graphs," in Foundations of Computational Mathematics, New York: Springer-Verlag, 1997, pp. 216-230.
    @INCOLLECTION{K97, mrkey = {1661982},
      author = {Kohayakawa, Yoshiharu},
      mrclass = {05C70 (05C80)},
      address = {New York},
      publisher = {Springer-Verlag},
      mrnumber = {1661982},
      booktitle = {Foundations of Computational Mathematics},
      venue = {{R}io de {J}aneiro, 1997},
      title = {Szemerédi's regularity lemma for sparse graphs},
      pages = {216--230},
      year = {1997},
      zblnumber = {0868.05042},
      }
  • [KLR96] Y. Kohayakawa, T. Łuczak, and V. Rödl, "Arithmetic progressions of length three in subsets of a random set," Acta Arith., vol. 75, iss. 2, pp. 133-163, 1996.
    @ARTICLE{KLR96, mrkey = {1379396},
      number = {2},
      issn = {0065-1036},
      author = {Kohayakawa, Yoshiharu and {\L}uczak, Tomasz and R{ö}dl, Vojt{ě}ch},
      mrclass = {11B25 (05C80 11K99 60D05)},
      journal = {Acta Arith.},
      volume = {75},
      mrnumber = {1379396},
      fjournal = {Acta Arithmetica},
      mrreviewer = {Colin J. H. McDiarmid},
      coden = {AARIA9},
      title = {Arithmetic progressions of length three in subsets of a random set},
      year = {1996},
      pages = {133--163},
      }
  • [KLR97] Go to document Y. Kohayakawa, T. Łuczak, and V. Rödl, "On $K^4$-free subgraphs of random graphs," Combinatorica, vol. 17, iss. 2, pp. 173-213, 1997.
    @ARTICLE{KLR97, mrkey = {1479298},
      number = {2},
      issn = {0209-9683},
      author = {Kohayakawa, Yoshiharu and {\L}uczak, Tomasz and R{ö}dl, Vojt{ě}ch},
      mrclass = {05C80 (05C35)},
      doi = {10.1007/BF01200906},
      journal = {Combinatorica},
      volume = {17},
      mrnumber = {1479298},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      mrreviewer = {Mark R. Jerrum},
      title = {On {$K\sp 4$}-free subgraphs of random graphs},
      year = {1997},
      pages = {173--213},
      zblnumber = {0889.05068},
      }
  • [KRS04] Go to document Y. Kohayakawa, V. Rödl, and M. Schacht, "The Turán theorem for random graphs," Combin. Probab. Comput., vol. 13, iss. 1, pp. 61-91, 2004.
    @ARTICLE{KRS04, mrkey = {2034303},
      number = {1},
      issn = {0963-5483},
      author = {Kohayakawa, Yoshiharu and R{ö}dl, Vojt{ě}ch and Schacht, Mathias},
      mrclass = {05C80 (05C35 60C05)},
      doi = {10.1017/S0963548303005856},
      journal = {Combin. Probab. Comput.},
      volume = {13},
      mrnumber = {2034303},
      fjournal = {Combinatorics, Probability and Computing},
      mrreviewer = {Ivan Pashov},
      title = {The {T}urán theorem for random graphs},
      year = {2004},
      pages = {61--91},
      zblnumber = {1048.05075},
      }
  • [L06] T. Łuczak, "Randomness and regularity," in International Congress of Mathematicians. Vol. III, Eur. Math. Soc., 2006, pp. 899-909.
    @INCOLLECTION{L06, mrkey = {2275711},
      author = {{\L}uczak, Tomasz},
      mrclass = {05C80 (05C35 05C65 05D05 05D40)},
      addres = {Zürich},
      publisher = {Eur. Math. Soc.},
      mrnumber = {2275711},
      booktitle = {International {C}ongress of {M}athematicians. {V}ol. {III}},
      mrreviewer = {Amites Sarkar},
      title = {Randomness and regularity},
      pages = {899--909},
      year = {2006},
      zblnumber = {1099.05073},
      }
  • [LRV92] Go to document T. Łuczak, A. Ruciński, and B. Voigt, "Ramsey properties of random graphs," J. Combin. Theory Ser. B, vol. 56, iss. 1, pp. 55-68, 1992.
    @ARTICLE{LRV92, mrkey = {1182457},
      number = {1},
      issn = {0095-8956},
      author = {{\L}uczak, Tomasz and Ruci{ń}ski, Andrzej and Voigt, Bernd},
      mrclass = {05C80 (05C55)},
      doi = {10.1016/0095-8956(92)90006-J},
      journal = {J. Combin. Theory Ser. B},
      volume = {56},
      mrnumber = {1182457},
      fjournal = {Journal of Combinatorial Theory. Series B},
      mrreviewer = {Alan M. Frieze},
      coden = {JCBTB8},
      title = {Ramsey properties of random graphs},
      year = {1992},
      pages = {55--68},
      zblnumber = {0711.05041},
      }
  • [NRS06] Go to document B. Nagle, V. Rödl, and M. Schacht, "The counting lemma for regular $k$-uniform hypergraphs," Random Structures Algorithms, vol. 28, iss. 2, pp. 113-179, 2006.
    @ARTICLE{NRS06, mrkey = {2198495},
      number = {2},
      issn = {1042-9832},
      author = {Nagle, Brendan and R{ö}dl, Vojt{ě}ch and Schacht, Mathias},
      mrclass = {05C35 (05C65)},
      doi = {10.1002/rsa.20117},
      journal = {Random Structures Algorithms},
      volume = {28},
      mrnumber = {2198495},
      fjournal = {Random Structures \& Algorithms},
      mrreviewer = {Jozef Skokan},
      title = {The counting lemma for regular {$k$}-uniform hypergraphs},
      year = {2006},
      pages = {113--179},
      zblnumber = {1093.05045},
      }
  • [N09] Go to document H. H. Nguyen, "On two-point configurations in a random set," Integers, vol. 9, p. a3, 41-45, 2009.
    @ARTICLE{N09, mrkey = {2506135},
      issn = {1867-0652},
      author = {Nguyen, Hoi H.},
      mrclass = {11B30},
      doi = {10.1515/INTEG.2009.004},
      journal = {Integers},
      volume = {9},
      mrnumber = {2506135},
      fjournal = {Integers. Electronic Journal of Combinatorial Number Theory},
      mrreviewer = {Jamie Simpson},
      title = {On two-point configurations in a random set},
      year = {2009},
      pages = {A3, 41--45},
      zblnumber = {1207.11021},
      }
  • [R41] Go to document R. Rado, "Note on combinatorial analysis," Proc. London Math. Soc., vol. 48, pp. 122-160, 1943.
    @ARTICLE{R41, mrkey = {0009007},
      issn = {0024-6115},
      author = {Rado, R.},
      mrclass = {09.0X},
      doi = {10.1112/plms/s2-48.1.122},
      journal = {Proc. London Math. Soc.},
      volume = {48},
      mrnumber = {0009007},
      fjournal = {Proceedings of the London Mathematical Society. Second Series},
      mrreviewer = {P. Erd{ö}s},
      title = {Note on combinatorial analysis},
      year = {1943},
      pages = {122--160},
      zblnumber = {0028.33801},
      }
  • [R30] Go to document F. P. Ramsey, "On a problem of formal logic," Proc. London Math. Soc., vol. S2-30, iss. 1, p. 264, 1929.
    @ARTICLE{R30, 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.},
      volume = {S2-30},
      mrnumber = {1576401},
      fjournal = {Proceedings of the London Mathematical Society},
      title = {On a problem of formal logic},
      pages = {264—286},
      year = {1929},
      jfmnumber = {55.0032.04},
      }
  • [RTTV08] O. Reingold, L. Trevisan, M. Tulsiani, and S. Vadhan, "Dense subsets of pseudorandom sets," in Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, Washington DC: IEEE Computer Society, 2008, pp. 76-85.
    @INCOLLECTION{RTTV08,
      author = {Reingold, O. and Trevisan, L. and Tulsiani, M. and Vadhan, S.},
      booktitle = {Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science},
      address = {Washington DC},
      title = {Dense subsets of pseudorandom sets},
      publisher = {IEEE Computer Society},
      year = {2008},
      pages = {76--85},
      }
  • [RR93] V. Rödl and A. Ruciński, "Lower bounds on probability thresholds for Ramsey properties," in Combinatorics, Paul Erdős is Eighty, Budapest: János Bolyai Math. Soc., 1993, vol. 1, pp. 317-346.
    @INCOLLECTION{RR93, mrkey = {1249720},
      author = {R{ö}dl, V. and Ruci{ń}ski, A.},
      mrclass = {05C55 (05C80)},
      series = {Bolyai Soc. Math. Stud.},
      address = {Budapest},
      publisher = {János Bolyai Math. Soc.},
      volume = {1},
      mrnumber = {1249720},
      booktitle = {Combinatorics, {P}aul {E}rdős is Eighty},
      mrreviewer = {C. C. Rousseau},
      title = {Lower bounds on probability thresholds for {R}amsey properties},
      pages = {317--346},
      year = {1993},
      zblnumber = {0790.05078},
      }
  • [RR94] Go to document V. Rödl and A. Ruciński, "Random graphs with monochromatic triangles in every edge coloring," Random Structures Algorithms, vol. 5, iss. 2, pp. 253-270, 1994.
    @ARTICLE{RR94, mrkey = {1262978},
      number = {2},
      issn = {1042-9832},
      author = {R{ö}dl, Vojt{ě}ch and Ruci{ń}ski, Andrzej},
      mrclass = {05C80 (05C55)},
      doi = {10.1002/rsa.3240050202},
      journal = {Random Structures Algorithms},
      volume = {5},
      mrnumber = {1262978},
      fjournal = {Random Structures \& Algorithms},
      mrreviewer = {A. G. Thomason},
      title = {Random graphs with monochromatic triangles in every edge coloring},
      year = {1994},
      pages = {253--270},
      zblnumber = {0790.05079},
      }
  • [RR95] Go to document V. Rödl and A. Ruciński, "Threshold functions for Ramsey properties," J. Amer. Math. Soc., vol. 8, iss. 4, pp. 917-942, 1995.
    @ARTICLE{RR95, mrkey = {1276825},
      number = {4},
      issn = {0894-0347},
      author = {R{ö}dl, Vojt{ě}ch and Ruci{ń}ski, Andrzej},
      mrclass = {05C55 (05C80 05D10)},
      doi = {10.2307/2152833},
      journal = {J. Amer. Math. Soc.},
      volume = {8},
      mrnumber = {1276825},
      fjournal = {Journal of the American Mathematical Society},
      title = {Threshold functions for {R}amsey properties},
      year = {1995},
      pages = {917--942},
      zblnumber = {0846.05079},
      }
  • [RR97] Go to document V. Rödl and A. Ruciński, "Rado partition theorem for random subsets of integers," Proc. London Math. Soc., vol. 74, iss. 3, pp. 481-502, 1997.
    @ARTICLE{RR97, mrkey = {1434440},
      number = {3},
      issn = {0024-6115},
      author = {R{ö}dl, Vojtech and Ruci{ń}ski, Andrzej},
      mrclass = {05D10 (11B25 60C05)},
      doi = {10.1112/S0024611597000178},
      journal = {Proc. London Math. Soc.},
      volume = {74},
      mrnumber = {1434440},
      fjournal = {Proceedings of the London Mathematical Society. Third Series},
      mrreviewer = {Yuri Bilu},
      title = {Rado partition theorem for random subsets of integers},
      year = {1997},
      pages = {481--502},
      zblnumber = {0880.05080},
      }
  • [RR98] Go to document V. Rödl and A. Ruciński, "Ramsey properties of random hypergraphs," J. Combin. Theory Ser. A, vol. 81, iss. 1, pp. 1-33, 1998.
    @ARTICLE{RR98, mrkey = {1492867},
      number = {1},
      issn = {0097-3165},
      author = {R{ö}dl, Vojtech and Ruci{ń}ski, Andrzej},
      mrclass = {05C80 (05C55 05C65)},
      doi = {10.1006/jcta.1997.2785},
      journal = {J. Combin. Theory Ser. A},
      volume = {81},
      mrnumber = {1492867},
      fjournal = {Journal of Combinatorial Theory. Series A},
      mrreviewer = {Tomasz J. {\L}uczak},
      coden = {JCBTA7},
      title = {Ramsey properties of random hypergraphs},
      year = {1998},
      pages = {1--33},
      zblnumber = {0893.05011},
      }
  • [RRS07] Go to document V. Rödl, A. Ruciński, and M. Schacht, "Ramsey properties of random $k$-partite, $k$-uniform hypergraphs," SIAM J. Discrete Math., vol. 21, iss. 2, pp. 442-460, 2007.
    @ARTICLE{RRS07, mrkey = {2318677},
      number = {2},
      issn = {0895-4801},
      author = {R{ö}dl, Vojt{ě}ch and Ruci{ń}ski, Andrzej and Schacht, Mathias},
      mrclass = {05C55 (05C65 05C80 05D10)},
      doi = {10.1137/060657492},
      journal = {SIAM J. Discrete Math.},
      volume = {21},
      mrnumber = {2318677},
      fjournal = {SIAM Journal on Discrete Mathematics},
      mrreviewer = {A. G. Thomason},
      title = {Ramsey properties of random {$k$}-partite, {$k$}-uniform hypergraphs},
      year = {2007},
      pages = {442--460},
      zblnumber = {1140.05043},
      }
  • [RS04] Go to document V. Rödl and J. Skokan, "Regularity lemma for $k$-uniform hypergraphs," Random Structures Algorithms, vol. 25, iss. 1, pp. 1-42, 2004.
    @ARTICLE{RS04, mrkey = {2069663},
      number = {1},
      issn = {1042-9832},
      author = {R{ö}dl, Vojt{ě}ch and Skokan, Jozef},
      mrclass = {05D05 (05C65 05C75 60C05)},
      doi = {10.1002/rsa.20017},
      journal = {Random Structures Algorithms},
      volume = {25},
      mrnumber = {2069663},
      fjournal = {Random Structures \& Algorithms},
      mrreviewer = {W. G. Brown},
      title = {Regularity lemma for {$k$}-uniform hypergraphs},
      year = {2004},
      pages = {1--42},
      zblnumber = {1046.05042},
      }
  • [R53] Go to document K. F. Roth, "On certain sets of integers," J. London Math. Soc., vol. 28, pp. 104-109, 1953.
    @ARTICLE{R53, mrkey = {0051853},
      issn = {0024-6107},
      author = {Roth, K. F.},
      mrclass = {10.0X},
      doi = {10.1112/jlms/s1-28.1.104},
      journal = {J. London Math. Soc.},
      volume = {28},
      mrnumber = {0051853},
      fjournal = {Journal of the London Mathematical Society. Second Series},
      mrreviewer = {P. Erd{ö}s},
      title = {On certain sets of integers},
      year = {1953},
      pages = {104--109},
      zblnumber = {0050.04002},
      }
  • [Sj14] Go to document W. Samotij, "Stability results for random discrete structures," Random Structures Algorithms, vol. 44, iss. 3, pp. 269-289, 2014.
    @ARTICLE{Sj14, mrkey = {3188596},
      number = {3},
      issn = {1042-9832},
      author = {Samotij, Wojciech},
      mrclass = {05C80 (05C35)},
      doi = {10.1002/rsa.20477},
      journal = {Random Structures Algorithms},
      volume = {44},
      mrnumber = {3188596},
      fjournal = {Random Structures \& Algorithms},
      mrreviewer = {David Conlon},
      title = {Stability results for random discrete structures},
      year = {2014},
      pages = {269--289},
      zblnumber = {1290.05131},
      }
  • [ST14] Go to document D. Saxton and A. Thomason, "Hypergraph containers," Invent. Math., vol. 201, iss. 3, pp. 925-992, 2015.
    @ARTICLE{ST14, mrkey = {3385638},
      number = {3},
      issn = {0020-9910},
      author = {Saxton, David and Thomason, Andrew},
      mrclass = {05C65 (05C69)},
      doi = {10.1007/s00222-014-0562-8},
      journal = {Invent. Math.},
      volume = {201},
      mrnumber = {3385638},
      fjournal = {Inventiones Mathematicae},
      title = {Hypergraph containers},
      year = {2015},
      pages = {925--992},
      zblnumber = {1320.05085},
      }
  • [S09] Go to document M. Schacht, "Extremal results for discrete random structures," Ann. of Math., vol. 184, pp. 333-365, 2016.
    @ARTICLE{S09,
      author = {Schacht, Mathias},
      title = {Extremal results for discrete random structures},
      doi = {10.4007/annals.2016.184.2.1},
      pages = {333--365},
      year = {2016},
      journal = {Ann. of Math.},
      volume = {184},
      }
  • [S16] I. Schur, "Über die Kongruenz $x^m + y^m = z^m \, (\mbox{mod } p)$," Jber. Deutsch. Mat. Verein., vol. 25, pp. 114-117, 1916.
    @ARTICLE{S16, volume = {25},
      author = {Schur, I.},
      title = {{Ü}ber die Kongruenz $x^m + y^m = z^m \, (\mbox{mod } p)$},
      pages = {114--117},
      year = {1916},
      journal = {Jber. Deutsch. Mat. Verein.},
      jfmnumber = {46.0193.02},
      }
  • [S68] M. Simonovits, "A method for solving extremal problems in graph theory, stability problems," in Theory of Graphs, New York: Academic Press, 1968, pp. 279-319.
    @INCOLLECTION{S68, mrkey = {0233735},
      author = {Simonovits, M.},
      mrclass = {05.55},
      address = {New York},
      publisher = {Academic Press},
      mrnumber = {0233735},
      booktitle = {Theory of {G}raphs},
      venue = {{P}roc. {C}olloq., {T}ihany, 1966},
      mrreviewer = {J. W. Moon},
      title = {A method for solving extremal problems in graph theory, stability problems},
      pages = {279--319},
      year = {1968},
      zblnumber = {0164.24604},
      }
  • [SV03] Go to document T. Szabó and V. H. Vu, "Turán’s theorem in sparse random graphs," Random Structures Algorithms, vol. 23, iss. 3, pp. 225-234, 2003.
    @ARTICLE{SV03, mrkey = {1999036},
      number = {3},
      issn = {1042-9832},
      author = {Szab{ó},
      Tibor and Vu, Van H.},
      mrclass = {05C80 (05C35 60C05)},
      doi = {10.1002/rsa.10088},
      journal = {Random Structures Algorithms},
      volume = {23},
      mrnumber = {1999036},
      fjournal = {Random Structures \& Algorithms},
      mrreviewer = {David B. Penman},
      title = {Turán's theorem in sparse random graphs},
      year = {2003},
      pages = {225--234},
      zblnumber = {1028.05101},
      }
  • [Sz75] E. Szemerédi, "On sets of integers containing no $k$ elements in arithmetic progression," Acta Arith., vol. 27, pp. 199-245, 1975.
    @ARTICLE{Sz75, mrkey = {0369312},
      issn = {0065-1036},
      author = {Szemer{é}di, E.},
      mrclass = {10L10},
      journal = {Acta Arith.},
      volume = {27},
      mrnumber = {0369312},
      note = {Collection of articles in memory of Juri{\u\i} Vladimirovi{\v{c}} Linnik},
      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},
      zblnumber = {0335.10054},
      }
  • [Sz78] E. Szemerédi, "Regular partitions of graphs," in Problèmes Combinatoires et Théorie des Graphes, Paris: CNRS, 1978, vol. 260, pp. 399-401.
    @INCOLLECTION{Sz78, mrkey = {0540024},
      author = {Szemer{é}di, Endre},
      mrclass = {05C35 (10L10)},
      series = {Colloq. Internat. CNRS},
      address = {Paris},
      publisher = {CNRS},
      volume = {260},
      mrnumber = {0540024},
      booktitle = {Problèmes Combinatoires et Théorie des Graphes},
      mrreviewer = {D. A. Klarner},
      venue = {{C}olloq. {I}nternat. {CNRS},
      {U}niv. {O}rsay, {O}rsay, 1976},
      title = {Regular partitions of graphs},
      pages = {399--401},
      year = {1978},
      zblnumber = {0413.05055},
      }
  • [T06] Go to document T. Tao, "A variant of the hypergraph removal lemma," J. Combin. Theory Ser. A, vol. 113, iss. 7, pp. 1257-1280, 2006.
    @ARTICLE{T06, mrkey = {2259060},
      number = {7},
      issn = {0097-3165},
      author = {Tao, Terence},
      mrclass = {05C35 (05C65 05C75 11B75 37A45)},
      doi = {10.1016/j.jcta.2005.11.006},
      journal = {J. Combin. Theory Ser. A},
      volume = {113},
      mrnumber = {2259060},
      fjournal = {Journal of Combinatorial Theory. Series A},
      mrreviewer = {Jozef Skokan},
      coden = {JCBTA7},
      title = {A variant of the hypergraph removal lemma},
      year = {2006},
      pages = {1257--1280},
      zblnumber = {1105.05052},
      }
  • [T41] P. Turán, "Eine Extremalaufgabe aus der Graphentheorie," Mat. Fiz. Lapok, vol. 48, pp. 436-452, 1941.
    @ARTICLE{T41, mrkey = {0018405},
      volume = {48},
      mrnumber = {0018405},
      author = {Tur{á}n, Paul},
      mrclass = {56.0X},
      mrreviewer = {P. Erd{ö}s},
      title = {Eine {E}xtremalaufgabe aus der {G}raphentheorie},
      pages = {436--452},
      year = {1941},
      journal = {Mat. Fiz. Lapok},
      zblnumber = {0026.26903},
      }
  • [VdW27] B. L. van der Waerden, "Beweis einer Baudetschen Vermutung," Nieuw. Arch. Wisk., vol. 15, pp. 212-216, 1927.
    @ARTICLE{VdW27, volume = {15},
      author = {van der Waerden, B. L.},
      title = {Beweis einer Baudetschen Vermutung},
      pages = {212--216},
      year = {1927},
      journal = {Nieuw. Arch. Wisk.},
      jfmnumber = {53.0073.12},
      }
  • [V59] Go to document P. Varnavides, "On certain sets of positive density," J. London Math. Soc., vol. 34, pp. 358-360, 1959.
    @ARTICLE{V59, mrkey = {0106865},
      issn = {0024-6107},
      author = {Varnavides, P.},
      mrclass = {10.00},
      doi = {10.1112/jlms/s1-34.3.358},
      journal = {J. London Math. Soc.},
      volume = {34},
      mrnumber = {0106865},
      fjournal = {Journal of the London Mathematical Society. Second Series},
      mrreviewer = {P. Erd{ö}s},
      title = {On certain sets of positive density},
      year = {1959},
      pages = {358--360},
      zblnumber = {0088.25702},
      }
  • [Vu01] V. H. Vu, "A large deviation result on the number of small subgraphs of a random graph," Combin. Probab. Comput., vol. 10, iss. 1, pp. 79-94, 2001.
    @ARTICLE{Vu01, mrkey = {1827810},
      number = {1},
      issn = {0963-5483},
      author = {Vu, Van H.},
      mrclass = {05C80},
      journal = {Combin. Probab. Comput.},
      volume = {10},
      mrnumber = {1827810},
      fjournal = {Combinatorics, Probability and Computing},
      mrreviewer = {Andrzej Ruci{ń}ski},
      title = {A large deviation result on the number of small subgraphs of a random graph},
      year = {2001},
      pages = {79--94},
      zblnumber = {0982.05092},
      }

Authors

D. Conlon

Mathematical Institute, University of Oxford, Oxford, United Kingdom

W. T. Gowers

Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge, United Kingdom