Hypergraph saturation irregularities

MaRDI QIDQ1753084zbMATH OpenFDO

Authors Natalie C. Behague

Publication date 25 May 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.05799, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p11

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

hypergraphssaturation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Abstract: Let $mathcalF$ be a family of $r$-graphs. An $r$-graph $G$ is called $mathcalF$-saturated if it does not contain any members of $mathcalF$ but adding any edge creates a copy of some $r$-graph in $mathcalF$. The saturation number $operatornamesat(mathcalF,n)$ is the minimum number of edges in an $mathcalF$-saturated graph on $n$ vertices. We prove that there exists a finite family $mathcalF$ such that $operatornamesat(mathcalF,n)/n^{r-1}$ does not tend to a limit. This settles a question of Pikhurko.

Review text

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)].

Recommendations

• scientific article; zbMATH DE number 2192110
• scientific article; zbMATH DE number 4081590
• A survey of minimum saturated graphs
• Minimizing the numbers of cliques and cycles of fixed size in an \(F\)-saturated graph
• Saturated r-uniform hypergraphs

Cites work

• A survey of minimum saturated graphs
• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 4081590 (Why is no real title available?)
• scientific article; zbMATH DE number 2192110 (Why is no real title available?)
• On generalized graphs
• Saturated graphs with minimal number of edges
• The Minimum Size of Saturated Hypergraphs

Cited in

(9)

• Saturation of Berge hypergraphs
• Saturation number of \(tK_{l,l,l}\) in the complete tripartite graph
• Microthesis: Hypergraph saturation irregularities
• scientific article; zbMATH DE number 4081590 (Why is no real title available?)
• scientific article; zbMATH DE number 2192110 (Why is no real title available?)
• A survey of minimum saturated graphs
• Weakly saturated hypergraphs and a conjecture of Tuza
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Hyperbolic saturation

This page was built for publication: Hypergraph saturation irregularities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1753084)