×

zbMATH — the first resource for mathematics

An exact Turán result for the generalized triangle. (English) Zbl 1175.05137
In a \(k\)-uniform hypergraph three edges \(D_1,D_2, D_3\) form a generalized triangle if \(D_1\triangle D_2 \subseteq D_3.\) Let \({\mathcal T}_k\) denote the set of all \(k\)-graphs with generalized triangles. Let \(\Sigma_k \subset {\mathcal T}_k\) contain all \(k\)-graphs with the special generalized triangle \(| D_1\cap D_2| =k-1.\) The exact value of the Turán function ex\((n,{\mathcal T}_k)\) was computed for \(k=3\) by B. Bollobás [Discrete Math. 8, 21–24 (1974; Zbl 0291.05114)] and for \(k=4\) by A. F. Sidorenko [Math. Notes 41, 247–259 (1987; Zbl 0677.05064)]. P. Frankl and Z. Füredi [J. Comb. Theory, Ser. A 52, No. 1, 129–147 (1989; Zbl 0731.05030)] studied the Turán problem for the special \(k\)-graph \(T_k\in \Sigma_k\) where \(| (D_1\cup D_2)\cap D_3| =2.\) In 1989 they conjectured that there exists a constant \(n_0(k)\) such that ex\((n,T_k)=\)ex\((n,\Sigma_k)\) for all \(n> n_0(k).\) This conjecture is known to be true for \(k=3.\) This lengthy, rather involved paper under review proves the conjecture for the case \(k=4\).

MSC:
05D05 Extremal set theory
05C35 Extremal problems in graph theory
05C65 Hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] B. Bollobás: Three-graphs without two triples whose symmetric difference is contained in a third, Discrete Math. 8 (1974), 21–24. · Zbl 0291.05114 · doi:10.1016/0012-365X(74)90105-8
[2] D. de Caen: Uniform hypergraphs with no block containing the symmetric difference of any two other blocks, Congres. Numer. 47 (1985), 249–253.
[3] G. Elek and B. Szegedy: Limits of hypergraphs, removal and regularity lemmas. A non-standard approach; submitted (2007), arXiv:0705.2179.
[4] P. Erdos and M. Simonovits: Supersaturated graphs and hypergraphs, Combinatorica 3(2) (1983), 181–192. · Zbl 0529.05027 · doi:10.1007/BF02579292
[5] P. Frankl and Z. Füredi: A new generalization of the Erdos-Ko-Rado theorem, Combinatorica 3(3–4) (1983), 341–349. · Zbl 0529.05001 · doi:10.1007/BF02579190
[6] P. Frankl and Z. Füredi: Extremal problems whose solutions are the blowups of the small Witt-designs, J. Combin. Theory Ser. (A) 52 (1989), 129–147. · Zbl 0731.05030 · doi:10.1016/0097-3165(89)90067-8
[7] Z. Füredi and M. Simonovits: Triple systems not containing a Fano configuration, Combin. Prob. Computing 14 (2005), 467–488. · Zbl 1075.05062 · doi:10.1017/S0963548305006784
[8] W. T. Gowers: Hypergraph regularity and the multidimensional Szemerédi’s theorem, submitted (2007), arXiv:0710.3032.
[9] G. O. H. Katona: Extremal problems for hypergraphs, Combinatorics vol. 56, Math. Cent. Tracts, 1974, pp. 13–42. · Zbl 0298.05142
[10] G. O. H. Katona, T. Nemetz and M. Simonovits: On a graph problem of Turán (In Hungarian), Mat. Fiz. Lapok 15 (1964), 228–238. · Zbl 0138.19402
[11] P. Keevash and D. Mubayi: Stability results for cancellative hypergraphs, J. Combin. Theory Ser. (B) 92 (2004), 163–175. · Zbl 1052.05051 · doi:10.1016/j.jctb.2004.05.003
[12] P. Keevash and B. Sudakov: The Turán number of the Fano plane, Combinatorica 25(5) (2005), 561–574. · Zbl 1089.05074 · doi:10.1007/s00493-005-0034-2
[13] P. Keevash and B. Sudakov: On a hypergraph Turán problem of Frankl, Combinatorica 25(6) (2005), 673–706. · Zbl 1089.05075 · doi:10.1007/s00493-005-0042-2
[14] W. Mantel: Problem 28, Winkundige Opgaven 10 (1907), 60–61.
[15] D. Mubayi and O. Pikhurko: A new generalization of Mantel’s theorem to k-graphs, J. Combin. Theory Ser. (B) 97 (2007), 669–678. · Zbl 1153.05032 · doi:10.1016/j.jctb.2006.11.003
[16] B. Nagle, V. Rödl and M. Schacht: The counting lemma for regular k-uniform hypergraphs, Random Struct. Algorithms 28 (2005), 113–179. · Zbl 1093.05045 · doi:10.1002/rsa.20117
[17] O. Pikhurko: Exact computation of the hypergraph Turán function for expanded complete 2-graphs, arXiv:math/0510227, accepted by J. Comb. Th. Ser. (B). The publication is suspended because of a disagreement over copyright, see http://www.math.cmu.edu/:_pikhurko/Copyright.html , 2005.
[18] V. Rödl and J. Skokan: Regularity lemma for k-uniform hypergraphs, Random Struct. Algorithms 25 (2004), 1–42. · Zbl 1046.05042 · doi:10.1002/rsa.20017
[19] V. Rödl and J. Skokan: Applications of the regularity lemma for uniform hypergraphs, Random Struct. Algorithms 28 (2006), 180–194. · Zbl 1087.05031 · doi:10.1002/rsa.20108
[20] J. B. Shearer: A new construction for cancellative families of sets, Electronic J. Combin. 3 (1996), 3 pp.
[21] A. F. Sidorenko: The maximal number of edges in a homogeneous hypergraph containing no prohibited subgraphs, Math Notes 41 (1987), 247–259, Translated from Mat. Zametki. · Zbl 0677.05064
[22] T. Tao: A variant of the hypergraph removal lemma, J. Combin. Theory Ser. (A) 113 (2006), 1257–1280. · Zbl 1105.05052 · doi:10.1016/j.jcta.2005.11.006
[23] P. Turán: On an extremal problem in graph theory (in Hungarian), Mat. Fiz. Lapok 48 (1941), 436–452.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.