Non-uniform Kahn-Kalai, spread, variants, and applications
Thinula De Silva, Pu Gao · 2026
Read Non-uniform Kahn-Kalai, spread, variants, and applications by Thinula De Silva, Pu Gao (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-13737.txt.
Introduction
Thinula De Silva and Pu Gao introduce a non-uniform notion of spread for the Kahn-Kalai framework. Building on Park and Vondrak's generalization of the Park-Pham theorem to non-uniform measures, they define spread in that setting. The framework yields 1-statements about subgraph containment for inhomogeneous random graphs, with forced edges allowed or not. They derive conditions for perfect matchings in the Stochastic Block Model and the Chung-Lu model. Those conditions are not tight in general but capture thresholds across broad regimes.
Catalog record
| CREATOR | Thinula De Silva, Pu Gao |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87867 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.13737
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Non-uniform Kahn-Kalai, spread, variants, and applications Thinula De Silva, Pu Gao Abstract Building on B. Park and Vondrák’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 𝒢 ( n , d ) \mathcal{G}(n,\textbf{d}) , utilizing a coupling argument to demonstrate thresholds for perfect matchings in 𝒢 ( n , d ) \mathcal{G}(n,\textbf{d}) for a broad range of degree sequences d . 1 Introduction Random graph theory, initiated by Erdős and Rényi in the late 1950s, has become a central field in modern graph theory and theoretical computer science. One of the most striking phenomena in random graph theory is the abrupt structural transformation known as a phase transition, where a small change in edge probability leads to a sudden change in graph structures or parameters. Friedgut and Kalai proved that every monotone graph property exhibits a phase transition [ 4 ] . Determining the threshold at which a given monotone graph property undergoes the phase transition is a problem-specific task and lies at the heart of random graph theory. The famous Kahn-Kalai conjecture, proposed by Kahn and Kalai in 2006, relates the threshold of an increasing family to a natural lower bound called the expectation threshold. The conjecture asserts that this lower bound is, up to a logarithmic factor, close to the actual threshold. This conjecture is stated in a more general setting. Let X be a finite set. In the example of random graph {\mathcal{G}}(n,p) , X=\binom{[n]}{2} is the set of edges in a complete graph on n vertices. Let \mathcal{F}\subseteq 2^{X} be an increasing family, where \mathcal{F}\neq\emptyset,2^{X} . As an example of increasing graph properties, we can think of {\mathcal{F}} being {\mathcal{F}}_{\texttt{PM}} , the set of graphs on [n] containing a perfect matching (assuming that n is even). Given p\in[0,1] , a probability measure \mu_{p} on the set of subsets of X is defined by \mu_{p}(S)=p^{\left\lvert S\right\rvert}(1-p)^{\left\lvert X\setminus S\right\rvert}\quad\text{for all $S\subseteq X$}. It is not hard to show that \mu_{p}(\mathcal{F}):=\sum\limits_{S\in\mathcal{F}}\mu_{p}(S) is strictly increasing in p with \mu_{0}({\mathcal{F}})=0 and \mu_{1}({\mathcal{F}})=1 . Thus, there is a unique value p_{c}(\mathcal{F}) , called the threshold of {\mathcal{F}} , such that u_{p}(\mathcal{F})=1/2 when p=p_{c}(\mathcal{F}) . As noted in [ 1 ] , \lim\limits_{n\rightarrow\infty}\mu_{p}(\mathcal{F})=\begin{cases}0&\text{ if }p\ll p_{c}(\mathcal{F})\\ 1&\text{ if }p\gg p_{c}(\mathcal{F})\end{cases} and thus p_{c}(\mathcal{F}) marks the phase transition where the measure {\mathcal{F}} undergoes the sudden change from 0 to 1. Determining p_{c}(\mathcal{F}) involves identifying p_{c} , usually a function of N=|X| , and proving that {\text{{0-statement:}}}\quad\mu_{p}({\mathcal{F}})=o(1),\quad\text{if $p\ll p_{c}$}; and {\text{{1-statement:}}}\quad\mu_{p}({\mathcal{F}})=1-o(1),\quad\text{if $p\gg p_{c}$}. In many situations, establishing the 0-statement is a much easier task than the 1-statement, as typically one can easily prove the existence of certain obstructions for {\mathcal{F}} , e.g. isolated vertices for {\mathcal{F}}={\mathcal{F}}_{\texttt{PM}} . The Kahn-Kalai conjecture states that p_{c}({\mathcal{F}})=O(p_{E}({\mathcal{F}})\log N) , where p_{E}({\mathcal{F}}) is the so-called expectation threshold, which will be formally defined in Section 1.4 . Roughly speaking, it can be viewed as the “best lower bound” that can be obtained by considering the expected number of obstructions. We highlight two key advances on the Kahn-Kalai conjecture, which are restated as Theorem 1.15 and Theorem 1.16 respectively. First, Park and Pham [ 15 ] confirmed the conjecture, which reduces determining thresholds for an increasing family to estimating the expectation threshold. However, the latter still remains challenging as it involves optimizing the “covers” of the given increasing family {\mathcal{F}} . Second, an earlier work by Frankston, Kahn, Narayanan, and Park [ 3 ] uses the dual of the cover optimization to provide an upper bound for the primal and thereby demonstrate the 1-statement. The dual variables have a combinatorial interpretation known as spread . Proving the 1-statement for {\mathcal{F}} involves estimating the spread of structures related to {\mathcal{F}} . This approach has significantly advanced threshold determination for long-standing problems in random graph theory (such as the square of Hamilton cycles in [ 8 ] , the bounded degree subgraphs in [ 3 ] , the Erdős conjecture about high girth Steiner triple systems in [ 9 ] , etc.) while also greatly simplifying proofs for existing theorems with very involved proofs such as the bounded degree spanning trees (originally proved by Montgomery in [ 12 ] and later proved using Kahn-Kalai in [ 3 ] ). In this paper, we discuss a few generalizations and variants of the Park-Pham theorem (i.e. the Kahn-Kalai conjecture). The Park-Pham theorem concerns a probability measure on the subsets of X by including every element of X with a uniform probability p . What happens if the inclusion probability is not uniform for the elements? In a recent work [ 14 ] , B. Park and Vondrák proved that the Park-Pham theorem holds for this generalized version; see the precise statement in Section 1.5 . As before, this theorem relates two thresholds and does not directly yield an estimate for the threshold of an increasing family {\mathcal{F}} . Indeed, the notion of “threshold” is not so clear any more, as we are dealing with vectors \textbf{p}\in[0,1]^{X} rather than a single real probability p . We first extend the notion of thresholds and phase transitions in this more general setting. Given \textbf{p}\in[0,1]^{X} , let \mu_{\textbf{p}} be the product measure on 2^{X} where \mu_{\textbf{p}}(S):=\prod\limits_{x\in S}p_{x}\prod\limits_{y\notin S}(1-p_{y})\quad\text{for all $S\subseteq X$} (1) and \mu_{\textbf{p}}(\mathcal{F}):=\sum\limits_{S\in\mathcal{F}}\mu_{\textbf{p}}(S) . Let X_{\textbf{p}} be a random subset of X drawn from \mu_{\textbf{p}} . In the uniform case, p_{c}(\mathcal{F}) is defined by \mu^{-1}(1/2) , where \mu=\mu_{p}({\mathcal{F}}) is viewed as a function of p , which is known to be continuous and increasing since {\mathcal{F}} is an increasing family. This notation of threshold naturally generalises to the non-uniform setting, where we define p_{c}(\mathcal{F}) to be the following set of p : \{\textbf{p}\in[0,1]^{X}:\mu_{\textbf{p}}(\mathcal{F})=1/2\}. (2) The theorem below demonstrates that phase transitions do occur around the values of p in the set ( 2 ). Theorem 1.1 . Let \mathcal{F}\neq\emptyset,2^{X} be an increasing family such that \mathcal{F}\subseteq 2^{X} and 0<\varepsilon<1 be fixed. If \textbf{p}^{*}\in[0,1]^{X} such that \varepsilon<\mu_{\textbf{p}^{*}}(\mathcal{F})<1-\varepsilon and \alpha=\omega(1) , then \lim\limits_{\left\lvert X\right\rvert\rightarrow\infty}\mu_{\textbf{p}}(\mathcal{F})=\begin{cases}0&\text{ if }\textbf{p}\leq\textbf{p}^{*}/\alpha\\ 1&\text{ if }\textbf{p}\geq\alpha\textbf{p}^{*}\end{cases} . Remark . Such \textbf{p}^{*} always exists. To see this, note that if \mathcal{F}\neq\emptyset,2^{X} , then for each 0<\delta<1 , there exists \textbf{p}\in[0,1]^{X} such that \mu_{\textbf{p}}\left(\mathcal{F}\right)=\delta . This is because \mu_{\textbf{p}}\left(\mathcal{F}\right) is a polynomial in p , and an increasing function that attains both 0 (at \textbf{p}=\textbf{0} ) and 1 (at \textbf{p}=\textbf{1} ), as \mathcal{F} is an increasing family. However, unlike in the uniform setting, given p , it is not clear which \textbf{p}^{*} it should be compared to in order to determine which of the following cases p falls into. • Supercritical case: \textbf{p}\gg\textbf{p}^{*} for some \textbf{p}^{*}\in p_{c}({\mathcal{F}}) ; • Subcritical case: \textbf{p}\ll\textbf{p}^{*} for some \textbf{p}^{*}\in p_{c}({\mathcal{F}}) ; • Near the threshold case: \textbf{p}=\Theta(\textbf{p}^{*}) for some \textbf{p}^{*}\in p_{c}({\mathcal{F}}) ; • None