Pith. sign in

On the boundedness of degenerate hypergraphs

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

We investigate the impact of a high-degree vertex in Tur\'{a}n problems for degenerate hypergraphs (including graphs). We say an $r$-graph $F$ is bounded if there exist constants $\alpha, \beta>0$ such that for large $n$, every $n$-vertex $F$-free $r$-graph with a vertex of degree at least $\alpha \binom{n-1}{r-1}$ has fewer than $(1-\beta) \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\'{e}di Theorem and the anti-Ramsey theorems of Erd\H{o}s--Simonovits--S\'{o}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\"{e}te~\cite{KMV15}.

fields

math.CO 1

years

2025 1

verdicts

CONDITIONAL 1

representative citing papers

Tiling $H$ in dense graphs

math.CO · 2025-01-20 · conditional · novelty 7.0

The asymptotic maximum number of edges in a graph with H-matching number below beta n is determined for the H-shaped tree, refuting Lang's conjecture.

citing papers explorer

Showing 1 of 1 citing paper.

  • Tiling $H$ in dense graphs math.CO · 2025-01-20 · conditional · none · ref 4 · internal anchor

    The asymptotic maximum number of edges in a graph with H-matching number below beta n is determined for the H-shaped tree, refuting Lang's conjecture.