An Improved Threshold for the Minimum Degree Kruskal-Katona Theorem for 3-Uniform Hypergraphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918481251794944 |
|---|---|
| author | Liu, Haorui Lu, Mei Zhang, Yi |
| author_facet | Liu, Haorui Lu, Mei Zhang, Yi |
| contents | Given a set $X$ and a sufficiently large integer $t$, let $\mathcal{F}$ be a family of $k$-subsets of $X$. The Kruskal-Katona theorem states that if $|\mathcal{F}|\geq \binom{t}{k}$, then $|\partial_{k-1}\mathcal{F}|\geq\binom{t}{k-1}$. The minimum degree version of this problem asks: if $δ(\mathcal{F})\geq \binom{t}{k-1}$, how small can $|\partial_{k-1}\mathcal{F}|$ be? In this article, for the case $k=3$, we prove that every extremal graph for this problem contains an isolated copy of $K_{t+1}^3$ whenever $|X| \geq ct^2 + o(t^2)$, with the constant $c = 1 + \sqrt{928/33}$. Our proof uses a graph transformation that regularizes the neighborhood structure of extremal graphs, reducing the problem to a counting argument on the neighbors of a disjoint clique family. This improves a result of Füredi and Zhao [SIAM J.\ Discrete Math.\ 36(4), 2022], reducing the threshold from $O(t^3)$ to $O(t^2)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_02594 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Improved Threshold for the Minimum Degree Kruskal-Katona Theorem for 3-Uniform Hypergraphs Liu, Haorui Lu, Mei Zhang, Yi Combinatorics 05D05, 05C65, 05C35 Given a set $X$ and a sufficiently large integer $t$, let $\mathcal{F}$ be a family of $k$-subsets of $X$. The Kruskal-Katona theorem states that if $|\mathcal{F}|\geq \binom{t}{k}$, then $|\partial_{k-1}\mathcal{F}|\geq\binom{t}{k-1}$. The minimum degree version of this problem asks: if $δ(\mathcal{F})\geq \binom{t}{k-1}$, how small can $|\partial_{k-1}\mathcal{F}|$ be? In this article, for the case $k=3$, we prove that every extremal graph for this problem contains an isolated copy of $K_{t+1}^3$ whenever $|X| \geq ct^2 + o(t^2)$, with the constant $c = 1 + \sqrt{928/33}$. Our proof uses a graph transformation that regularizes the neighborhood structure of extremal graphs, reducing the problem to a counting argument on the neighbors of a disjoint clique family. This improves a result of Füredi and Zhao [SIAM J.\ Discrete Math.\ 36(4), 2022], reducing the threshold from $O(t^3)$ to $O(t^2)$. |
| title | An Improved Threshold for the Minimum Degree Kruskal-Katona Theorem for 3-Uniform Hypergraphs |
| topic | Combinatorics 05D05, 05C65, 05C35 |
| url | https://arxiv.org/abs/2605.02594 |