The number of C2-free graphs

Advances in Mathematics - Tập 298 - Trang 534-580 - 2016
Robert Morris1, David Saxton1
1IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brazil

Tài liệu tham khảo

Alon, 1999, Norm-graphs: variations and applications, J. Combin. Theory Ser. B, 76, 280, 10.1006/jctb.1999.1906 Balogh, 2004, On the number of graphs without forbidden subgraph, J. Combin. Theory Ser. B, 91, 1, 10.1016/j.jctb.2003.08.001 Balogh, 2009, The typical structure of graphs without given excluded subgraphs, Random Structures Algorithms, 34, 305, 10.1002/rsa.20242 Balogh, 2011, The fine structure of octahedron-free graphs, J. Combin. Theory Ser. B, 101, 67, 10.1016/j.jctb.2010.11.001 Balogh, 2015, Independent sets in hypergraphs, J. Amer. Math. Soc., 28, 669, 10.1090/S0894-0347-2014-00816-X Balogh, 2010, Almost all C4-free graphs have fewer than (1−ε)ex(n,C4) edges, SIAM J. Discrete Math., 24, 1011, 10.1137/09074989X Balogh, 2011, The number of Km,m-free graphs, Combinatorica, 31, 131, 10.1007/s00493-011-2610-y Balogh, 2011, The number of Ks,t-free graphs, J. Lond. Math. Soc., 83, 368, 10.1112/jlms/jdq086 Benson, 1966, Minimal regular graphs of girths eight and twelve, Canad. J. Math., 18, 1091, 10.4153/CJM-1966-109-8 Blagojević, 2013, Turán numbers for Ks,t-free graphs: topological obstructions and algebraic constructions, Israel J. Math., 197, 199, 10.1007/s11856-012-0184-z Bollobás, 2002 Bondy, 1974, Cycles of even length in graphs, J. Combin. Theory Ser. B, 16, 97, 10.1016/0095-8956(74)90052-5 Brown, 1966, On graphs that do not contain a Thomsen graph, Canad. Math. Bull., 9, 281, 10.4153/CMB-1966-036-2 Bukh, 2016, Random algebraic construction of extremal graphs, Bull. Lond. Math. Soc. Bukh, 2016, A bound on the number of edges in graphs without an even cycle, Combin. Probab. Comput. Collares Neto, 2016, Maximum-size antichains in random set-systems, Random Structures Algorithms, 10.1002/rsa.20647 Conlon, 2016, Combinatorial theorems in sparse random sets, Ann. of Math., 10.4007/annals.2016.184.2.2 Dellamonica, 2016, On the number of Bh-sets, Combin. Probab. Comput., 25, 108, 10.1017/S0963548315000206 Dellamonica, 2016, The number of B3-sets of a given cardinality, J. Combin. Theory Ser. A, 142, 44, 10.1016/j.jcta.2016.03.004 D. Dellamonica, Y. Kohayakawa, S. Lee, V. Rödl, W. Samotij, The number of Bh-sets of a given cardinality, submitted for publication. Erdős, 1938, 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, 2, 74 Erdős, 1965, Extremal problems in graph theory, 29 Erdős, 1976, Asymptotic enumeration of Kn-free graphs, vol. 17, 19 Erdős, 1986, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin., 2, 113, 10.1007/BF01788085 Erdős, 1966, On a problem of graph theory, Studia Sci. Math. Hungar., 1, 215 Erdős, 1966, A limit theorem in graph theory, Studia Sci. Math. Hungar., 1, 51 Erdős, 1982, Compactness results in extremal graph theory, Combinatorica, 2, 275, 10.1007/BF02579234 Erdős, 1984, Cube-supersaturated graphs and related problems, 203 Erdős, 1946, On the structure of linear graphs, Bull. Amer. Math. Soc., 52, 1087, 10.1090/S0002-9904-1946-08715-7 R. Faudree, M. Simonovits, Cycle-supersaturated graphs, in preparation. Füredi, 2013, The history of degenerate (bipartite) extremal graph problems, vol. 25, 169 Füredi, 1996, New asymptotics for bipartite Turań numbers, J. Combin. Theory Ser. A, 75, 141, 10.1006/jcta.1996.0067 Füredi, 2006, On the Turán number for the hexagon, Adv. Math., 203, 476, 10.1016/j.aim.2005.04.011 Haxell, 1995, Turán's extremal problem in random graphs: forbidding even cycles, J. Combin. Theory Ser. B, 64, 273, 10.1006/jctb.1995.1035 D. Kleitman, D. Wilson, On the number of graphs which lack small cycles, 1996, manuscript. Kleitman, 1982, On the number of graphs without 4-cycles, Discrete Math., 41, 167, 10.1016/0012-365X(82)90204-7 Kohayakawa, 1998, An extremal problem for random graphs and the number of graphs with large even-girth, Combinatorica, 18, 101, 10.1007/PL00009804 Kohayakawa, 2015, The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers, Random Structures Algorithms, 46, 1, 10.1002/rsa.20496 Kolaitis, 1987, Kℓ+1-free graphs: asymptotic structure and a 0–1 law, Trans. Amer. Math. Soc., 303, 637 Kollár, 1996, Norm-graphs and bipartite Turán numbers, Combinatorica, 16, 399, 10.1007/BF01261323 Kővári, 1954, On a problem of K. Zarankiewicz, Colloq. Math., 3, 50, 10.4064/cm-3-1-50-57 Kreuter, 1994 Lazebnik, 1994, Properties of certain families of 2k-cycle free graphs, J. Combin. Theory Ser. B, 60, 10.1006/jctb.1994.1020 Nagle, 2006, Extremal hypergraph problems and the regularity method, vol. 26, 247 Pikhurko, 2012, A note on the Turán function of even cycles, Proc. Amer. Math. Soc., 140, 3687, 10.1090/S0002-9939-2012-11274-2 Prömel, 1992, The asymptotic number of graphs not containing a fixed color-critical subgraph, Combinatorica, 12, 463, 10.1007/BF01305238 Rödl, 2013, Extremal results in random graphs, vol. 25, 535 Saxton, 2012 Saxton, 2015, Hypergraph containers, Invent. Math., 201, 1, 10.1007/s00222-014-0562-8 Schacht, 2016, Extremal results for random discrete structures, Ann. of Math., 184, 331, 10.4007/annals.2016.184.2.1 Turán, 1941, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok, 48, 436 Verstraëte, 2000, On arithmetic progressions of cycle lengths in graphs, Combin. Probab. Comput., 9, 369, 10.1017/S0963548300004478 Wenger, 1991, Extremal graphs with no C4, C6, or C10, J. Combin. Theory Ser. B, 52, 113, 10.1016/0095-8956(91)90097-4