On the Thresholds of Degenerate Hypergraphs

Fix $d>0,\alpha,\epsilon\in(0,1]$. An $n$-vertex $k$-uniform hypergraph $G$ is $(d,\alpha,\epsilon)$-degenerate if $m_1(G)\le{d+\frac{d}{\log_2 n}}$ and $e\left(G[U]\right)\le{d\left(|U|-1\right)-\alpha}$ for every subset $U\subseteq{V(G)}$ of size $2\le|U|\le{\epsilon n}$. These hypergraphs encompass several natural (hyper)graph classes, including $d$-degenerate hypergraphs for integers $d\ge2$, planar graphs, and powers of cycles. In this paper, we consider the appearance threshold of a $(d,\alpha,\epsilon)$-degenerate hypergraph with bounded maximum degree in the Erdős–Rényi model. We show that $G^{(k)}(n,p_n)$ contains $G_n$ with high probability whenever $p_n=\omega(n^{-1/d})$, improving previous results of Riordan and Kelly–Müyesser–Pokrovskiy.

Authors

Publication Details

Journal
The Electronic Journal of Combinatorics
Published
2026-11-20
DOI
https://doi.org/10.37236/14914
Citations
4
Primary Topic
Limits and Structures in Graph Theory
Type
article
Field-Weighted Citation Impact
2.44

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

On the Thresholds of Degenerate Hypergraphs

Yu Chen, Jie Han, Haoran Luo
4 citations
The Electronic Journal of Combinatorics
Limits and Structures in Graph Theory
2.44
article

On the Thresholds of Degenerate Hypergraphs

Yu Chen, Jie Han, Haoran Luo
article en
4 citations

Abstract

Fix $d>0,\alpha,\epsilon\in(0,1]$. An $n$-vertex $k$-uniform hypergraph $G$ is $(d,\alpha,\epsilon)$-degenerate if $m_1(G)\le{d+\frac{d}{\log_2 n}}$ and $e\left(G[U]\right)\le{d\left(|U|-1\right)-\alpha}$ for every subset $U\subseteq{V(G)}$ of size $2\le|U|\le{\epsilon n}$. These hypergraphs encompass several natural (hyper)graph classes, including $d$-degenerate hypergraphs for integers $d\ge2$, planar graphs, and powers of cycles. In this paper, we consider the appearance threshold of a $(d,\alpha,\epsilon)$-degenerate hypergraph with bounded maximum degree in the Erdős–Rényi model. We show that $G^{(k)}(n,p_n)$ contains $G_n$ with high probability whenever $p_n=\omega(n^{-1/d})$, improving previous results of Riordan and Kelly–Müyesser–Pokrovskiy.

The Electronic Journal of CombinatoricsVol. 33(4)
National Science Foundation, National Natural Science Foundation of China, Beijing Institute of Technology, University of Illinois at Urbana-Champaign
Openalex Percentile: Top 17%
Limits and Structures in Graph Theory
2.44
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon