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
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