Abstract
We study thresholds for extremal properties of random discrete structures. We determine the threshold for Szemerédi’s theorem on arithmetic progressions in random subsets of the integers and its multidimensional extensions, and we determine the threshold for Turán-type problems for random graphs and hypergraphs. In particular, we verify a conjecture of Kohayakawa, Łuczak, and Rödl for Turán-type problems in random graphs. Similar results were obtained independently by Conlon and Gowers.
-
[BSS90]
L. Babai, M. Simonovits, and J. Spencer, "Extremal subgraphs of random graphs," J. Graph Theory, vol. 14, iss. 5, pp. 599-622, 1990.@ARTICLE{BSS90, mrkey = {1073101},
number = {5},
author = {Babai, L{á}szl{ó} and Simonovits, Mikl{ó}s and Spencer, Joel},
issn = {0364-9024},
mrclass = {05C80 (05C35)},
journal = {J. Graph Theory},
doi = {10.1002/jgt.3190140511},
volume = {14},
mrnumber = {1073101},
fjournal = {Journal of Graph Theory},
mrreviewer = {Zbigniew Palka},
coden = {JGTHDO},
title = {Extremal subgraphs of random graphs},
pages = {599--622},
year = {1990},
zblnumber={0738.05048},
} -
[Bo78] B. Bollobás, Extremal Graph Theory, New York: Academic Press [Harcourt Brace Jovanovich, Publishers], 1978, vol. 11.
@BOOK{Bo78, mrkey = {0506522},
author = {Bollob{á}s, B{é}la},
mrclass = {05C35 (05-02)},
series = {London Math. Soc. Monogr.},
address = {New York},
isbn = {0-12-111750-2},
publisher = {Academic Press [Harcourt Brace Jovanovich, Publishers]},
volume = {11},
mrnumber = {0506522},
mrreviewer = {Michael O. Albertson},
title = {Extremal Graph Theory},
pages = {xx+488},
year = {1978},
zblnumber={0419.05031},
} -
[Bo98] B. Bollobás, Modern Graph Theory, New York: Springer-Verlag, 1998, vol. 184.
@BOOK{Bo98, mrkey = {1633290},
author = {Bollob{á}s, B{é}la},
mrclass = {05-01 (05-02 05Cxx)},
series = {Grad. Texts in Math.},
isbn = {0-387-98488-7},
address = {New York},
publisher = {Springer-Verlag},
doi = {10.1007/978-1-4612-0619-4},
volume = {184},
mrnumber = {1633290},
mrreviewer = {Jerrold W. Grossman},
title = {Modern Graph Theory},
pages = {xiv+394},
year = {1998},
zblnumber={0902.05016},
} -
[Bo01] B. Bollobás, Random Graphs, Second ed., Cambridge: Cambridge Univ. Press, 2001, vol. 73.
@BOOK{Bo01, mrkey = {1864966},
author = {Bollob{á}s, B{é}la},
mrclass = {05C80 (60C05)},
series = {Cambridge Stud. Adv. Math.},
edition = {Second},
address = { Cambridge},
isbn = {0-521-80920-7; 0-521-79722-5},
publisher = {Cambridge Univ. Press},
doi = {10.1017/CBO9780511814068},
volume = {73},
mrnumber = {1864966},
title = {Random Graphs},
pages = {xviii+498},
year = {2001},
zblnumber={0979.05003},
} -
[BoMu08] J. A. Bondy and U. S. R. Murty, Graph Theory, New York: Springer-Verlag, 2008, vol. 244.
@BOOK{BoMu08, mrkey = {2368647},
author = {Bondy, J. A. and Murty, U. S. R.},
mrclass = {05-01 (05Cxx)},
series = {Grad. Texts in Math.},
isbn = {978-1-84628-969-9},
address = {New York},
publisher = {Springer-Verlag},
volume = {244},
mrnumber = {2368647},
mrreviewer = {Arthur M. Hobbs},
title = {Graph Theory},
pages = {xii+651},
year = {2008},
zblnumber={1134.05001},
} -
[CG10] D. Conlon and W. T. Gowers, "Combinatorial theorems in sparse random sets," Ann. of Math., vol. 184, pp. 367-454, 2016.
@article{CG10,
author = {Conlon, D. and Gowers, W. T.},
journal= {Ann. of Math.},
title = {Combinatorial theorems in sparse random sets},
volume = {184},
pages = {367--454},
doi = {10.4007/annals.2016.184.2.2},
year = {2016},
} -
[Di10] R. Diestel, Graph Theory, Fourth ed., New York: Springer-Verlag, 2010, vol. 173.
@BOOK{Di10, mrkey = {2744811},
author = {Diestel, Reinhard},
mrclass = {05-01 (05Cxx)},
series = {Grad. Texts in Math.},
edition = {Fourth},
isbn = {978-3-642-14278-9},
address = {New York},
publisher = {Springer-Verlag},
volume = {173},
mrnumber = {2744811},
title = {Graph Theory},
pages = {xviii+437},
year = {2010},
zblnumber={1204.05001},
} -
[ErSt46] P. Erdös and A. H. Stone, "On the structure of linear graphs," Bull. Amer. Math. Soc., vol. 52, pp. 1087-1091, 1946.
@ARTICLE{ErSt46, mrkey = {0018807},
author = {Erd{ö}s, P. and Stone, A. H.},
issn = {0002-9904},
mrclass = {56.0X},
journal = {Bull. Amer. Math. Soc.},
doi = {10.1090/S0002-9904-1946-08715-7},
volume = {52},
mrnumber = {0018807},
fjournal = {Bulletin of the American Mathematical Society},
mrreviewer = {H. S. M. Coxeter},
title = {On the structure of linear graphs},
pages = {1087--1091},
year = {1946},
zblnumber={0063.01277},
} -
[Er38] P. ErdHos, "On sequences of integers no one of which divides the product of two others and on some related problems," Mitt. Forsch.-Inst. Math. Mech. Univ. Tomsk, vol. 2, pp. 74-82, 1938.
@ARTICLE{Er38, volume = {2},
author = {Erd{ő}s, P.},
title = {On sequences of integers no one of which divides the product of two others and on some related problems},
journal = {Mitt. Forsch.-Inst. Math. Mech. Univ. Tomsk},
year = {1938},
pages = {74--82},
zblnumber={0020.00504},
} -
[Er64] P. ErdHos, "On extremal problems of graphs and generalized graphs," Israel J. Math., vol. 2, pp. 183-190, 1964.
@ARTICLE{Er64, mrkey = {0183654},
author = {Erd{ő}s, P.},
issn = {0021-2172},
mrclass = {05.40},
journal = {Israel J. Math.},
doi = {10.1007/BF02759942},
volume = {2},
mrnumber = {0183654},
fjournal = {Israel Journal of Mathematics},
mrreviewer = {A. H. Stone},
title = {On extremal problems of graphs and generalized graphs},
pages = {183--190},
year = {1964},
zblnumber={0129.39905},
} -
[ErSi66] P. ErdHos and M. Simonovits, "A limit theorem in graph theory," Studia Sci. Math. Hungar, vol. 1, pp. 51-57, 1966.
@ARTICLE{ErSi66, mrkey = {0205876},
author = {Erd{ő}s, P. and Simonovits, M.},
issn = {0081-6906},
mrclass = {05.40},
journal = {Studia Sci. Math. Hungar},
volume = {1},
mrnumber = {0205876},
fjournal = {Studia Scientiarum Mathematicarum Hungarica. A Quarterly of the Hungarian Academy of Sciences},
mrreviewer = {W. Moser},
title = {A limit theorem in graph theory},
year = {1966},
pages = {51--57},
zblnumber={0129.39905},
} -
[ErSi83] P. ErdHos and M. Simonovits, "Supersaturated graphs and hypergraphs," Combinatorica, vol. 3, iss. 2, pp. 181-192, 1983.
@ARTICLE{ErSi83, mrkey = {0726456},
number = {2},
author = {Erd{ő}s, Paul and Simonovits, Mikl{ó}s},
issn = {0209-9683},
mrclass = {05C55 (05C65)},
journal = {Combinatorica},
doi = {10.1007/BF02579292},
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},
pages = {181--192},
year = {1983},
zblnumber={0529.05027},
} -
[ErTu36] P. Erdös and P. Turán, "On some sequences of integers," J. London Math. Soc., vol. S1-11, iss. 4, pp. 261-264, 1936.
@ARTICLE{ErTu36, mrkey = {1574918},
number = {4},
author = {Erd{ö}s, Paul and Tur{á}n, Paul},
mrclass = {Contributed Item},
journal = {J. London Math. Soc.},
doi = {10.1112/jlms/s1-11.4.261},
volume = {S1-11},
mrnumber = {1574918},
fjournal = {The Journal of the London Mathematical Society},
title = {On some sequences of integers},
year = {1936},
pages = {261--264},
zblnumber = {0015.15203},
} -
[FGR88] P. Frankl, R. L. Graham, and V. Rödl, "Quantitative theorems for regular systems of equations," J. Combin. Theory Ser. A, vol. 47, iss. 2, pp. 246-261, 1988.
@ARTICLE{FGR88, mrkey = {0930955},
number = {2},
author = {Frankl, P. and Graham, R. L. and R{ö}dl, V.},
issn = {0097-3165},
mrclass = {05A99 (15A99)},
journal = {J. Combin. Theory Ser. A},
doi = {10.1016/0097-3165(88)90020-9},
volume = {47},
mrnumber = {0930955},
fjournal = {Journal of Combinatorial Theory. Series A},
mrreviewer = {Charles M. Grinstead},
coden = {JCBTA7},
title = {Quantitative theorems for regular systems of equations},
pages = {246--261},
year = {1988},
zblnumber={0654.05002},
} -
[FR86] 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},
author = {Frankl, P. and R{ö}dl, V.},
issn = {0911-0119},
mrclass = {05C55},
journal = {Graphs Combin.},
doi = {10.1007/BF01788087},
volume = {2},
mrnumber = {0932121},
fjournal = {Graphs and Combinatorics},
mrreviewer = {J. Spencer},
coden = {GRCOE5},
title = {Large triangle-free subgraphs in graphs without {$K\sb 4$}},
pages = {135--144},
year = {1986},
zblnumber={0596.05037},
} -
[FRS] 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{FRS, mrkey = {2760356},
number = {4},
author = {Friedgut, Ehud and R{ö}dl, Vojt{ě}ch and Schacht, Mathias},
issn = {1042-9832},
mrclass = {05C80 (05D10 05D40 60C05)},
journal = {Random Structures Algorithms},
doi = {10.1002/rsa.20352},
volume = {37},
mrnumber = {2760356},
fjournal = {Random Structures \& Algorithms},
mrreviewer = {Dmitry A. Shabanov},
title = {Ramsey properties of random discrete structures},
pages = {407--436},
year = {2010},
zblnumber={1228.05284},
} -
[Fu94] Z. F–redi, "Random Ramsey graphs for the four-cycle," Discrete Math., vol. 126, iss. 1-3, pp. 407-410, 1994.
@ARTICLE{Fu94, mrkey = {1264510},
number = {1-3},
author = {F{--}redi, Zolt{á}n},
issn = {0012-365X},
mrclass = {05C55 (05C35)},
journal = {Discrete Math.},
doi = {10.1016/0012-365X(94)90287-9},
volume = {126},
mrnumber = {1264510},
fjournal = {Discrete Mathematics},
mrreviewer = {Ralph Faudree},
coden = {DSMHA4},
title = {Random {R}amsey graphs for the four-cycle},
pages = {407--410},
year = {1994},
zblnumber={0792.05128},
} -
[FuKa78] H. Furstenberg and Y. Katznelson, "An ergodic Szemerédi theorem for commuting transformations," J. Analyse Math., vol. 34, pp. 275-291 (1979), 1978.
@ARTICLE{FuKa78, mrkey = {0531279},
author = {Furstenberg, H. and Katznelson, Y.},
issn = {0021-7670},
mrclass = {28D05 (10K50 10L02 10L20)},
journal = {J. Analyse Math.},
doi = {10.1007/BF02790016},
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},
pages = {275--291 (1979)},
year = {1978},
zblnumber={0426.28014},
} -
[Ge05] S. Gerke, Random graphs with constraints, 2005.
@MISC{Ge05,
author = {Gerke, S.},
note = {Habilitationsschrift, Institut f{ü}r Informatik, Technische Universit{ä}t M{ü}nchen},
title = {Random graphs with constraints},
year = {2005},
} -
[GSS04] 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},
author = {Gerke, S. and Schickinger, T. and Steger, A.},
issn = {1042-9832},
mrclass = {05C80 (60C05)},
journal = {Random Structures Algorithms},
doi = {10.1002/rsa.20000},
volume = {24},
mrnumber = {2035876},
fjournal = {Random Structures \& Algorithms},
mrreviewer = {Michael Krivelevich},
title = {{$K\sb 5$}-free subgraphs of random graphs},
pages = {194--232},
year = {2004},
zblnumber={1035.05084},
} -
[GRR96] 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},
author = {Graham, Ronald and R{ö}dl, Vojtech and Ruci{ń}ski, Andrzej},
issn = {0022-314X},
mrclass = {05A18 (11K99)},
journal = {J. Number Theory},
doi = {10.1006/jnth.1996.0155},
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},
pages = {388--408},
year = {1996},
zblnumber={0880.05081},
} -
[GRS90] R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey Theory, Hoboken, NJ: John Wiley & Sons, 2013.
@BOOK{GRS90, mrkey = {3288500},
author = {Graham, Ronald L. and Rothschild, Bruce L. and Spencer, Joel H.},
mrclass = {05-02 (05A99 05C55 54H20)},
series = {Wiley Ser. Discrete Math. Optimization},
address = {Hoboken, NJ},
isbn = {978-1-118-79966-6},
publisher = {John Wiley \& Sons},
mrnumber = {3288500},
note = {paperback edition of the second (1990) edition [\mr{1044995}]},
title = {Ramsey Theory},
year = {2013},
pages = {xiv+196},
zblnumber={1280.05001},
} -
[HKL95] 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},
author = {Haxell, P. E. and Kohayakawa, Y. and {\L}uczak, T.},
issn = {0095-8956},
mrclass = {05C80 (60C05)},
journal = {J. Combin. Theory Ser. B},
doi = {10.1006/jctb.1995.1035},
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},
pages = {273--287},
year = {1995},
zblnumber={0828.05056},
} -
[HKL96] 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},
author = {Haxell, P. E. and Kohayakawa, Y. and {\L}uczak, T.},
issn = {0209-9683},
mrclass = {05C80 (05C35 05C38)},
journal = {Combinatorica},
doi = {10.1007/BF01300129},
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},
pages = {107--122},
year = {1996},
zblnumber={0853.05072},
} -
[JLR00] S. Janson, T. Łuczak, and A. Rucinski, Random Graphs, New York: Wiley-Interscience, 2000.
@BOOK{JLR00, mrkey = {1782847},
author = {Janson, Svante and {\L}uczak, Tomasz and Rucinski, Andrzej},
mrclass = {05C80 (60C05 82B41)},
series = {Wiley-Intersci. Ser. Discrete Math. and Optimization},
address = {New York},
isbn = {0-471-17541-2},
publisher = {Wiley-Interscience},
doi = {10.1002/9781118032718},
mrnumber = {1782847},
mrreviewer = {Mark R. Jerrum},
title = {Random Graphs},
pages = {xii+333},
year = {2000},
zblnumber={0968.05003},
} -
[KNS64] G. Katona, T. Nemetz, and M. Simonovits, "On a problem of Turán in the theory of graphs," Mat. Lapok, vol. 15, pp. 228-238, 1964.
@ARTICLE{KNS64, mrkey = {0172263},
author = {Katona, Gyula and Nemetz, Tibor and Simonovits, Mikl{ó}s},
issn = {0025-519X},
mrclass = {55.10 (05.40)},
journal = {Mat. Lapok},
volume = {15},
mrnumber = {0172263},
fjournal = {Matematikai Lapok. Bolyai János Matematikai Társulat},
title = {On a problem of {T}urán in the theory of graphs},
year = {1964},
pages = {228--238},
zblnumber={0138.19402},
} -
[KKS98] Y. Kohayakawa, B. Kreuter, and A. Steger, "An extremal problem for random graphs and the number of graphs with large even-girth," Combinatorica, vol. 18, iss. 1, pp. 101-120, 1998.
@ARTICLE{KKS98, mrkey = {1645658},
number = {1},
author = {Kohayakawa, Yoshiharu and Kreuter, B. and Steger, A.},
issn = {0209-9683},
mrclass = {05C80 (05A16 05C35 05C38)},
journal = {Combinatorica},
doi = {10.1007/PL00009804},
volume = {18},
mrnumber = {1645658},
fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
mrreviewer = {Tomasz J. {\L}uczak},
title = {An extremal problem for random graphs and the number of graphs with large even-girth},
pages = {101--120},
year = {1998},
zblnumber={0910.05059},
} -
[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},
author = {Kohayakawa, Yoshiharu and {\L}uczak, Tomasz and R{ö}dl, Vojt{ě}ch},
issn = {0065-1036},
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},
pages = {133--163},
year = {1996},
zblnumber={0858.11009},
} -
[KLR97] 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},
author = {Kohayakawa, Yoshiharu and {\L}uczak, Tomasz and R{ö}dl, Vojt{ě}ch},
issn = {0209-9683},
mrclass = {05C80 (05C35)},
journal = {Combinatorica},
doi = {10.1007/BF01200906},
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},
pages = {173--213},
year = {1997},
zblnumber={0889.05068},
} -
[KRS04] 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},
author = {Kohayakawa, Yoshiharu and R{ö}dl, Vojt{ě}ch and Schacht, Mathias},
issn = {0963-5483},
mrclass = {05C80 (05C35 60C05)},
journal = {Combin. Probab. Comput.},
doi = {10.1017/S0963548303005856},
volume = {13},
mrnumber = {2034303},
fjournal = {Combinatorics, Probability and Computing},
mrreviewer = {Ivan Pashov},
title = {The {T}urán theorem for random graphs},
pages = {61--91},
year = {2004},
zblnumber={1048.05075},
} -
[KST54] T. Kövari, V. T. Sós, and P. Turán, "On a problem of K. Zarankiewicz," Colloquium Math., vol. 3, pp. 50-57, 1954.
@ARTICLE{KST54, mrkey = {0065617},
volume = {3},
mrnumber = {0065617},
author = {K{ö}vari, T. and S{ó}s, V. T. and Tur{á}n, P.},
mrclass = {27.2X},
mrreviewer = {J. Riguet},
title = {On a problem of {K}. {Z}arankiewicz},
journal = {Colloquium Math.},
year = {1954},
pages = {50--57},
zblnumber={0055.00704},
} -
[Kre97] B. Kreuter, Probabilistic versions of Ramsey’s and Turán’s theorems, 1997.
@MISC{Kre97,
author = {Kreuter, B.},
note = {Ph.D. thesis},
title = {Probabilistic versions of {R}amsey's and {T}ur{á}n's theorems},
year = {1997},
} -
[Ma07] W. Mantel, "Vraagstuk xxviii," Wiskundige Opgaven, vol. 10, pp. 60-61, 1907.
@ARTICLE{Ma07, volume = {10},
author = {Mantel, W.},
title = {Vraagstuk xxviii},
journal = {Wiskundige Opgaven},
year = {1907},
pages = {60--61},
} -
[Ra33] R. Rado, "Studien zur Kombinatorik," Math. Z., vol. 36, iss. 1, pp. 424-470, 1933.
@ARTICLE{Ra33, mrkey = {1545354},
number = {1},
author = {Rado, Richard},
issn = {0025-5874},
mrclass = {Contributed Item},
journal = {Math. Z.},
doi = {10.1007/BF01188632},
volume = {36},
mrnumber = {1545354},
fjournal = {Mathematische Zeitschrift},
coden = {MAZEAX},
title = {Studien zur {K}ombinatorik},
pages = {424--470},
year = {1933},
zblnumber={0006.14603},
} -
[RR95] 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},
author = {R{ö}dl, Vojt{ě}ch and Ruci{ń}ski, Andrzej},
issn = {0894-0347},
mrclass = {05C55 (05C80 05D10)},
journal = {J. Amer. Math. Soc.},
doi = {10.2307/2152833},
volume = {8},
mrnumber = {1276825},
fjournal = {Journal of the American Mathematical Society},
title = {Threshold functions for {R}amsey properties},
pages = {917--942},
year = {1995},
zblnumber={0846.05079},
} -
[RR97] 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},
author = {R{ö}dl, Vojtech and Ruci{ń}ski, Andrzej},
issn = {0024-6115},
mrclass = {05D10 (11B25 60C05)},
journal = {Proc. London Math. Soc.},
doi = {10.1112/S0024611597000178},
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},
pages = {481--502},
year = {1997},
zblnumber={0880.05080},
} -
[RRS07] 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},
author = {R{ö}dl, Vojt{ě}ch and Ruci{ń}ski, Andrzej and Schacht, Mathias},
issn = {0895-4801},
mrclass = {05C55 (05C65 05C80 05D10)},
journal = {SIAM J. Discrete Math.},
doi = {10.1137/060657492},
volume = {21},
mrnumber = {2318677},
fjournal = {SIAM Journal on Discrete Mathematics},
mrreviewer = {A. G. Thomason},
title = {Ramsey properties of random {$k$}-partite, {$k$}-uniform hypergraphs},
pages = {442--460},
year = {2007},
zblnumber={1140.05043},
} -
[Schur16] I. Schur, "Über die Kongruenz $x^m+y^m\equiv z^m (\text{mod} p)$," Jahresber. Deutsch. Math.-Verein., vol. 25, pp. 114-117, 1916.
@ARTICLE{Schur16, volume = {25},
author = {Schur, I.},
title = {{Ü}ber die {K}ongruenz $x^m+y^m\equiv z^m (\text{mod} p)$},
journal = {Jahresber. Deutsch. Math.-Verein.},
year = {1916},
pages = {114--117},
jfmnumber={46.0193.02},
} -
[SV03] 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},
author = {Szab{ó},
Tibor and Vu, Van H.},
issn = {1042-9832},
mrclass = {05C80 (05C35 60C05)},
journal = {Random Structures Algorithms},
doi = {10.1002/rsa.10088},
volume = {23},
mrnumber = {1999036},
fjournal = {Random Structures \& Algorithms},
mrreviewer = {David B. Penman},
title = {Turán's theorem in sparse random graphs},
pages = {225--234},
year = {2003},
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},
author = {Szemer{é}di, E.},
issn = {0065-1036},
mrclass = {10L10},
journal = {Acta Arith.},
volume = {27},
mrnumber = {0369312},
note = {collection of articles in memory of {J}uri{\u\i} {V}ladimirovi{\v{c}} {L}innik},
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},
pages = {199--245},
year = {1975},
zblnumber={0303.10056},
} -
[Tu41] P. Turán, "Eine Extremalaufgabe aus der Graphentheorie," Mat. Fiz. Lapok, vol. 48, pp. 436-452, 1941.
@ARTICLE{Tu41, 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},
journal = {Mat. Fiz. Lapok},
year = {1941},
pages = {436--452},
zblnumber={0026.26903},
}
Full Article