×

zbMATH — the first resource for mathematics

Extension of a theorem of Moon and Moser on complete subgraphs. (English) Zbl 0532.05037
Let G denote a hypergraph with n vertices whose edges are k-tuples of vertices. Let \(N_ h\) denote the number of complete h-graphs with h vertices and \(\left( \begin{matrix} h\\ k\end{matrix} \right)\) edges contained in G. The author extends an argument of J. W. Moon and L. Moser [Publ. Math. Inst. Hungar. Acad. Sci., Ser. A 7, 283-286 (1962; Zbl 0114.012)] to give a lower bound for \(N_{h+1}\) in terms of \(N_ h\) and \(N_{h-1}\). From this he deduces an improved general upper bound on the number of edges possible in G if it is to contain no complete h-graph.
Reviewer: J.W.Moon

MSC:
05C35 Extremal problems in graph theory
05C65 Hypergraphs
PDF BibTeX XML Cite