EUVIMEDOpdag EUVIMED
Crossref

On the Thresholds of Degenerate Hypergraphs

Yu Chen, Jie Han, Haoran Luo

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.

AbstractBibliografiske oplysningerCiteRelated studies

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}
}
Start for free →