Hypergraph saturation irregularities (Q1753084)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Hypergraph saturation irregularities
scientific article

    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