×

zbMATH — the first resource for mathematics

On the maximal number of edges in a homogeneous hypergraph not containing prohibited subgraphs. (English. Russian original) Zbl 0677.05064
Math. Notes 41, 247-259 (1987); translation from Mat. Zametki 41, No. 3, 433-455 (1987).
The author proves that the maximal number of edges of a 4-uniform hypergraph with n vertices without two edges whose symmetric difference is contained in a third is equal to \(\lfloor n/4\rfloor \lfloor (n+1)/4\rfloor \lfloor (n+2)/4\rfloor \lfloor (n+3)/4\rfloor\) and that the extremal hypergraph is unique up to isomorphism. This settles a conjecture of B. Bollobás, who solved the corresponding problem for 3-uniform hypergraphs [Discrete Math. 8, 21-24 (1974; Zbl 0291.05114)].

MSC:
05C65 Hypergraphs
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] W. Mantel, Vraagstuk XXVIII, Wiskundige Opgevan met de Oplossingen,10, No. 1, 60-61 (1907).
[2] P. Turan, ?Egy grafelmeleti szelsöerekfeladatrol,? Mat. Fiz. Lapok,48, No. 3, 436-453 (1941).
[3] P. Erdös, ?On the combinatorial problems which I would most like to see solved,? Combinatorica,1, No. 1, 25-42 (1981). · Zbl 0486.05001 · doi:10.1007/BF02579174
[4] B. Bollobas, ?Three-graphs without two triples whose symmetric difference is contained in a third,? Discrete Math.,8, No. 1, 21-24 (1974). · Zbl 0291.05114 · doi:10.1016/0012-365X(74)90105-8
[5] P. Erdös and M. Simonovits, ?Compactness results in extremal graph theory,? Combinatorica,2, No. 3, 275-288 (1982). · Zbl 0508.05043 · doi:10.1007/BF02579234
[6] M. Simonovits, Extremal Graph Theory. Selected Topics in Graph Theory, Academic Press, New York (1983), pp. 161-200. · Zbl 0531.05037
[7] W. G. Brown and M. Simonovits, ?Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures,? Discrete Math.,48, Nos. 2-3, 147-162 (1984). · Zbl 0541.05035 · doi:10.1016/0012-365X(84)90178-X
[8] T. S. Motzkin and E. G. Straus, ?Maxima for graphs and a new proof of a theorem of Turan,? Can. J. Math.,17, No. 4, 533-540 (1965). · Zbl 0129.39902 · doi:10.4153/CJM-1965-053-6
[9] P. Erdos and M. Simonovits, ?A limit theorem in graph theory,? Stud. Math. Hung.,1, Nos. 1-2, 51-57 (1966).
[10] P. Cameron and J. van Lindt, The Theory of Graphs, Coding Theory, and Block-Schemes [Russian translation], Nauka, Moscow (1982).
[11] K. A. Rybnikova (ed.), Combinatorial Analysis. Problems and Exercises [in Russian], Nauka, Moscow (1982).
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.