Non-uniform Kahn-Kalai, spread, variants, and applications
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917341422419968 |
|---|---|
| author | De Silva, Thinula Gao, Pu |
| author_facet | De Silva, Thinula Gao, Pu |
| contents | Building on B.Park and Vondrak's recent generalization of the J.Park-Pham Theorem (formerly known as Kahn-Kalai conjecture) to non-uniform probability measures, this paper introduces the notion of "spread" for the non-uniform setting. This provides a framework to establish 1-statements for subgraph containment in inhomogeneous random graphs with or without a set of forced edges. Using this approach, we derived conditions for the emergence of perfect matchings in the Stochastic Block Model and the Chung-Lu model, and verified that these conditions are in general not tight, but they capture thresholds across a broad range of regimes. Finally, we bridge this non-uniform framework with $\mathcal{G}(n,\textbf{d})$, utilizing a coupling argument to demonstrate thresholds for perfect matchings in $\mathcal{G}(n,\textbf{d})$ for a broad range of degree sequences $\textbf{d}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_13737 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Non-uniform Kahn-Kalai, spread, variants, and applications De Silva, Thinula Gao, Pu Combinatorics Probability Building on B.Park and Vondrak's recent generalization of the J.Park-Pham Theorem (formerly known as Kahn-Kalai conjecture) to non-uniform probability measures, this paper introduces the notion of "spread" for the non-uniform setting. This provides a framework to establish 1-statements for subgraph containment in inhomogeneous random graphs with or without a set of forced edges. Using this approach, we derived conditions for the emergence of perfect matchings in the Stochastic Block Model and the Chung-Lu model, and verified that these conditions are in general not tight, but they capture thresholds across a broad range of regimes. Finally, we bridge this non-uniform framework with $\mathcal{G}(n,\textbf{d})$, utilizing a coupling argument to demonstrate thresholds for perfect matchings in $\mathcal{G}(n,\textbf{d})$ for a broad range of degree sequences $\textbf{d}$. |
| title | Non-uniform Kahn-Kalai, spread, variants, and applications |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2603.13737 |