On the minimum size of tight hypergraphs. (English) Zbl 0776.05079

Summary: A \(k\)-graph, \(H=(V,E)\), is tight if for every surjective mapping \(f:V\to\{1,\dots,k\}\) there exists an edge \(\alpha\in E\) such that \(f|_ \alpha\) is injective. Clearly, 2-graphs are tight if and only if they are connected. Bounds for the minimum number \(\varphi^ k_ n\) of edges in a tight \(k\)-graph with \(n\) vertices are given. We conjecture that \(\varphi^ 3_ n=\lceil n(n-2)/3\rceil\) for every \(n\) and prove the equality when \(2n+1\) is prime. From the examples, minimal embeddings of complete graphs into surfaces follow.


05C65 Hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs
05C05 Trees
Full Text: DOI


[1] , and , On tight kgraphs. In preparation.
[2] , and , Tight and untight triangulated surfaces. Preprint.
[3] Rudiments of Ramsey Theory. AMS, Providence, RI (1981).
[4] Iwaniec, Monatsh. Math. 98 pp 115– (1984)
[5] Topological and algebraic methods in graph theory; in Graph theory and related topics. Proceedings of Conference in Honour of W.T. Tutte, Waterloo, Ontario, 1977. Academic Press, New York (1979) 1–14.
[6] The acyclic disconnection of a digraph. In preparation. · Zbl 0928.05033
[7] Map Color Theorem. Die Grundlehren der Mathematischen Wissenchaften, Band 209, Springer-Verlag, Berlin (1974).
[8] Schur, Jber. Deutsche Math. Verein. 25 pp 114– (1916)
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.