Skip to content
DraconiticResearch
Search Sources API
190,332 studies31 sourcesUpdated 2 min ago
PreprintCC BY 4.0arXiv

A linear upper bound for Berge saturation numbers

  • Tianying Xie
Open at sourcePDFDOICite

Abstract

For a graph F with at least one edge, a k-uniform hypergraph is Berge-F-saturated if it contains no Berge-F, but adding any missing hyperedge creates a Berge-F. The saturation number satk(n,Berge−F) is the minimum number of edges in such a hypergraph on n vertices. English, Gordon, Graber, Methuku and Sullivan conjectured a linear upper bound for every fixed finite family of forbidden graphs. We prove the single-graph case: satk(n,Berge−F)=OF,k(n) for every fixed integer k≥2 and every fixed finite simple graph F with at least one edge. The proof combines a sparse construction with degree and matching arguments.

Related

  1. An Improved Upper Bound for Multicolour Ramsey Numbers
    Sunghyeon Jo
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. A General Upper Bound on Multicolor Ordered Ramsey Numbers
    Martin Balko, Klára Grinerová
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Saturation in three-uniform Berge hypergraphs: the five-star spectrum and the K4 saturation number
    XuanYu Cao, Yuan Lai, Chunxiang Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. A near-linear upper bound for Burr's conjecture
    Liangdong Fan, Junying Lu, Yaojun Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. A degree-linear upper bound for the Pólya exponent of forms with fixed arity
    Yulong Li, Colin Tan
    arXivPreprintCC BY-NC-SA 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{xie2026linear,
  title = {{A linear upper bound for Berge saturation numbers}},
  author = {Tianying Xie},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.11409},
  eprint = {2610.11409},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.11409},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A linear upper bound for Berge saturation numbers
AU  - Tianying Xie
PY  - 2026
DA  - 2026/10/08
PB  - arXiv
DO  - 10.48550/arxiv.2610.11409
UR  - https://arxiv.org/abs/2610.11409
AB  - For a graph F with at least one edge, a k-uniform hypergraph is Berge-F-saturated if it contains no Berge-F, but adding any missing hyperedge creates a Berge-F. The saturation number sat_k(n,Berge−F) is the minimum number of edges in such a hypergraph on n vertices. English, Gordon, Graber, Methuku and Sullivan conjectured a linear upper bound for every fixed finite family of forbidden graphs. We prove the single-graph case: sat_k(n,Berge−F)=O_F,k(n) for every fixed integer k≥2 and every fixed finite simple graph F with at least one edge. The proof combines a sparse construction with degree and matching arguments.
ER  -