On the boundedness of degenerate hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910508008865792 |
|---|---|
| author | Hou, Jianfeng Hu, Caiyun Li, Heng Liu, Xizhi Yang, Caihong Zhang, Yixiao |
| author_facet | Hou, Jianfeng Hu, Caiyun Li, Heng Liu, Xizhi Yang, Caihong Zhang, Yixiao |
| contents | We investigate the impact of a high-degree vertex in Turán problems for degenerate hypergraphs (including graphs). We say an $r$-graph $F$ is bounded if there exist constants $α, β>0$ such that for large $n$, every $n$-vertex $F$-free $r$-graph with a vertex of degree at least $α\binom{n-1}{r-1}$ has fewer than $(1-β) \cdot \mathrm{ex}(n,F)$ edges. The boundedness property is crucial for recent works~\cite{HHLLYZ23a,DHLY24} that aim to extend the classical Hajnal--Szemerédi Theorem and the anti-Ramsey theorems of Erdős--Simonovits--Sós.
We show that many well-studied degenerate hypergraphs, such as all even cycles, most complete bipartite graphs, and the expansion of most complete bipartite graphs, are bounded. In addition, to prove the boundedness of the expansion of complete bipartite graphs, we introduce and solve a Zarankiewicz-type problem for $3$-graphs, strengthening a theorem by Kostochka--Mubayi--Verstraëte~\cite{KMV15}. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_00427 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the boundedness of degenerate hypergraphs Hou, Jianfeng Hu, Caiyun Li, Heng Liu, Xizhi Yang, Caihong Zhang, Yixiao Combinatorics We investigate the impact of a high-degree vertex in Turán problems for degenerate hypergraphs (including graphs). We say an $r$-graph $F$ is bounded if there exist constants $α, β>0$ such that for large $n$, every $n$-vertex $F$-free $r$-graph with a vertex of degree at least $α\binom{n-1}{r-1}$ has fewer than $(1-β) \cdot \mathrm{ex}(n,F)$ edges. The boundedness property is crucial for recent works~\cite{HHLLYZ23a,DHLY24} that aim to extend the classical Hajnal--Szemerédi Theorem and the anti-Ramsey theorems of Erdős--Simonovits--Sós. We show that many well-studied degenerate hypergraphs, such as all even cycles, most complete bipartite graphs, and the expansion of most complete bipartite graphs, are bounded. In addition, to prove the boundedness of the expansion of complete bipartite graphs, we introduce and solve a Zarankiewicz-type problem for $3$-graphs, strengthening a theorem by Kostochka--Mubayi--Verstraëte~\cite{KMV15}. |
| title | On the boundedness of degenerate hypergraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2407.00427 |