An absolute constant C suffices for bounded-degree tree universality in G(n, C ln n/n), and cycle-factor universality is optimal up to constants via depth-optimal linking systems.
The Park-Pham Theorem with Optimal Convergence Rate
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
Park and Pham's recent proof of the Kahn-Kalai conjecture was a major breakthrough in the field of graph and hypergraph thresholds. Their result gives an upper bound on the threshold at which a probabilistic construction has a $1-\epsilon$ chance of achieving a given monotone property. While their bound in other parameters is optimal up to constant factors for any fixed $\epsilon$, it does not have the optimal dependence on $\epsilon$ as $\epsilon\rightarrow 0$. In this short paper, we prove a version of the Park-Pham Theorem with optimal $\epsilon$-dependence.
citation-role summary
citation-polarity summary
fields
math.CO 1years
2026 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Universality in random graphs via optimal linking systems: trees and beyond
An absolute constant C suffices for bounded-degree tree universality in G(n, C ln n/n), and cycle-factor universality is optimal up to constants via depth-optimal linking systems.