×

Turán problems on non-uniform hypergraphs. (English) Zbl 1302.05128

Summary: A non-uniform hypergraph \(H=(V,E)\) consists of a vertex set \(V\) and an edge set \(E\subseteq 2^V\); the edges in \(E\) are not required to all have the same cardinality. The set of all cardinalities of edges in \(H\) is denoted by \(R(H)\), the set of edge types. For a fixed hypergraph \(H\), the Turán density \(\pi(H)\) is defined to be \(\lim_{n\to\infty}\max_{G_n}h_n(G_n)\), where the maximum is taken over all \(H\)-free hypergraphs \(G_n\) on \(n\) vertices satisfying \(R(G_n)\subseteq R(H)\), and \(h_n(G_n)\), the so called Lubell function, is the expected number of edges in \(G_n\) hit by a random full chain. This concept, which generalizes the Turán density of \(k\)-uniform hypergraphs, is motivated by recent work on extremal poset problems. The details connecting these two areas will be revealed in the end of this paper.
Several properties of Turán density, such as supersaturation, blow-up, and suspension, are generalized from uniform hypergraphs to non-uniform hypergraphs. Other questions such as “Which hypergraphs are degenerate?” are more complicated and don’t appear to generalize well. In addition, we completely determine the Turán densities of \(\{1,2\}\)-hypergraphs.

MSC:

05C65 Hypergraphs
05D05 Extremal set theory
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] M. Axenovich, J. Manske, and R. Martin, Q2-free families in the Boolean lattice, Order 30 (2013), 585-592. · Zbl 1282.06008
[2] Rahil Baber and John Talbot, New Tur´an densities for 3-graphs, Elect. J. Combin., (2012), P22, 21p. · Zbl 1244.05122
[3] J. Balogh, P. Hu, B. Lidick´y, and H. Liu, Upper bounds on the size of 4- and 6-cyclefree subgraphs of the hypercube, European J. Combin., 35 (2014), 75-85. · Zbl 1296.05096
[4] B. Bukh, Set families with a forbidden poset, Elect. J. Combin. 16 (2009), R142, 11p. · Zbl 1190.06004
[5] T. Carroll and G. O. H. Katona, Bounds on maximal families of sets not containing three sets with A ∪ B ⊂ C, A 6⊂ B, Order 25 (2008), 229-236. · Zbl 1171.05051
[6] F. Chung, L. Lu, An upper bound for the Tur´an number t3(n, 4). J. Combin. Theory Ser. A 87 (1999), no. 2, 381-389. · Zbl 0946.05063
[7] D. Conlon, An extremal theorem in the hypercube. Electron. J. Combin. 17 (2010), #R111. · Zbl 1193.05094
[8] A. De Bonis and G. O. H. Katona, Largest families without an r-fork, Order 24 (2007), 181-191. · Zbl 1127.05101
[9] A. De Bonis, G. O. H. Katona and K. J. Swanepoel, Largest family without A ∪ B ⊆ C ∩ D, J. Combin. Theory (Ser. A) 111 (2005), 331-336. the electronic journal of combinatorics 21(4) (2014), #P4.2231 · Zbl 1070.05077
[10] D. de Caen, Extension of a theorem of Moon and Moser on complete subgraphs. Ars Combin. 16 (1983), 5-10. · Zbl 0532.05037
[11] D. de Caen, The current status of Tur´an’s problem on hypergraphs. Extremal problems for finite sets (Visegr´ad, 1991), 187-197, Bolyai Soc. Math. Stud., 3, J´anos Bolyai Math. Soc., Budapest, 1994. · Zbl 0820.05042
[12] D. de Caen, D. L. Kreher, S.P. Radziszowski, and W.H. Mills, On the coverings t-sets with t + 1-sets: C(9, 5, 4) and C(10, 6, 5). Discrete Math. 92 (1991), 65-77. · Zbl 0758.05038
[13] P. Erd˝os, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898-902. · Zbl 0063.01270
[14] P. Erd˝os, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964), 183-190. · Zbl 0129.39905
[15] P. Erd˝os, On the combinatorial problems which I would like to see solved, Combinatorica 1 (1981), 25-42. · Zbl 0486.05001
[16] P. Erd˝os, M. Simonovits, Supersaturated graphs and hypergraphs. Combinatorica 3 (1983), 181-192. · Zbl 0529.05027
[17] P. Frankl, Z. F¨uredi, A new generalization of the Erd˝os-Ko-Rado theorem, Combinatorica 3 (1983), 341-349. · Zbl 0529.05001
[18] P. Frankl, Z. F¨uredi, An exact result for 3-graphs, Discrete Math. 50 (1984), 323-328. · Zbl 0538.05050
[19] Z. F¨uredi, D. Mubayi and O. Pikhurko, Quadruple systems with independent neighborhoods, J. Comb. Theory Ser. A 115 (2008), 1552-1560. · Zbl 1190.05036
[20] Z. F¨uredi and M. Simonovits, Triple systems not containing a Fano configuration, Combin. Probab. Comput. 14 (2005), 467-484. · Zbl 1075.05062
[21] G. Giraud, Majoration du nombre de Ramsey ternaire-bicolore en (4, 4). C. R. Acad. Sci. Paris S´er. A-B 269 (1969), A620-A622. · Zbl 0321.05005
[22] G. Giraud, Remarques sur deux probl‘emes extr´emaux. (French) [Remarks on two extremal problems] Discrete Math. 84 (1990), no. 3, 319-321. · Zbl 0714.05034
[23] J. R. Griggs and G. O. H. Katona, No four subsets forming an N , J. Combinatorial Theory (Ser. A) 115 (2008), 677-685. · Zbl 1170.05056
[24] J. R. Griggs and W.-T. Li, The partition method for poset-free families, Journal of Combinatorial Optimization, 25, Issue 4, (2013), 587-596. · Zbl 1273.90172
[25] J.R.GriggsandW.-T.Li,Poset-freefamiliesandLubell-boundedness, arXiv:1208.4241.
[26] J. R. Griggs, W.-T. Li, and L. Lu, Diamond-free Families, Journal of Combinatorial Theory Ser. A, 119 (2012), 310-322. · Zbl 1235.05144
[27] J. R. Griggs and L. Lu, On families of subsets with a forbidden subposet, Combinatorics, Probability, and Computing 18 (2009), 731-748. · Zbl 1215.05082
[28] G. Katona, T. Nemetz, M. Simonovits, On a problem of Tur´an in the theory of graphs. Mat. Lapok 15 (1964), 228-238. the electronic journal of combinatorics 21(4) (2014), #P4.2232 · Zbl 0138.19402
[29] G. O. H. Katona and T. G. Tarj´an, Extremal problems with excluded subgraphs in the n-cube, in: M. Borowiecki, J. W. Kennedy, and M. M. Sys lo (eds.) Graph Theory, Lag´ow, 1981, Lecture Notes in Math., 1018 84-93, Springer, Berlin Heidelberg New York Tokyo, 1983. · Zbl 0533.05035
[30] P. Keevash, Hypergraph Tur´an Problems, Surveys in Combinatorics, Cambridge University Press, 2011, 80-140.
[31] P. Keevash, The Tur´an problem for hypergraphs on fixed size, Electron. J. Combin. 12 (2005), Note 11, 6 pp. (electronic). · Zbl 1075.05084
[32] P. Keevash and B. Sudakov, The Tur´an number of the Fano plane, Combinatorica 25 (2005), 561-574. · Zbl 1089.05074
[33] P. Keevash and B. Sudakov, On a hypergraph Tur´an problem of Frankl, Combinatorica 25 (2005), 673-706. · Zbl 1089.05075
[34] L. Kramer, R. Martin, M. Young, On diamond-free subposets of the Boolean lattice, J. Combin. Theory Ser. A, 120, Issue 3, (2013), 545-560. · Zbl 1345.05112
[35] N. W. Lemons, Tur´an Problems for Hypergraphs, dissertation, Central European University, Budapest, Hungary, (2008).
[36] Linyuan Lu, On crown-free families of subsets, J. Combin. Theory Ser. A., 126, (2014) 216-231. · Zbl 1295.05251
[37] J. Manske and J. Shen, Three layer Q2-free families in the Boolean lattice, Order 30, Issue 2 (2013), 585-592. · Zbl 1282.06008
[38] K. Markstr¨om, Extremal graphs and bounds for the Tur´an density of the 4-uniform K5, Discrete Math. 309 no. 16, (2009), 5231-5234. · Zbl 1185.05108
[39] D. Mubayi, On hypergraphs with every four points spanning at most two triples, Electron. J. Combin. 10 (2003), no. 1, Note 10, 4 pp. (electronic). · Zbl 1023.05105
[40] D. Mubayi and Y. Zhao, Non-uniform Tur´an-type problems, J. Comb. Th. A, 111 (2004), 106-110. · Zbl 1066.05097
[41] O. Pikhurko, Exact computation of the hypergraph Tur´an function for expanded complete 2-graphs, Accepted by J. Combin. Theory Ser. B publication suspended for an indefinite time, see http://www.math.cmu.edu/ pikhurko/Copyright.html.
[42] A. Razborov, On 3-hypergraphs with forbidden 4-vertex configurations, SIAM J. Disc. Math. 24 (2010), 946-963. · Zbl 1223.05204
[43] A. Sidorenko, An analytic approach to extremal problems for graphs and hypergraphs. Extremal problems for finite sets (Visegr´ad, 1991), 423-455, Bolyai Soc. Math. Stud., 3, J´anos Bolyai Math. Soc., Budapest, 1994. · Zbl 0832.05062
[44] A. Sidorenko, On Tur´an numbers T (n, 5, 4) and numbers of monochromatic 4-cliques in 2-colored 3-graphs (in Russian). Voprosi Kibernetiki 64 (1980), 117-124. · Zbl 0508.05035
[45] A. Sidorenko, The method of quadratic forms in a combinatorial problem of Tur´an. (in Russian) Vestnik Moskov. Univ. Ser. I Mat. Mekh. 76 (1982), no. 1, 3-6. the electronic journal of combinatorics 21(4) (2014), #P4.2233
[46] A. Sidorenko, Upper bounds for Tur´an numbers, J. Combin. Theory Ser. A 77 (1997), no. 1, 134-147. · Zbl 0873.05003
[47] A. Sidorenko, What we know and what we do not know about Tur´an numbers. Graphs Combin. 11 (1995), no. 2, 179-199. · Zbl 0839.05050
[48] J. Talbot, Chromatic Tur´an problems and a new upper bound for the Tur´an density of K−4, Europ. J. Combin. 28 (2007), no. 8, 2125-2142. · Zbl 1128.05030
[49] H. T. Thanh, An extremal problem with excluded subposets in the Boolean lattice, Order 15 (1998), 51-57. · Zbl 0917.05077
[50] P. Tur´an, On an extremal problem in graph theory. Mat. Fiz. Lapok 48 (1941), 436-452. · Zbl 0026.26903
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.