Hypergraph saturation irregularities (Q1753084)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 6873162
Language Label Description Also known as
default for all languages
No label defined
    English
    Hypergraph saturation irregularities
    scientific article; zbMATH DE number 6873162

      Statements

      Hypergraph saturation irregularities (English)
      0 references
      0 references
      25 May 2018
      0 references
      Summary: Let \(\mathcal{F}\) be a family of \(r\)-graphs. An \(r\)-graph \(G\) is called \(\mathcal{F}\)-saturated if it does not contain any members of \(\mathcal{F}\) but adding any edge creates a copy of some \(r\)-graph in \(\mathcal{F}\). The saturation number \(\operatorname{sat}(\mathcal{F},n)\) is the minimum number of edges in an \(\mathcal{F}\)-saturated graph on \(n\) vertices. We prove that there exists a finite family \(\mathcal{F}\) such that \(\operatorname{sat}(\mathcal{F},n) / n^{r-1}\) does not tend to a limit. This settles a question of \textit{O. Pikhurko} [Comb. Probab. Comput. 8, No. 5, 483--492 (1999; Zbl 0938.05035)].
      0 references
      hypergraphs
      0 references
      saturation
      0 references

      Identifiers