A Phase Transition for Small Dense Subhypergraphs
En palabras de los autores
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 and , let be the smallest integer such that every -vertex -graph of average degree at least contains a nonempty subhypergraph on at most vertices with average degree at least . We show that the behavior of undergoes a phase transition at . We determine 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 and , our result implies a conjecture of Feige.
Apareció: martes, 22 de septiembre. arXiv. Preprint, todavía sin revisión por pares.