Random Turán Problems for K s , t K_{s,t} Expansions

Jiaxi Nie, Sam Spiro · 2024

Read Random Turán Problems for K s , t K_{s,t} Expansions by Jiaxi Nie, Sam Spiro (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-09367.txt.

Description

Jiaxi Nie and Sam Spiro tackle random Turán problems for complete bipartite graph expansions. Their 2024 arXiv paper studies sparse random hypergraphs. An expansion grows each edge by adding new internal vertices. The question asks how large an expansion-free piece can be. Random hosts change the classic extremal picture.

Essentially tight bounds are proved for wide parameter ranges. The results break past a natural tight-tree barrier. Earlier random Turán work stopped at that barrier. Their methods also give optimal supersaturation for dense hosts. Supersaturation counts copies once density passes the threshold. The three-uniform expansion case is fully covered. Extremal combinatorics gains tools for random settings.

Catalog record

CREATORJiaxi Nie, Sam Spiro
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE91 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-09367

Browse the full library · About the Tower of Babel