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
- Yu Chen (ORCID: https://orcid.org/0000-0002-4696-9269)
- Jie Han (ORCID: https://orcid.org/0000-0002-2013-2962)
- Haoran Luo (ORCID: https://orcid.org/0000-0002-1951-6678)
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
- National Science Foundation
- National Natural Science Foundation of China
- Beijing Institute of Technology
- University of Illinois at Urbana-Champaign