Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-07T13:27:23.239Z Has data issue: false hasContentIssue false
  • English
  • Français

The Minimum Size of Saturated Hypergraphs

Published online by Cambridge University Press:  01 September 1999

OLEG PIKHURKO
OLEG PIKHURKO
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Cambridge University, Cambridge CB2 1SB, England (e-mail: O.Pikhurko@dpmms.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let [Fscr] be a family of forbidden k-hypergraphs (k-uniform set systems). An [Fscr]-saturated hypergraph is a maximal k-uniform set system not containing any member of [Fscr]. As the main result we prove that, for any finite family [Fscr], the minimum number of edges of an [Fscr]-saturated hypergraph is O(nk−1). In particular, this implies a conjecture of Tuza. Some other related results are presented.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 8 , Issue 5 , September 1999 , pp. 483 - 492
Copyright
1999 Cambridge University Press