A Phase Transition for Small Dense Subhypergraphs
Abstract
The local--global principle, which concerns the relationship between local structure and global parameters, has attracted considerable attention in extremal combinatorics over the past few decades. In this paper, we study how global density forces small dense subhypergraphs in uniform hypergraphs. For fixed r≥3 and s>1, let tr(n,d,s) be the smallest integer t such that every n-vertex r-graph of average degree at least d contains a nonempty subhypergraph on at most t vertices with average degree at least s. We show that the behavior of tr(n,d,s) undergoes a phase transition at s=mainr/(r−1). We determine tr(n,d,s) and obtain asymptotically sharp bounds in several parameter regimes. This answers, up to polylogarithmic factors, a question of Feige and Wagner that was later restated as Problem~3.3 by Janzer, Sudakov and Tomon. In particular, when r=3 and s=2, our result implies a conjecture of Feige.
Related
- Spanning subhypergraphs with degree constraints
- Phase Transitions and Modulation in Dense Oscillatory Associative Memories
- Phase transition of random non-uniform hypergraphs
- Analytic description of the phase transition of inhomogeneous multigraphs
- A liquid vapor phase transition in quantum statistical mechanics
BibTeX
@misc{kuang2026phase,
title = {{A Phase Transition for Small Dense Subhypergraphs}},
author = {Peiru Kuang and Yan Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23720},
eprint = {2609.23720},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23720},
}
RIS
TY - UNPB
TI - A Phase Transition for Small Dense Subhypergraphs
AU - Peiru Kuang
AU - Yan Wang
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23720
UR - https://arxiv.org/abs/2609.23720
AB - The local--global principle, which concerns the relationship between local structure and global parameters, has attracted considerable attention in extremal combinatorics over the past few decades. In this paper, we study how global density forces small dense subhypergraphs in uniform hypergraphs. For fixed r≥3 and s>1, let t_r(n,d,s) be the smallest integer t such that every n-vertex r-graph of average degree at least d contains a nonempty subhypergraph on at most t vertices with average degree at least s. We show that the behavior of t_r(n,d,s) undergoes a phase transition at s=mainr/(r−1). We determine t_r(n,d,s) and obtain asymptotically sharp bounds in several parameter regimes. This answers, up to polylogarithmic factors, a question of Feige and Wagner that was later restated as Problem~3.3 by Janzer, Sudakov and Tomon. In particular, when r=3 and s=2, our result implies a conjecture of Feige.
ER -