On the weight of Berge-\(F\)-free hypergraphs
From MaRDI portal
Publication:2327220
zbMath1422.05073arXiv1902.03398MaRDI QIDQ2327220
Cory Palmer, Dániel Gerbner, Sean English, Abhishek Methuku
Publication date: 14 October 2019
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Abstract: For a graph $F$, we say a hypergraph is a Berge-$F$ if it can be obtained from $F$ by replacing each edge of $F$ with a hyperedge containing it. A hypergraph is Berge-$F$-free if it does not contain a subhypergraph that is a Berge-$F$. The weight of a non-uniform hypergraph $mathcal{H}$ is the quantity $sum_{h in E(mathcal{H})} |h|$. Suppose $mathcal{H}$ is a Berge-$F$-free hypergraph on $n$ vertices. In this short note, we prove that as long as every edge of $mathcal{H}$ has size at least the Ramsey number of $F$ and at most $o(n)$, the weight of $mathcal{H}$ is $o(n^2)$. This result is best possible in some sense. Along the way, we study other weight functions, and strengthen results of Gerbner and Palmer; and Gr'osz, Methuku and Tompkins.
Full work available at URL: https://arxiv.org/abs/1902.03398
File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)
Cites Work
- Hypergraphs with no cycle of length 4
- 3-uniform hypergraphs avoiding a given odd cycle
- On 3-uniform hypergraphs without a cycle of a given length
- Forbidden Berge hypergraphs
- Hypergraph extensions of the Erdős-Gallai theorem
- The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
- General lemmas for Berge-Turán hypergraph problems
- Turán numbers for Berge-hypergraphs and related extremal problems
- Asymptotics for the Turán number of Berge-\(K_{2,t}\)
- Counting copies of a fixed subgraph in \(F\)-free graphs
- Hypergraphs with No Cycle of a Given Length
- Triangle-Free Hypergraphs
- Extremal Results for Berge Hypergraphs
Related Items (3)
$t$-Wise Berge and $t$-Heavy Hypergraphs ⋮ The Turán number of Berge book hypergraphs ⋮ Hypergraph based Berge hypergraphs
This page was built for publication: On the weight of Berge-\(F\)-free hypergraphs
