1 Graph thresholds and the main result
When does a random graph contain a prescribed graph? A necessary condition is that each subgraph of the target have a reasonable expected number of copies. Kahn and Kalai [8] conjectured that this elementary obstruction determines the containment threshold within a logarithmic factor, uniformly over the target graph. We prove this conjecture, with the logarithm depending on the number of target edges.
For finite simple graphs G and F, write N(G,F) for the number of subgraphs of G isomorphic to F. These are ordinary copies: additional edges between the chosen vertices are allowed. Let G(n,p) be the random graph on [n]=\{1,\ldots,n\} in which each edge is present independently with probability p. For a graph H with at least one edge and at most n vertices, define
The first quantity is the containment threshold; the second is the graph expectation threshold. Both infima are attained, since the relevant probabilities and expectations are continuous, there are only finitely many constraints, and p=1 satisfies all of them. The single-edge constraint gives \pE(n,H)>0. If H appears with probability at least one half, then so does every F\subseteq H, and its expected count is at least one half. Thus \pE(n,H)\le\pc(n,H).
Theorem 1.1. For every n\ge2 and every finite simple graph H with h=e(H)\ge1 edges and at most n vertices,
In particular,
Here \ee is the base of the natural logarithm. The constants are explicit and universal; the graph H may vary with n. Kahn and Kalai use expected count one in their formulation. Replacing one half by one changes the graph expectation threshold by a factor between one and two: for each subgraph with r\ge1 edges its expected count is proportional to p^r, so its constraint changes by 2^{1/r}\le2. This normalization therefore gives the same conjecture.
1.1 History and the obstruction
For a fixed target, threshold questions are part of the classical random-graph theory of Erdős and Rényi [5]; Bollobás [2] treated threshold functions for general fixed subgraphs. Here the target can grow with the host graph. For example, let H be a perfect matching on an even number n of vertices. Then \pE(n,H)=\Theta(1/n), whereas \pc(n,H)=\Theta(\log n/n) [6, 8]. The larger scale is needed to eliminate isolated vertices of the host: a perfect matching must cover every vertex. Hamilton cycles exhibit the same logarithmic gap [8]. These examples show why a uniform comparison must allow a logarithm. Other spanning targets have required different methods: Riordan [14], for example, proved that for every fixed p>1/4, G(2^d,p) contains the d-dimensional cube with probability tending to one.
To distinguish the two Kahn–Kalai conjectures, consider a nonempty proper increasing family \mathcal F\subseteq2^X, where X is finite. A cover is a family \mathcal G\subseteq2^X such that every F\in\mathcal F contains some S\in\mathcal G. Its cost at density p is \sum_{S\in\mathcal G}p^{|S|}. The integral expectation threshold q(\mathcal F) is the largest p for which a cover has cost at most 1/2. A fractional cover assigns weights w_S\ge0 to S\subseteq X, requires \sum_{S\subseteq F}w_S\ge1 for each F\in\mathcal F, and has cost \sum_S w_Sp^{|S|}. Allowing these covers defines q_f(\mathcal F) with the same budget 1/2. Union bounds and expectations give q(\mathcal F)\le q_f(\mathcal F)\le p_{\mathrm c}(\mathcal F), where p_{\mathrm c}(\mathcal F) is the density at which an independent random subset belongs to \mathcal F with probability 1/2.
Talagrand [15, Section 6] introduced the fractional formulation and its dual description by spread probability measures. Alweiss, Lovett, Wu, and Zhang [1], building on the regularity viewpoint of Lovett, Solomon, and Zhang [9], developed the fragment method in their work on sunflowers. Frankston, Kahn, Narayanan, and Park [7] proved p_{\mathrm c}(\mathcal F)=O(q_f(\mathcal F)\log\ell), where \ell is the maximum of two and the largest size of a minimal member of \mathcal F. Park and Pham [13] proved the corresponding bound with q in place of q_f, resolving the abstract Kahn–Kalai conjecture by a minimum-fragment argument. The integral and fractional thresholds are within a universal constant factor at the common one-half budget [12, Theorem 1.1]. This comparison is contextual; the proof below does not use it.
For the family \mathcal F_H of edge sets containing a copy of H, the copies of any one subgraph form a cover. Thus \pE(n,H)\le q(\mathcal F_H), and the abstract theorem alone does not give the desired bound in terms of \pE(n,H). Mossel, Niles-Weed, Sun, and Zadik [11, Theorem 1] obtained a single logarithm using the modified graph threshold
The factor N(H,F) records that containing H supplies all its copies of F. By symmetry this parameter equals q_f(\mathcal F_H) [3, Equation (1)]; comparing it with \pE(n,H) is the additional graph-specific problem.
Dubroff, Kahn, and Park [3, Theorems 1.2–1.5] proved q_f(\mathcal F_H)=O(\pE(n,H)\log^2 n) and hence \pc(n,H)=O(\pE(n,H)\log^3 n), using a rooted-extension decomposition. They also established the conjectured single-logarithm bound when \pE(n,H)<1/(3n). In further work [4, Theorems 1.4–1.5], they proved N(H,F)\le\EE N(G(n,\min\{1,Lq\}),F) whenever all subgraphs of H have expected count at least one at density q, for test graphs F that are cliques, cycles, or bounded-degree trees. The constant L is universal for cliques and cycles and depends on the degree bound for trees. Tran [16] then obtained q_f(\mathcal F_H)=O(\pE(n,H)\log(2e(H))), reducing the general containment loss to O(\log^2(2e(H))). He removed the loss in the comparison of expectation thresholds for trees and for graphs whose average degree is at least the logarithm of their maximum degree, thereby proving the second conjecture for these classes. His ratio-maximizing cores give the conditional graph-extension distributions used here.
Tran [16, Section 4] also proposed a coupling conjecture that would absorb successive conditional extensions while paying the logarithmic sampling cost once. We prove the required containment bound through a tree reduction: we keep all possible extension histories in a tree and reduce every level with the same random set. Disjointness along a history supplies the precise control of dependence that this reuse requires.
1.2 Proof strategy and method ancestry
Start with a nonempty edge subset I of H. Among its subgraphs, choose S maximizing the probability that a fixed copy S_0 on [n] lies in a uniform copy of I, after division by a suitable exponential weight in e(S). The first-moment constraints force S to be smaller than I by a fixed factor. Maximality also bounds the probability that a prescribed set J of added edges appears, conditional on any copy of S, by (C_0\pE(n,H))^{|J|} for a universal constant C_0. Repeating the choice gives nested subgraphs. The tree branches over all their possible copies; its arc labels are the added edges. Those labels are disjoint along each path, and their sizes increase geometrically. This maximization argument is the graph-specific spread-link construction of Tran [16, Section 3]. Its conditioning step has antecedents in the large-link argument of Lovett, Solomon, and Zhang [9, Claim 29] and the spread-link extraction from a maximal violating core in Alweiss, Lovett, Wu, and Zhang [1, Lemma 2.4].
For one distribution of labels, we use the Bayesian resampling construction of Mossel, Niles-Weed, Sun, and Zadik [10]. Plant a source label into an independent random set W, sample a target label from the posterior distribution given their union, and retain the part of the target outside W. This remainder is also a subset of the source. Section 2 proves that large remainders are exponentially unlikely and bounds the change of measure on coordinates outside the target.
Section 3 applies this transition simultaneously at every node of the fixed tree. A recursively defined potential bounds the probability that too many continuations fail. Below a target arc, all labels avoid that arc’s label, so the local change-of-measure estimate applies to the entire descendant potential. This is the step that permits one W to halve every level’s capacity while preserving spread at a controlled conditioning cost. Iteration needs only logarithmically many successful draws. Finally, Section 4 constructs the graph hierarchy, with the ordinary-copy normalization explicit, and applies the tree covering theorem. All these arguments are proved below.
Throughout, \log without a subscript is the natural logarithm. For a finite set X and 0\le\rho\le1, let \mu_\rho be the law of a random subset of X that includes each element independently with probability \rho.
2 Resampling a spread family
The graph argument will produce distributions of edge extensions. We first show how one product sample can replace a set from such a distribution by a smaller remainder, and bound the resulting change in the law of coordinates outside the chosen set.
For a>0, a probability distribution on subsets A\subseteq X is a-spread if
We allow the distribution to be carried by a finite indexed family (A_b)_{b\in B}: distinct indices may have the same label, and labels may be empty. Write \nu_b>0 for the weights, with \sum_b\nu_b=1.
The transition below is the planted-set and posterior-resampling construction of Mossel, Niles-Weed, Sun, and Zadik [10, Sections 2.1–2.3]. We record a capacity-dependent failure estimate and a change-of-measure bound for functions of coordinates outside the target label; the latter will control the dependence between successive tree levels.
Fix 0<\rho<1 and W\subseteq X. The following transition will be used at every node of a tree:
- 1.
Choose a source c with law \nu, and set Y=W\cup A_c.
- 2.
Choose a target b with conditional probabilities
\frac{\nu_b\rho^{-|A_b|}\ind_{\{A_b\subseteq Y\}}}{Z(Y)}, \qquad Z(Y)=\sum_{d\in B}\nu_d\rho^{-|A_d|} \ind_{\{A_d\subseteq Y\}}. \tag{2.2} - 3.
Retain the fragment T=A_b\setminus W.
The denominator is positive because A_c\subseteq Y and \nu_c>0. To see why these are posterior probabilities, now let W\sim\mu_\rho independently of the source. For a fixed source c, the probability mass of the planted union at a set Y is \mu_\rho(Y)\rho^{-|A_c|}\ind_{\{A_c\subseteq Y\}}. After averaging over c, the law of Y therefore has density Z relative to \mu_\rho, and Bayes’ formula gives (2.2). At a specified W, however, only the source is guaranteed to have its original law \nu; the target law may differ.
For every transition of positive probability,
The first inclusion will preserve spread by comparing the fragment with the source. The second lets us recover the chosen target from W and its fragment. In the tree application, that target also specifies which child and its continuations are kept. The entire transition, including its fragment, only inspects membership in W on \bigcup_{b\in B}A_b.
Lemma 2.1 (Local resampling). Suppose that |A_b|\le m for a positive integer m, the law \nu is a-spread, and
Let W\sim\mu_\rho, independently of the source choice, and perform the transition above. Call the transition a local failure if
Then
Moreover, for each fixed target b and every nonnegative function f depending only on W\cap(X\setminus A_b),
The expectation on the right is with respect to W\sim\mu_\rho.
Proof. The density identity above gives
We will use the following consequence of spread. For a fixed b, let R=|A_c\cap A_b|, where c has law \nu. For every 0\le r\le m, including the trivial case r=0,
On Z(Y)\ge\ee^{-10m}, bound the reciprocal denominator in (2.2) by \ee^{10m}. For a fixed pair (c,b), the condition A_b\subseteq W\cup A_c requires A_b\setminus A_c\subseteq W, an event of probability \rho^{|A_b\setminus A_c|}. Also, |T|>m/2 implies |A_c\cap A_b|>m/2. Therefore
Together with (2.6), this gives
as m\ge1.
For (2.5), again bound the reciprocal denominator and then sum over sources. The event A_b\setminus A_c\subseteq W uses only coordinates inside A_b, so it is independent of f(W). Hence
The penultimate inequality is (2.7); the last uses (1+a/\rho)^m\le\ee^m.
3 Covering a tree
We now cover an entire chain of extensions. The input is a finite tree whose edge labels are disjoint along each path and whose child laws are spread. The aim is to put the labels of one full path inside a product sample, with a cost logarithmic in the largest extension size.
A probability tree on X is a finite rooted tree with all leaves at the same depth, together with a probability distribution \nu_v on the children \ch(v) of each non-leaf node v and a label A_v(b)\subseteq X on the arc from v to each child b. We delete zero-weight children. Different nodes or arcs may carry identical labels; nodes are never identified merely because their labels agree. A path always means a full root-to-leaf path, unless otherwise specified. Write
for its union of labels.
The tree is disjoint if the labels along each path are pairwise disjoint. A level has capacity m if all its labels have size at most m. A level is a-spread if the child distribution at every node immediately above that level is a-spread. Thus all requirements concern individual child distributions; no spread assumption is made on the distribution of a full path.
Theorem 3.1 (Tree covering). Let \TT be a disjoint probability tree on a finite set X, with k\ge1 levels. Suppose that every level is \sigma-spread, where \sigma>0, and that its positive integer capacities satisfy
Set
Then
Section 4 constructs such a tree for H with \sigma=128\pE(n,H) and \ell_k\le e(H). We prove the tree theorem by repeatedly pruning and reweighting the tree while replacing its labels by smaller subsets. Empty labels and unequal label sizes must therefore be allowed.
3.1 One simultaneous reduction
Lemma 3.2 (Reduction). Let \TT be a disjoint probability tree with k\ge1 levels and positive integer capacities m_1,\ldots,m_k satisfying m_{j+1}\ge16m_j. Suppose level j is \alpha_j-spread, where
There is a deterministic procedure which, given W\sim\mu_\rho, succeeds with probability at least 3/4 and on success returns a disjoint probability tree \TT' with the same levels, such that:
- (i)
level j has capacity \lfloor m_j/2\rfloor and is \alpha_j/(1-\ee^{-m_j})-spread;
- (ii)
for every path Q of \TT' there is a path P of \TT with
\UU(P)\subseteq W\cup\UU(Q). \tag{3.1}
Proof. The output will be a subtree with labels A_v(b)\setminus W and child laws obtained from the target marginals of the local transition. We first identify which children can be retained while discarding at most \ee^{-m_j} of the transition mass at each retained node with outgoing level j. Keep the input tree fixed throughout this analysis. At a node whose outgoing level is j, use the transition of Section 2 with its child distribution and capacity m_j. All nodes use the same set W. At fixed W, write d_v(W) for the probability of local failure at v, and t_{vb}(W) for the probability of local non-failure with target b. Thus
All these probabilities refer to the child laws of the fixed input tree, before any pruning or conditioning.
Pruning. For the remainder of the construction, fix W and put \epsilon_j=\ee^{-m_j}. Declare all leaves good. Working upward, declare a node v with outgoing level s good if
The attempt succeeds exactly when the root is good.
To bound the probability that the root is bad, define a nonnegative potential on every node of the input tree. Set D_v(W)=0 at leaves and, at a node with outgoing level s, define recursively
Every bad node satisfies D_v(W)>1. Indeed, assuming this for its bad children, the numerator in (3.4) is at least
where the last inequality follows from (3.2) and the failure of (3.3). This proves the assertion by backward induction.
Expected potential. We now average over W\sim\mu_\rho. Fix a child b of a node v with outgoing level s, and abbreviate its incoming label to A_b. Every label in the entire subtree below b is disjoint from A_b: each such label lies on a path containing the arc into b. The transition at any node in that subtree only inspects W on the union of that node’s child labels. By its recursive definition, D_b(W) therefore depends only on W outside A_b.
This statement concerns every node of the fixed input tree, before conditioning on that node being good or being retained. Figure 1 shows the disjointness that makes this possible.
Figure 1: Disjointness along paths controls the change of measure. Every arc below b lies on a path through its incoming arc, so the potential D_b is a function of coordinates outside the incoming label. The diagram is schematic; labels on different branches may overlap.
In the local transition at v,
We may consequently apply (2.5) with f(W)=D_b(W). Together with (2.4) and \epsilon_s^{-1}=\ee^{m_s}, the recurrence gives
This step controls the dependence caused by reusing W. Since the child weights sum to one, backward induction yields
In particular, if o is the root, then
For the last inequality, geometric growth gives \sum_{h<j}m_h\le m_j/15, and the m_j are distinct positive integers. Thus the sum is at most \sum_{m\ge1}\ee^{-7m}<1/4.
The reduced tree. On success, start from the good root. At any good node v with outgoing level j, put
Retain each good child b with t_{vb}(W)>0, give it weight t_{vb}(W)/\gamma_v(W), replace its incoming label by
and continue recursively into b. The result is a pruned and reweighted subtree of the input tree. It has the same depth because \gamma_v>0 at every retained non-leaf node. Its labels are subsets of the old labels, so it is disjoint. Since A_v(b)\subseteq W\cup T_b on every retained arc, it also satisfies (3.1). A retained child has t_{vb}>0, which implies |T_b|\le\lfloor m_j/2\rfloor.
This new child law is the target marginal of the joint transition conditioned on local non-failure and a good target. Denote this conditioning event by E_v. For the spread bound, use the source: (2.3) gives T\subseteq A_v(c) for every transition, and the unconditioned source has law \nu_v even at fixed W. Thus, for every nonempty J\subseteq X,
This proves all the assertions. The quantities t_{vb}(W) define the entire construction deterministically; sources and targets are auxiliary random variables used to analyze its weights.
3.2 Iteration
Proof of Theorem 3.1. If r=1, the conclusion is immediate. Suppose r<1, and set
In particular 0<\rho<1. Start with \TT and make successive attempts using fresh independent sets of law \mu_\rho. A failed attempt leaves the current tree unchanged. After a successful attempt, retain the tree provided by Lemma 3.2. Conditionally on the complete past, the current tree is fixed and the next draw still has law \mu_\rho.
After t successes, the capacity at original level i is
using \lfloor\lfloor x\rfloor/2\rfloor=\lfloor x/2\rfloor. Levels of zero capacity form an initial segment. After each success, choose any one path through that segment and keep its ending subtree, deleting the segment. All committed labels are empty, so each path of the retained subtree extends to a full path by adjoining the chosen empty prefix. This preserves the recovery guarantee and every bound at a retained node. If no levels remain, only the root is left. Fix a tie-breaking rule for these choices. The remaining positive capacities still satisfy m_{i+1}(t)\ge16m_i(t), since \lfloor16x\rfloor\ge16\lfloor x\rfloor.
At a remaining original level i, a valid spread parameter after t successes is
The positive integers \lfloor\ell_i/2^u\rfloor in this product are distinct. The infinite product over all positive integers is less than 4, because
Consequently \alpha_i(t)\le4\sigma=a. The initial tree satisfies these bounds, and Lemma 3.2 proves them inductively after every success. Thus every attempt before completion has conditional success probability at least 3/4.
After s successes, (3.6) is zero at every level. Composing (3.1) through the successful reductions shows that the union of their draws contains the labels of a path in the original tree. The expected waiting time for each next success is at most 4/3: conditionally on the past, its tail is bounded by that of a geometric random variable with success probability 3/4. Hence the expected number of attempts needed is at most 4s/3. By Markov’s inequality, completion occurs within 4s attempts with probability at least 2/3.
Predraw 4s independent sets of law \mu_\rho, including any that the procedure ultimately does not use, and take their union W_*. It has law \mu_{r_*}, where
With probability at least 2/3, W_* contains a path union. The same bound holds for \mu_r by monotonicity.
4 Application to graph containment
It remains to construct the tree required by Theorem 3.1. We use the normalized-containment maximization and conditional-extension argument of Tran [16, Section 3, Lemma 3.1], with constants suited to the factor-16 separation of capacities. The copy-count identity below also appears in Mossel, Niles-Weed, Sun, and Zadik [11, Equation (5)].
Put q=\pE(n,H) and \sigma=128q. Delete the isolated vertices of H and of each graph subsequently considered, and identify these graphs with their edge sets. This does not change the event of containing H: any copy of its nonisolated part can be extended by choosing the required number of additional vertices, since n\ge|V(H)| and copies need not be induced. Every edge subset used below, on its incident vertices, is a subgraph of the original H, so its expectation at q is at least 1/2. Throughout this deletion, q remains the threshold defined using the original graph H.
For a graph F without isolated vertices, let
In particular, M(F)=(n)_{v(F)}/|\operatorname{Aut}(F)|, where (n)_v=n(n-1)\cdots(n-v+1) and \operatorname{Aut}(F) is the group of vertex permutations preserving adjacency. Dividing by this group counts each ordinary copy once; M(I,F) likewise counts copies, rather than vertex embeddings. For the empty edge set use M(\varnothing)=M(I,\varnothing)=1. If \boldsymbol I is a uniformly chosen copy of I on [n], and F_0 is any fixed copy of an edge subset F\subseteq I, then
Indeed, permutation symmetry makes the probability independent of the chosen copy F_0. Summing it over all M(F) copies counts the M(I,F) copies contained in each \boldsymbol I.
Lemma 4.1 (Graph hierarchy). There is a disjoint probability tree on X=\binom{[n]}2 whose path unions are copies of H with its isolated vertices removed, such that every level is \sigma-spread and its label sizes \ell_1,\ldots,\ell_k satisfy
Proof. For a current nonempty edge set I\subseteq H, choose an edge subset S\subseteq I maximizing
where S_0 is any fixed copy of S on [n]. The empty set is allowed and has value 1. Fix any deterministic rule for breaking ties.
Write h_I=|I| and r=|S|>0. The expectation constraint gives M(S)q^r\ge1/2, while M(I,S)\le\binom{h_I}{r}. By (4.1),
For r\ge h_I/17, the bound \binom{h_I}{r}\le(\ee h_I/r)^r gives
Thus every maximizing predecessor satisfies |S|<|I|/17.
Repeat the selection until the empty set is reached, and write the resulting nested sequence in reverse order as
Here and below H denotes its edge set. Build a tree rooted at the empty set. From each reached copy S_0 of H_{i-1}, take as children all copies of H_i containing S_0, with the uniform distribution, and label the arc to a child I_0 by I_0\setminus S_0. Such children exist, since every copy of H_{i-1} extends to a copy of H_i on [n]. Keep distinct histories as distinct tree nodes. The labels on every path are disjoint and their union is a copy of H. Their sizes are
It remains to check conditional spread. At a node S_0, let A be its random added label. If J\cap S_0\ne\varnothing, then \PP(J\subseteq A)=0. Otherwise, for a uniform copy \boldsymbol I of H_i,
If the numerator is positive, S_0\cup J is isomorphic to an edge subset U\subseteq H_i. Maximality of H_{i-1} in (4.2) gives
Together with (4.3), this gives \PP(J\subseteq A)\le\sigma^{|J|}. If the numerator is zero, the same bound is immediate. This proves the lemma.
Proof of Theorem 1.1. Apply Theorem 3.1 to the tree of Lemma 4.1, with \sigma=128q. Since \ell_k\le h=e(H), a Bernoulli edge set with parameter
contains a copy of H with probability at least 2/3. This proves (1.1). Finally, h\le\binom n2\le n^2 and n\ge2 give 1+\log_2 h\le3\log_2 n, and hence the stated constant C=6144\ee^{50}.
References
- [1]R. Alweiss, S. Lovett, K. Wu, and J. Zhang, Improved bounds for the sunflower lemma, Annals of Mathematics (2) 194 (2021), no. 3, 795–815. doi:10.4007/annals.2021.194.3.5.
- [2]B. Bollobás, Threshold functions for small subgraphs, Mathematical Proceedings of the Cambridge Philosophical Society 90 (1981), no. 2, 197–206. doi:10.1017/S0305004100058655.
- [3]Q. Dubroff, J. Kahn, and J. Park, On the “second” Kahn–Kalai conjecture, arXiv:2508.14269v1 (August 19, 2025). https://arxiv.org/abs/2508.14269v1.
- [4]Q. Dubroff, J. Kahn, and J. Park, On the “second” Kahn–Kalai conjecture: cliques, cycles, and trees, arXiv:2510.02005v2 (October 23, 2025). https://arxiv.org/abs/2510.02005v2.
- [5]P. Erdős and A. Rényi, On the evolution of random graphs, Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5 (1960), 17–61. https://static.renyi.hu/~p_erdos/1960-10.pdf.
- [6]P. Erdős and A. Rényi, On the existence of a factor of degree one of a connected random graph, Acta Mathematica Academiae Scientiarum Hungaricae 17 (1966), 359–368. https://users.renyi.hu/~p_erdos/1966-16.pdf.
- [7]K. Frankston, J. Kahn, B. Narayanan, and J. Park, Thresholds versus fractional expectation-thresholds, Annals of Mathematics (2) 194 (2021), no. 2, 475–495. doi:10.4007/annals.2021.194.2.2.
- [8]J. Kahn and G. Kalai, Thresholds and expectation thresholds, Combinatorics, Probability and Computing 16 (2007), no. 3, 495–502. doi:10.1017/S0963548307008474.
- [9]S. Lovett, N. Solomon, and J. Zhang, From DNF compression to sunflower theorems via regularity, 34th Computational Complexity Conference, LIPIcs 137 (2019), 5:1–5:14. doi:10.4230/LIPIcs.CCC.2019.5.
- [10]E. Mossel, J. Niles-Weed, N. Sun, and I. Zadik, A Bayesian proof of the spread lemma, Random Structures & Algorithms 66 (2025), no. 4, e70008. doi:10.1002/rsa.70008.
- [11]E. Mossel, J. Niles-Weed, N. Sun, and I. Zadik, On the second Kahn–Kalai conjecture, arXiv:2209.03326v1 (September 7, 2022). https://arxiv.org/abs/2209.03326v1.
- [12]OpenAI, Integral and fractional expectation thresholds are equivalent, OpenAI Math Release preprint PDF, 2026, Theorem 1.1, p. 2. Reading view on this site: Integral and fractional expectation thresholds are equivalent.
- [13]J. Park and H. T. Pham, A proof of the Kahn–Kalai conjecture, Journal of the American Mathematical Society 37 (2024), no. 1, 235–243. doi:10.1090/jams/1028.
- [14]O. Riordan, Spanning subgraphs of random graphs, Combinatorics, Probability and Computing 9 (2000), no. 2, 125–148. doi:10.1017/S0963548399004150.
- [15]M. Talagrand, Are many small sets explicitly small?, Proceedings of the 42nd ACM Symposium on Theory of Computing (2010), 13–36. doi:10.1145/1806689.1806693.
- [16]T. Tran, Fractional expectation thresholds and the “second” Kahn–Kalai conjecture, arXiv:2609.20546v2 (September 24, 2026). https://arxiv.org/abs/2609.20546v2.