On the Thresholds of Degenerate Hypergraphs
The Electronic Journal of Combinatorics · 2026-11-20 · 33 (4)
DOI: 10.37236/14914 ↗At a glance
Journal article in The Electronic Journal of Combinatorics, published online on 2026-11-20. Written by Yu Chen and 2 co-authors.
Abstract (original language)
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.
Cite
APA
Chen, Y., Han, J., & Luo, H. (2026). On the Thresholds of Degenerate Hypergraphs. The Electronic Journal of Combinatorics, 33(4). https://doi.org/10.37236/14914
Vancouver
Chen Y, Han J, Luo H. On the Thresholds of Degenerate Hypergraphs. The Electronic Journal of Combinatorics. 2026;33(4). doi:10.37236/14914
BibTeX
@article{Chen2026,
author = {Chen, Yu and Han, Jie and Luo, Haoran},
title = {On the Thresholds of Degenerate Hypergraphs},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {4},
doi = {10.37236/14914}
}
EUVIMED