Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Linearity of saturation for Berge hypergraphs
 
research article

Linearity of saturation for Berge hypergraphs

English, Sean
•
Gerbner, Daniel
•
Methuku, Abhishek  
Show more
May 1, 2019
European Journal Of Combinatorics

For a graph F, we say a hypergraph H is a Berge-F if it can be obtained from F by replacing each edge of F with a hyperedge containing it. We say a hypergraph is Berge-F-saturated if it does not contain a Berge-F, but adding any hyperedge creates a copy of a Berge-F. The k-uniform saturation number of Berge-F, sat(k)(n, Berge-F) is the fewest number of hyperedges in a Berge-F-saturated k-uniform hypergraph on n vertices. We show that sat(k)(n, Berge-F) = O(n) for all graphs F and uniformities 3 <= k <= 5, partially answering a conjecture of English, Gordon, Graber, Methuku, and Sullivan. We also extend this conjecture to Berge copies of hypergraphs. (C) 2019 Elsevier Ltd. All rights reserved.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.ejc.2019.02.002
Web of Science ID

WOS:000465187100014

Author(s)
English, Sean
Gerbner, Daniel
Methuku, Abhishek  
Tait, Michael
Date Issued

2019-05-01

Publisher

ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD

Published in
European Journal Of Combinatorics
Volume

78

Start page

205

End page

213

Subjects

Mathematics

•

turan problems

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
June 18, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/157721
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés