Fractional covers, discrete convexity, and random-graph thresholds

← All digests

Family 175 · Combinatorics
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

When a random object first acquires a property, can its threshold be predicted from simple necessary patterns? A random graph containing a prescribed target must contain many smaller patterns, for example. Counting those patterns can show that the target is unlikely at low density.

A general version of this idea covers every successful object by elementary containment events. A fractional cover permits several partial contributions to replace a single selected event. Does this relaxation substantially improve the threshold estimate?

This family contains three related claims. M2 says integral and fractional expectation thresholds differ by only a universal factor. M3 proves a discrete-convexity statement about unions of likely sets at the original sampling density. M1 uses that theorem to split any target graph into a bounded number of pieces, each appearing near the target’s integral expectation threshold. The pieces are fixed in advance, but their embeddings need not fit together.

2. Background and essential definitions

Let $X$ be a finite ground set. Its random subset $X_p$ includes each element independently with probability $p$. Write $\mu_p(\mathcal A)$ for the probability that $X_p$ belongs to a family $\mathcal A$ of subsets.

A family $\mathcal F$ is increasing if adding elements cannot destroy membership. The family of edge sets containing a triangle is an example. Assume $\mathcal F$ is nonempty and is not the whole power set. Its ordinary threshold $p_c(\mathcal F)$ is the parameter where membership has probability one half.

A cover $\mathcal G$ of $\mathcal F$ is a collection of subsets such that every member of $\mathcal F$ contains at least one $S\in\mathcal G$. A generator $S$ need not itself guarantee the property; the cover gives necessary alternatives. Its cost is

$$c_p(\mathcal G)=\sum_{S\in\mathcal G}p^{|S|}.$$

Since $p^{|S|}$ is the probability that $S\subseteq X_p$, a union bound gives $\mu_p(\mathcal F)\leq c_p(\mathcal G)$. Call the family $p$-small when it has a cover of cost at most one half. Its integral expectation threshold is

$$q(\mathcal F)=\max\{p:\mathcal F\text{ is }p\text{-small}\}.$$

A fractional cover assigns coefficients $g(S)\in[0,1]$, requiring

$$\sum_{S\subseteq H}g(S)\geq1 \qquad(H\in\mathcal F).$$

Its cost is $\sum_S g(S)p^{|S|}$. Allowing these weighted covers defines $q_f(\mathcal F)$, again with budget one half. An integral cover is the special case of coefficients zero or one, so

$$q(\mathcal F)\leq q_f(\mathcal F)\leq p_c(\mathcal F).$$

For a simple example, the family of sets of size at least $k$ has the fractional cover $g(\{x\})=1/k$ on singletons. Each successful set accumulates total weight at least one. This illustrates how fractional contributions can be spread over small generators.

3. Development history and previous partial results

Kahn and Kalai proposed that ordinary thresholds are at most a logarithmic factor above expectation thresholds. This connects elementary counting obstructions with the probability of actually obtaining a complete structure.

Frankston, Kahn, Narayanan and Park proved the comparison using fractional expectation thresholds. Park and Pham proved the integral version. If $\ell$ is the larger of two and the maximum size of a minimal member of $\mathcal F$, their theorem gives

$$p_c(\mathcal F)\leq Cq(\mathcal F)\log\ell$$

for a universal constant. A minimal member loses the property whenever any element is removed.

Talagrand’s separate conjecture asked whether $q_f$ and $q$ themselves differ by only a constant. Earlier rounding results handled special supports, such as singletons, pairs and clique-based generators. More general selector methods introduced losses depending on the sizes of the weighted sets. Subsequent results reduced these to iterated logarithms. Park’s September 2026 manuscript gave a dimension-independent comparison still involving $\log\log(1/q)$. M2 claims to remove this remaining dependence.

Talagrand also proposed discrete convexity: sufficiently likely sets should cover most other sets using only a bounded number of unions, with the exceptional family having an inexpensive containment cover. Recent work supplied fractional versions and integral versions at a reduced density. Li’s work on spread measures is an important fractional input.

Finally, Ascoli, He, Park and Talagrand related discrete convexity to graph thresholds and proposed the decomposition resolved in M1. They proved several restricted graph classes, leaving the general interaction between high- and low-degree vertices as a principal obstacle.

4. What the new manuscripts claim

M2: constant-factor rounding

There is a universal constant $C$ such that

$$q_f(\mathcal F)\leq Cq(\mathcal F)$$

for every nonempty proper increasing family on a finite nonempty ground set. Both definitions keep the same covering budget, one half.

More concretely, a fractional cover costing at most one half at density $r$ can be replaced by an integral cover costing at most one half at density $r/C$. The constant is independent of the ground-set size, generator sizes, and number of generators. The paper supplies an explicit, unoptimized constant.

M3: discrete convexity at the same density

For any family $\mathcal D$, let $E_k(\mathcal D)$ consist of sets that are not contained in the union of any $k$ members of $\mathcal D$. Repetitions in that union are allowed.

M3 claims a universal integer $k$ such that

$$\mu_p(\mathcal D)\geq1-\frac1k \quad\Longrightarrow\quad E_k(\mathcal D)\text{ is }p\text{-small}.$$

The family $\mathcal D$ need not be increasing. The covering cost uses exactly the same $p$ as the probability hypothesis.

There is also a different tradeoff: if $\mu_p(\mathcal D)>1/2$, two unions suffice when the covering density is reduced to $p/C'$ for a universal constant $C'$. This combines Li’s fractional theorem with M2. Fewer unions and a weaker probability assumption are obtained at the price of a constant density loss; they are not the same statement as the main same-density theorem.

M1: fixed graph pieces near the expectation threshold

For a graph $H$ on at most $n$ vertices, let $q(H;n)$ be the integral expectation threshold for containing $H$ in $G(n,p)$, where every possible edge appears independently with probability $p$. Let $p_c(H;n)$ be its probability-one-half containment threshold.

M1 claims universal constants $k_0$ and $L$ such that the edges of every $H$ can be partitioned into pieces $H_1,\ldots,H_{k_0}$ with

$$p_c(H_i;n)\leq Lq(H;n) \qquad(1\leq i\leq k_0).$$

Pieces may share vertices or be empty. The partition is chosen before sampling the host graph. Each piece is tested for ordinary, non-induced containment separately. Their successful embeddings need not agree on shared vertices, so the theorem does not directly embed the whole target at density $Lq(H;n)$.

For edgeless targets the paper sets both thresholds to zero. M1 uses M3’s same-density covering theorem as an essential companion input.

5. Why the advance matters

Importance: 5/5. This family addresses central structural questions about random thresholds and the difference between fractional and discrete certificates. The first comparison removes every dimension or generator-size loss, while the discrete-convexity result retains the original density.

The graph decomposition explains one way to remove the logarithmic gap in the general threshold theorem: relax the demand that all edges be embedded in one compatible copy, and a bounded number of predetermined pieces suffice. The number of pieces does not grow with the target.

These statements should be appreciated together without merging them. Constant-factor rounding concerns certificates. Discrete convexity concerns unions of likely sets. Graph decomposition concerns separately embeddable pieces. Their connections give the family broad reach, and their different quantifiers explain why none is merely a restatement of the already established Kahn–Kalai threshold bound.

6. The main idea

Capture one object at many scales

M2 assigns a probability mass to the vertices of each successful set. It then independently gives ground-set elements random integer colors, interpreted as stages of exposure. A selector estimate finds one successful set whose mass is substantially captured at every stage simultaneously.

This simultaneity is crucial. Separate estimates could choose a different successful set at each stage and would provide no common object with controlled total loss. Here the uncaptured masses decrease geometrically, so their sum is bounded. The chosen set consequently has a bounded average stage.

Fractional weights are distributed over their generators’ vertices. A bounded average stage forces a substantial amount of generator weight to occur early. Independence then gives an upper bound on a weighted product sum that conflicts with this forced contribution. The contradiction yields an integral cover at a constant reduction in density.

Turn failure of unions into cover generators

M3 uses an expansion of functions on random subsets into orthogonal components, together with a signed product identity. A set that cannot be covered by the required unions must carry substantial weight in these components.

Large individual weights can be selected directly as inexpensive generators. When weight is distributed across many smaller components, a covering lemma combines high-degree selections with random unions. This produces an integral cover initially at a reduced density.

The final step couples several random rows. Each row separately has the original Bernoulli law, but the rows are dependent so that their union has an exactly prescribed larger density. This recovers the original covering parameter. Independence within each row and careful dependence between rows serve different purposes.

Transfer typical behavior to a graph partition

M1 defines a high-probability class of random graphs with strong embedding properties. Discrete convexity places a labeled copy of the target inside the union of a bounded number of deterministic graphs from that class. Assigning each target edge to one of them begins the partition.

Further splitting separates high-degree vertices, lower-degree regions and edges crossing between them. For crossing pieces, the problem is finding distinct host vertices with prescribed neighborhoods. Hall’s matching condition must hold for every collection of requirements. A compression lemma reduces the tests needed to control all those collections, allowing typical random behavior to transfer to each fixed piece.

7. Scope, limitations, and open questions

The comparison $q_f\leq Cq$ does not imply $p_c\leq Cq$ for every increasing property. The logarithmic gap between certificate thresholds and actual occurrence can be necessary. The new theorem removes the gap between two kinds of certificate, not every threshold gap.

Discrete convexity supplies an inexpensive cover of the exceptional family, which is stronger information than a probability bound alone. Its main theorem requires a very high starting probability and allows a large universal number of unions. The two-union corollary changes both parameters.

The decomposition pieces are fixed before the host is sampled, but their embeddings are separate. Requiring compatible embeddings would recover the whole target and is a substantially stronger request. Likewise, the theorem compares piece thresholds with the original target’s integral threshold, not with a simpler expected-copy parameter for one selected subgraph.

The universal constants are not optimized, and the headline results do not promise efficient algorithms for arbitrary families described implicitly. Their principal contribution is structural existence at the claimed scales.

8. Sources and further reading

M1 is the October 5 graph-decomposition manuscript. M2 gives the constant-factor integral–fractional comparison; M3 gives same-density discrete convexity and explains the two-union tradeoff.

Primary background includes Kahn–Kalai, the fractional threshold theorem, Park–Pham’s integral theorem, Talagrand’s original questions, and Ascoli–He–Park–Talagrand’s decomposition conjecture. The recent Li and Park manuscripts explain the immediate fractional and rounding predecessors.

Source manuscripts

• M1. OpenAI, Graph Decompositions at the Integral Expectation Threshold (October 5, 2026).
• M2. OpenAI, Integral and fractional expectation thresholds are equivalent (September 23, 2026).
• M3. OpenAI, Talagrand’s discrete-convexity conjecture (September 23, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.