On the Thresholds of Degenerate Hypergraphs

  • Yu Chen
  • Jie Han
  • Haoran Luo

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.

Published
2026-11-20
How to Cite
Chen, Y., Han, J., & Luo, H. (2026). On the Thresholds of Degenerate Hypergraphs. The Electronic Journal of Combinatorics, 33(4), #P4.40. https://doi.org/10.37236/14914
Article Number
P4.40