×

zbMATH — the first resource for mathematics

Asymptotic solution of a Turán-type problem. (English) Zbl 0724.05070
Let f(n,k) be the maximum number of edges in a 2k-uniform hypergraph on n vertices which does not contain edges of the form \(A\cup B\), \(A\cup C\), \(B\cup C\) where A, B and C are disjoint k-element sets. The following theorem (related to a problem of B. Bollabás) is proved: \[ (\frac{1}{2}+\frac{c}{n^ 2})/\left( \begin{matrix} n\\ 2k\end{matrix} \right)<f(n,k)<(\frac{1}{2}+\frac{2k}{n-4k})\left( \begin{matrix} n\\ 2k\end{matrix} \right), \] where \(c=c(k)>0\) is a constant. Finally the structure of an extremal hypergraph is conjectured.
Reviewer: K.Engel (Rostock)

MSC:
05D05 Extremal set theory
05C35 Extremal problems in graph theory
05C65 Hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bollobás, B.: Three-graphs without two triples whose symmetric difference is contained in a third. Discrete Math.8, 21–24 (1974) · Zbl 0291.05114
[2] Caen, D. de: Uniform hypergraphs with no blocks containing the symmetric difference of any two other blocks. Proc. 16-th S-E Conf. Congressus Num.47, 249–253 (1985)
[3] Erdös, P.: On extremal problems on graphs and generalized graphs, Isr. J. Math.2, 183–190 (1964) · Zbl 0129.39905
[4] Frankl, P., Füredi, Z.: Union-free families of sets and probability theory, Europ. J. Comb. Errata, ibid p. 3955, 127–131 (1984) · Zbl 0546.05049
[5] Frankl, P., Füredi, Z.: An extremal problem whose solutions are the blow-ups of the small Witt-designs. J. Comb. Theory52, 129–147 (1989) · Zbl 0731.05030
[6] Frankl, P., Füredi, Z.: A new generalization of the Erdös-Ko-Rado theorem. Combinatorica3, 341–349 (1983) · Zbl 0529.05001
[7] Katona, G.O.H.: Extremal problems for hypergraphs, in ”Combinatorics” Math. Cent. Tracts.56, Vol. II, pp. 13–42 (1974) · Zbl 0298.05142
[8] Katona, G.O.H., Nemetz, T., Simonovits, M.: On a graph problem of Turán, Mat. Lapok15, 228–238 (1964) (Hungarian, English summary) · Zbl 0138.19402
[9] Mantel, W.: Problem 28. Wiskundige Opgaven10, 60–61 (1907)
[10] Sidorenko, A.F.: Solution of a problem of Bollobás on 4-graphs. Mat. Zametki41, 433–455 (1987)
[11] Turán, P.: Research problem, Közl. MTA Mat. Kut. Int.6, 417–423 (1961)
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.