A new proof of the graph removal lemma

Abstract

Let $H$ be a fixed graph with $h$ vertices. The graph removal lemma states that every graph on $n$ vertices with $o(n^h)$ copies of $H$ can be made $H$-free by removing $o(n^2)$ edges. We give a new proof which avoids Szemerédi’s regularity lemma and gives a better bound. This approach also works to give improved bounds for the directed and multicolored analogues of the graph removal lemma. This answers questions of Alon and Gowers.

  • [AjSz] M. Ajtai and E. Szemerédi, "Sets of lattice points that form no squares," Stud. Sci. Math. Hungar., vol. 9, pp. 9-11 (1975), 1974.
    @article {AjSz, MRKEY = {0369299},
      AUTHOR = {Ajtai, M. and Szemer{é}di, E.},
      TITLE = {Sets of lattice points that form no squares},
      JOURNAL = {Stud. Sci. Math. Hungar.},
      FJOURNAL = {Studia Scientiarum Mathematicarum Hungarica. A Quarterly of the Hungarian Academy of Sciences},
      VOLUME = {9},
      YEAR = {1974},
      PAGES = {9--11 (1975)},
      ISSN = {0081-6906},
      MRCLASS = {10J25 (10E05)},
      MRNUMBER = {0369299},
      MRREVIEWER = {A. C. Woods},
      ZBLCOMMENT = {BIBPROC: YEAR doesn't match found ZBLNUMBER},
      ZBLNUMBER = {0303.10046},
      }
  • [Al] Go to document N. Alon, "Testing subgraphs in large graphs," Random Structures Algorithms, vol. 21, iss. 3-4, pp. 359-370, 2002.
    @article {Al, MRKEY = {1945375},
      AUTHOR = {Alon, Noga},
      TITLE = {Testing subgraphs in large graphs},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {21},
      YEAR = {2002},
      NUMBER = {3-4},
      PAGES = {359--370},
      ISSN = {1042-9832},
      MRCLASS = {05C85 (68R10)},
      MRNUMBER = {1945375},
      DOI = {10.1002/rsa.10056},
      ZBLNUMBER = {1027.68095},
      }
  • [AlSh] Go to document N. Alon and A. Shapira, "Testing subgraphs in directed graphs," J. Comput. System Sci., vol. 69, iss. 3, pp. 353-382, 2004.
    @article {AlSh, MRKEY = {2087940},
      AUTHOR = {Alon, Noga and Shapira, Asaf},
      TITLE = {Testing subgraphs in directed graphs},
      JOURNAL = {J. Comput. System Sci.},
      FJOURNAL = {Journal of Computer and System Sciences},
      VOLUME = {69},
      YEAR = {2004},
      NUMBER = {3},
      PAGES = {353--382},
      ISSN = {0022-0000},
      CODEN = {JCSSBM},
      MRCLASS = {68Q25 (05C20 68Q15 68R10 68W20)},
      MRNUMBER = {2087940},
      MRREVIEWER = {Eldar Fischer},
      DOI = {10.1016/j.jcss.2004.04.008},
      ZBLNUMBER = {1084.68087},
      }
  • [AlSp] N. Alon and J. H. Spencer, The Probabilistic Method, Third ed., Hoboken, NJ: John Wiley & Sons, 2008.
    @book {AlSp, MRKEY = {2437651},
      AUTHOR = {Alon, Noga and Spencer, Joel H.},
      TITLE = {The Probabilistic Method},
      SERIES = {Wiley-Interscience Series in Discrete Mathematics and Optimization},
      EDITION = {Third},
      PUBLISHER = {John Wiley \& Sons},
      ADDRESS = {Hoboken, NJ},
      YEAR = {2008},
      PAGES = {xviii+352},
      ISBN = {978-0-470-17020-5},
      MRCLASS = {60-02 (05C80 60C05 60F99 60G42)},
      MRNUMBER = {2437651},
      ZBLNUMBER = {1158.60303},
      ZBLNUMBER = {1148.05001},
      }
  • [Be] F. A. Behrend, "On sets of integers which contain no three terms in arithmetical progression," Proc. Nat. Acad. Sci. U. S. A., vol. 32, pp. 331-332, 1946.
    @article {Be, MRKEY = {0018694},
      AUTHOR = {Behrend, F. A.},
      TITLE = {On sets of integers which contain no three terms in arithmetical progression},
      JOURNAL = {Proc. Nat. Acad. Sci. U. S. A.},
      FJOURNAL = {Proceedings of the National Academy of Sciences of the United States of America},
      VOLUME = {32},
      YEAR = {1946},
      PAGES = {331--332},
      ISSN = {0027-8424},
      MRCLASS = {10.0X},
      MRNUMBER = {0018694},
      MRREVIEWER = {P. Erd{ö}s},
      ZBLNUMBER = {0060.10302},
      }
  • [BES] W. G. Brown, P. ErdHos, and V. T. Sós, "Some extremal problems on $r$-graphs," in New Directions in the Theory of Graphs, New York, 1973, pp. 53-63.
    @inproceedings {BES, MRKEY = {0351888},
      AUTHOR = {Brown, W. G. and Erd{ő}s, P. and S{ó}s, V. T.},
      TITLE = {Some extremal problems on {$r$}-graphs},
      BOOKTITLE = {New Directions in the Theory of Graphs},
      VENUE={{P}roc. {T}hird {A}nn {A}rbor {C}onf., {U}niv. {M}ichigan, {A}nn {A}rbor, {M}ich, 1971},
      PAGES = {53--63},
      PUBLISHER = {Academic Press},
      ADDRESS = {New York},
      YEAR = {1973},
      MRCLASS = {05C35},
      MRNUMBER = {0351888},
      MRREVIEWER = {B. Bollobas},
      ZBLNUMBER={0258.05132},
     }
  • [BuErGrSo] Go to document S. A. Burr, P. ErdHos, R. L. Graham, and V. T. Sós, "Maximal anti-Ramsey graphs and the strong chromatic number," J. Graph Theory, vol. 13, iss. 3, pp. 263-282, 1989.
    @article {BuErGrSo, MRKEY = {1000076},
      AUTHOR = {Burr, S. A. and Erd{ő}s, P. and Graham, R. L. and S{ó}s, V. T.},
      TITLE = {Maximal anti-{R}amsey graphs and the strong chromatic number},
      JOURNAL = {J. Graph Theory},
      FJOURNAL = {Journal of Graph Theory},
      VOLUME = {13},
      YEAR = {1989},
      NUMBER = {3},
      PAGES = {263--282},
      ISSN = {0364-9024},
      CODEN = {JGTHDO},
      MRCLASS = {05C55 (05C35)},
      MRNUMBER = {1000076},
      MRREVIEWER = {Miros{\l}aw Truszczy{ń}ski},
      DOI = {10.1002/jgt.3190130302},
      }
  • [Er] Go to document P. ErdHos, "Problems and results in combinatorial analysis and graph theory," in Proceedings of the First Japan Conference on Graph Theory and Applications, 1988, pp. 81-92.
    @inproceedings {Er, MRKEY = {0975526},
      AUTHOR = {Erd{ő}s, Paul},
      TITLE = {Problems and results in combinatorial analysis and graph theory},
      BOOKTITLE = {Proceedings of the {F}irst {J}apan {C}onference on {G}raph {T}heory and {A}pplications},
      VENUE={{H}akone, 1986},
      SERIES = {Discrete Math.},
      FJOURNAL = {Discrete Mathematics},
      VOLUME = {72},
      YEAR = {1988},
      PAGES = {81--92},
      ISSN = {0012-365X},
      CODEN = {DSMHA4},
      MRCLASS = {05C35 (05C55)},
      MRNUMBER = {0975526},
      MRREVIEWER = {R. L. Graham},
      DOI = {10.1016/0012-365X(88)90196-3},
      ZBLNUMBER={0661.05037},
      }
  • [EFR] Go to document P. ErdHos, P. Frankl, and V. Rödl, "The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent," Graphs Combin., vol. 2, iss. 2, pp. 113-121, 1986.
    @article {EFR, MRKEY = {0932119},
      AUTHOR = {Erd{ő}s, Paul and Frankl, P. and R{ö}dl, V.},
      TITLE = {The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent},
      JOURNAL = {Graphs Combin.},
      FJOURNAL = {Graphs and Combinatorics},
      VOLUME = {2},
      YEAR = {1986},
      NUMBER = {2},
      PAGES = {113--121},
      ISSN = {0911-0119},
      CODEN = {GRCOE5},
      MRCLASS = {05C30 (05C65 05C75)},
      MRNUMBER = {0932119},
      MRREVIEWER = {Edward A. Bender},
      DOI = {10.1007/BF01788085},
      ZBLNUMBER = {0593.05038},
      }
  • [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},
      AUTHOR = {Erd{ő}s, Paul and Simonovits, Mikl{ó}s},
      TITLE = {Supersaturated graphs and hypergraphs},
      JOURNAL = {Combinatorica},
      FJOURNAL = {Combinatorica. An International Journal of the János Bolyai Mathematical Society},
      VOLUME = {3},
      YEAR = {1983},
      NUMBER = {2},
      PAGES = {181--192},
      ISSN = {0209-9683},
      CODEN = {COMBDI},
      MRCLASS = {05C55 (05C65)},
      MRNUMBER = {0726456},
      MRREVIEWER = {E. Rodney Canfield},
      DOI = {10.1007/BF02579292},
      ZBLNUMBER = {0529.05027},
     }
  • [GGR] Go to document O. Goldreich, S. Goldwasser, and D. Ron, "Property testing and its connection to learning and approximation," J. ACM, vol. 45, iss. 4, pp. 653-750, 1998.
    @article {GGR, MRKEY = {1675099},
      AUTHOR = {Goldreich, Oded and Goldwasser, Shafi and Ron, Dana},
      TITLE = {Property testing and its connection to learning and approximation},
      JOURNAL = {J. ACM},
      FJOURNAL = {Journal of the ACM},
      VOLUME = {45},
      YEAR = {1998},
      NUMBER = {4},
      PAGES = {653--750},
      ISSN = {0004-5411},
      MRCLASS = {68Q25 (05C85 60C05 68R10 68W25)},
      MRNUMBER = {1675099},
      MRREVIEWER = {Mark R. Jerrum},
      DOI = {10.1145/285055.285060},
      ZBLNUMBER = {1065.68575},
      }
  • [Go] Go to document W. T. Gowers, "Lower bounds of tower type for Szemer├ędi’s uniformity lemma," Geom. Funct. Anal., vol. 7, iss. 2, pp. 322-337, 1997.
    @article {Go, MRKEY = {1445389},
      AUTHOR = {Gowers, W. T.},
      TITLE = {Lower bounds of tower type for {S}zemerédi's uniformity lemma},
      JOURNAL = {Geom. Funct. Anal.},
      FJOURNAL = {Geometric and Functional Analysis},
      VOLUME = {7},
      YEAR = {1997},
      NUMBER = {2},
      PAGES = {322--337},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {11B25 (05C35)},
      MRNUMBER = {1445389},
      MRREVIEWER = {Yuri Bilu},
      DOI = {10.1007/PL00001621},
      ZBLNUMBER = {0876.05053},
      }
  • [Go1] Go to document W. T. Gowers, Some unsolved problems in additive/combinatorial number theory.
    @misc{Go1,
      author={Gowers, W. T.},
      TITLE = {Some unsolved problems in additive/combinatorial number theory},
      URL={www.dpmms.cam.ac.uk/śwtg10/papers.html},
      SORTYEAR={2012},
      }
  • [Go2] W. T. Gowers, "Rough structure and classification," in GAFA 2000. Visions in Mathematics — Towards 2000, 2000, pp. 79-117.
    @inproceedings {Go2, MRKEY = {1826250},
      AUTHOR = {Gowers, W. T.},
      TITLE = {Rough structure and classification},
      BOOKTITLE = {GAFA 2000. Visions in Mathematics --- Towards 2000},
      VENUE={Tel Aviv, 1999},
      JOURNAL = {Geom. Funct. Anal.},
      VOLUME={2000},
      FJOURNAL = {Geometric and Functional Analysis},
      YEAR = {2000},
      NOTE = {{\rm Special Volume, Part I}},
      PAGES = {79--117},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {01A67 (00A30 05C55 05Dxx 68T01 68T15)},
      MRNUMBER = {1826250},
      MRREVIEWER = {Jerrold W. Grossman},
      ZBLNUMBER = {0989.01020},
      }
  • [Go3] 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 {Go3, MRKEY = {1844079},
      AUTHOR = {Gowers, W. T.},
      TITLE = {A new proof of {S}zemerédi's theorem},
      JOURNAL = {Geom. Funct. Anal.},
      FJOURNAL = {Geometric and Functional Analysis},
      VOLUME = {11},
      YEAR = {2001},
      NUMBER = {3},
      PAGES = {465--588},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {11B25 (11K38 11K45)},
      MRNUMBER = {1844079},
      MRREVIEWER = {Hillel Furstenberg},
      DOI = {10.1007/s00039-001-0332-9},
      ZBLNUMBER = {1028.11005},
      }
  • [Go4] 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 {Go4, MRKEY = {2195580},
      AUTHOR = {Gowers, W. T.},
      TITLE = {Quasirandomness, counting and regularity for 3-uniform hypergraphs},
      JOURNAL = {Combin. Probab. Comput.},
      FJOURNAL = {Combinatorics, Probability and Computing},
      VOLUME = {15},
      YEAR = {2006},
      NUMBER = {1-2},
      PAGES = {143--184},
      ISSN = {0963-5483},
      MRCLASS = {05D05 (05C35 05C65)},
      MRNUMBER = {2195580},
      MRREVIEWER = {J{ó}zsef Solymosi},
      DOI = {10.1017/S0963548305007236},
      ZBLNUMBER = {1082.05081},
      }
  • [Go5] 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 {Go5, MRKEY = {2373376},
      AUTHOR = {Gowers, W. T.},
      TITLE = {Hypergraph regularity and the multidimensional {S}zemerédi theorem},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {166},
      YEAR = {2007},
      NUMBER = {3},
      PAGES = {897--946},
      ISSN = {0003-486X},
      CODEN = {ANMAAH},
      MRCLASS = {05D10 (05C30 05C35 05C55 05C80 28D15)},
      MRNUMBER = {2373376},
      MRREVIEWER = {G{á}bor N. S{á}rk{ö}zy},
      DOI = {10.4007/annals.2007.166.897},
      ZBLNUMBER = {1159.05052},
      }
  • [Gr] Go to document B. Green, "A Szemer├ędi-type regularity lemma in abelian groups, with applications," Geom. Funct. Anal., vol. 15, iss. 2, pp. 340-376, 2005.
    @article {Gr, MRKEY = {2153903},
      AUTHOR = {Green, B.},
      TITLE = {A {S}zemerédi-type regularity lemma in abelian groups, with applications},
      JOURNAL = {Geom. Funct. Anal.},
      FJOURNAL = {Geometric and Functional Analysis},
      VOLUME = {15},
      YEAR = {2005},
      NUMBER = {2},
      PAGES = {340--376},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {11B75 (05D05 20K01)},
      MRNUMBER = {2153903},
      MRREVIEWER = {Mei Chu Chang},
      DOI = {10.1007/s00039-005-0509-8},
      ZBLNUMBER = {1160.11314},
      }
  • [KoSi] J. Komlós and M. Simonovits, "Szemer├ędi’s regularity lemma and its applications in graph theory," in Combinatorics, Paul Erdős is Eighty, Budapest, 1996, pp. 295-352.
    @inproceedings {KoSi, MRKEY = {1395865},
      AUTHOR = {Koml{ó}s, J. and Simonovits, M.},
      TITLE = {Szemerédi's regularity lemma and its applications in graph theory},
      BOOKTITLE = {Combinatorics, {P}aul {E}rdős is Eighty},
      VENUE={{K}eszthely, 1993},
      SERIES = {Bolyai Soc. Math. Stud.},
      VOLUME={2},
      PAGES = {295--352},
      PUBLISHER = {János Bolyai Math. Soc.},
      ADDRESS = {Budapest},
      YEAR = {1996},
      MRCLASS = {05C35},
      MRNUMBER = {1395865},
      MRREVIEWER = {W. G. Brown},
      ZBLNUMBER = {0851.05065},
      }
  • [KSV] Go to document D. Král, O. Serra, and L. Vena, "A combinatorial proof of the removal lemma for groups," J. Combin. Theory Ser. A, vol. 116, iss. 4, pp. 971-978, 2009.
    @article {KSV, MRKEY = {2513645},
      AUTHOR = {Kr{á}l, Daniel and Serra, Oriol and Vena, Llu{\'ı}s},
      TITLE = {A combinatorial proof of the removal lemma for groups},
      JOURNAL = {J. Combin. Theory Ser. A},
      FJOURNAL = {Journal of Combinatorial Theory. Series A},
      VOLUME = {116},
      YEAR = {2009},
      NUMBER = {4},
      PAGES = {971--978},
      ISSN = {0097-3165},
      CODEN = {JCBTA7},
      MRCLASS = {20D60 (05E10)},
      MRNUMBER = {2513645},
      MRREVIEWER = {Marius T{\u{a}}rn{\u{a}}uceanu},
      DOI = {10.1016/j.jcta.2008.12.003},
      ZBLNUMBER = {1209.05261},
      }
  • [KSV1] D. Král, O. Serra, and L. Vena, A removal lemma for systems of linear equations over finite fields.
    @misc{KSV1,
      author={Kr{á}l, Daniel and Serra, Oriol and Vena, Llu{\'ı}s},
      TITLE={A removal lemma for systems of linear equations over finite fields},
      NOTE={{\it Isreal J. Math.},
      to appear},
      }
  • [NaRoSc] 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 {NaRoSc, MRKEY = {2198495},
      AUTHOR = {Nagle, Brendan and R{ö}dl, Vojt{ě}ch and Schacht, Mathias},
      TITLE = {The counting lemma for regular {$k$}-uniform hypergraphs},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {28},
      YEAR = {2006},
      NUMBER = {2},
      PAGES = {113--179},
      ISSN = {1042-9832},
      MRCLASS = {05C35 (05C65)},
      MRNUMBER = {2198495},
      MRREVIEWER = {Jozef Skokan},
      DOI = {10.1002/rsa.20117},
      ZBLNUMBER = {1093.05045},
      }
  • [RoSk] 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 {RoSk, MRKEY = {2069663},
      AUTHOR = {R{ö}dl, Vojt{ě}ch and Skokan, Jozef},
      TITLE = {Regularity lemma for {$k$}-uniform hypergraphs},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {25},
      YEAR = {2004},
      NUMBER = {1},
      PAGES = {1--42},
      ISSN = {1042-9832},
      MRCLASS = {05D05 (05C65 05C75 60C05)},
      MRNUMBER = {2069663},
      MRREVIEWER = {W. G. Brown},
      DOI = {10.1002/rsa.20017},
      ZBLNUMBER = {1046.05042},
      }
  • [Ro] Go to document K. F. Roth, "On certain sets of integers," J. London Math. Soc., vol. 28, pp. 104-109, 1953.
    @article {Ro, MRKEY = {0051853},
      AUTHOR = {Roth, K. F.},
      TITLE = {On certain sets of integers},
      JOURNAL = {J. London Math. Soc.},
      FJOURNAL = {Journal of the London Mathematical Society. Second Series},
      VOLUME = {28},
      YEAR = {1953},
      PAGES = {104--109},
      ISSN = {0024-6107},
      MRCLASS = {10.0X},
      MRNUMBER = {0051853},
      MRREVIEWER = {P. Erd{ö}s},
      DOI = {10.1112/jlms/s1-28.1.104},
      ZBLNUMBER = {0050.04002},
      }
  • [RuSu] Go to document R. Rubinfeld and M. Sudan, "Robust characterizations of polynomials with applications to program testing," SIAM J. Comput., vol. 25, iss. 2, pp. 252-271, 1996.
    @article {RuSu, MRKEY = {1379300},
      AUTHOR = {Rubinfeld, Ronitt and Sudan, Madhu},
      TITLE = {Robust characterizations of polynomials with applications to program testing},
      JOURNAL = {SIAM J. Comput.},
      FJOURNAL = {SIAM Journal on Computing},
      VOLUME = {25},
      YEAR = {1996},
      NUMBER = {2},
      PAGES = {252--271},
      ISSN = {0097-5397},
      CODEN = {SMJCAT},
      MRCLASS = {68Q25 (68Q60)},
      MRNUMBER = {1379300},
      MRREVIEWER = {Claus-Peter Schnorr},
      DOI = {10.1137/S0097539793255151},
      ZBLNUMBER = {0844.68062},
      }
  • [RuSz] I. Z. Ruzsa and E. Szemerédi, "Triple systems with no six points carrying three triangles," in Combinatorics, Vol. II, Amsterdam, 1978, pp. 939-945.
    @inproceedings {RuSz, MRKEY = {0519318},
      AUTHOR = {Ruzsa, I. Z. and Szemer{é}di, E.},
      TITLE = {Triple systems with no six points carrying three triangles},
      BOOKTITLE = {Combinatorics, {V}ol. {\rm II}},
      VENUE={{P}roc. {F}ifth {H}ungarian {C}olloq., {K}eszthely, 1976},
      SERIES = {Colloq. Math. Soc. János Bolyai},
      VOLUME = {18},
      PAGES = {939--945},
      PUBLISHER = {North-Holland},
      ADDRESS = {Amsterdam},
      YEAR = {1978},
      MRCLASS = {05C99 (05B30)},
      MRNUMBER = {0519318},
      MRREVIEWER = {W. G. Brown},
      ZBLNUMBER = {0393.05031},
      }
  • [Sha] Go to document A. Shapira, "A proof of Green’s conjecture regarding the removal properties of sets of linear equations," J. Lond. Math. Soc., vol. 81, iss. 2, pp. 355-373, 2010.
    @article {Sha, MRKEY = {2603000},
      AUTHOR = {Shapira, Asaf},
      TITLE = {A proof of {G}reen's conjecture regarding the removal properties of sets of linear equations},
      JOURNAL = {J. Lond. Math. Soc.},
      FJOURNAL = {Journal of the London Mathematical Society. Second Series},
      VOLUME = {81},
      YEAR = {2010},
      NUMBER = {2},
      PAGES = {355--373},
      ISSN = {0024-6107},
      MRCLASS = {11P99 (05C35 68Q60)},
      MRNUMBER = {2603000},
      DOI = {10.1112/jlms/jdp076},
      ZBLNUMBER = {05688501},
      }
  • [Sh] Go to document I. D. Shkredov, "On a generalization of Szemer├ędi’s theorem," Proc. London Math. Soc., vol. 93, iss. 3, pp. 723-760, 2006.
    @article {Sh, MRKEY = {2266965},
      AUTHOR = {Shkredov, I. D.},
      TITLE = {On a generalization of {S}zemerédi's theorem},
      JOURNAL = {Proc. London Math. Soc.},
      FJOURNAL = {Proceedings of the London Mathematical Society. Third Series},
      VOLUME = {93},
      YEAR = {2006},
      NUMBER = {3},
      PAGES = {723--760},
      ISSN = {0024-6115},
      CODEN = {PLMTAL},
      MRCLASS = {11B25 (37A45)},
      MRNUMBER = {2266965},
      MRREVIEWER = {Randall McCutcheon},
      DOI = {10.1017/S0024611506015991},
      ZBLNUMBER = {1194.11024},
      }
  • [So] J. Solymosi, "Note on a generalization of Roth’s theorem," in Discrete and Computational Geometry, New York: Springer-Verlag, 2003, vol. 25, pp. 825-827.
    @incollection {So, MRKEY = {2038505},
      AUTHOR = {Solymosi, J{ó}zsef},
      TITLE = {Note on a generalization of {R}oth's theorem},
      BOOKTITLE = {Discrete and Computational Geometry},
      SERIES = {Algorithms Combin.},
      VOLUME = {25},
      PAGES = {825--827},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {2003},
      MRCLASS = {05D05},
      MRNUMBER = {2038505},
      ZBLNUMBER = {1047.52011},
     }
  • [Sz1] E. Szemerédi, "On sets of integers containing no $k$ elements in arithmetic progression, Collection of articles in memory of Juri\u\i Vladimirovi\vc Linnik," Acta Arith., vol. 27, pp. 199-245, 1975.
    @article {Sz1, MRKEY = {0369312},
      AUTHOR = {Szemer{é}di, Endre},
      TITLE = {On sets of integers containing no {$k$} elements in arithmetic progression, {C}ollection of articles in memory of {J}uri{\u\i} {V}ladimirovi{\v{c}} {L}innik},
      JOURNAL = {Acta Arith.},
      FJOURNAL = {Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica},
      VOLUME = {27},
      YEAR = {1975},
      PAGES = {199--245},
      ISSN = {0065-1036},
      MRCLASS = {10L10},
      MRNUMBER = {0369312},
      MRREVIEWER = {S. L. G. Choi},
      ZBLNUMBER = {0303.10056},
      }
  • [Sz] E. Szemerédi, "Regular partitions of graphs," in Problèmes Combinatoires et Théorie des Graphes, Paris, 1978, pp. 399-401.
    @inproceedings {Sz, MRKEY = {0540024},
      AUTHOR = {Szemer{é}di, Endre},
      TITLE = {Regular partitions of graphs},
      BOOKTITLE = {Problèmes Combinatoires et Théorie des Graphes},
      VENUE={{C}olloq. {I}nternat. {CNRS},
      {U}niv. {O}rsay, {O}rsay, 1976},
      SERIES = {Colloq. Internat. CNRS},
      VOLUME = {260},
      PAGES = {399--401},
      PUBLISHER = {CNRS},
      ADDRESS = {Paris},
      YEAR = {1978},
      MRCLASS = {05C35 (10L10)},
      MRNUMBER = {0540024},
      MRREVIEWER = {D. A. Klarner},
      ZBLNUMBER = {0413.05055},
      }
  • [Ta] 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 {Ta, MRKEY = {2259060},
      AUTHOR = {Tao, Terence},
      TITLE = {A variant of the hypergraph removal lemma},
      JOURNAL = {J. Combin. Theory Ser. A},
      FJOURNAL = {Journal of Combinatorial Theory. Series A},
      VOLUME = {113},
      YEAR = {2006},
      NUMBER = {7},
      PAGES = {1257--1280},
      ISSN = {0097-3165},
      CODEN = {JCBTA7},
      MRCLASS = {05C35 (05C65 05C75 11B75 37A45)},
      MRNUMBER = {2259060},
      MRREVIEWER = {Jozef Skokan},
      DOI = {10.1016/j.jcta.2005.11.006},
      ZBLNUMBER = {1105.05052},
      }
  • [Ta1] T. Tao, Structure and Randomness: Pages from Year One of a Mathematical Blog, Providence, RI: Amer. Math. Soc., 2008.
    @book {Ta1, MRKEY = {2459552},
      AUTHOR = {Tao, Terence},
      TITLE = {Structure and Randomness: Pages from Year One of a Mathematical Blog},
      PUBLISHER = {Amer. Math. Soc.},
      ADDRESS = {Providence, RI},
      YEAR = {2008},
      PAGES = {xii+298},
      ISBN = {978-0-8218-4695-7},
      MRCLASS = {00-02},
      MRNUMBER = {2459552},
      MRREVIEWER = {W. T. Gowers},
      ZBLNUMBER = {05380664},
      }

Authors

Jacob Fox

Department of Mathematics
Massachusetts Institute of Technology
Cambridge, MA 02139-4307