Expectation-threshold covers and graph decompositions

Source and verification

This article explains family 175 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Increasing families and containment certificates

Let $X$ be a finite nonempty set. A family $\mathcal{F}\subseteq 2^X$ is increasing if membership is preserved when elements are added. Write $X_p$ for the random subset retaining each element independently with probability $p$.

A containment cover is a family $\mathcal{C}$ such that every $F\in \mathcal{F}$ contains some $S\in \mathcal{C}$. Its cost is

$$c_p(\mathcal{C})=\sum _{S\in \mathcal{C}}{p}^{|S|}.$$

Since $\mathrm{Pr}(S\subseteq X_p)=p^{|S|}$, the union bound gives $\mathrm{Pr}(X_p\in \mathcal{F})\le c_p(\mathcal{C})$. A cover of cost at most $1/2$ is therefore an explicit certificate of small probability. The integral expectation threshold $q(\mathcal{F})$ is the largest $p$ allowing such a cover.

A fractional cover replaces the choice of generators by weights $g(S)\in [0,1]$, requiring

$$\sum _{S\subseteq F}g(S)\ge 1(F\in \mathcal{F}).$$

Its cost is ${\sum }_{S}g(S)p^{|S|}$. The corresponding threshold is $q_f(\mathcal{F})$. The empty set is allowed among the weighted subsets, with $p^0=1$ even at $p=0$. Expectations give

$$q(\mathcal{F})\le q_f(\mathcal{F})\le p_c(\mathcal{F}),$$

where $p_c$ is the density at which the increasing property has probability $1/2$.

🏷️ Constant-factor rounding

First comparison claim

For every nonempty proper increasing family on a finite nonempty ground set,

$$q_f(\mathcal{F})\le 25\cdot 512^{4}q(\mathcal{F}).$$

Both thresholds use the same budget $1/2$. The constant is independent of the sizes of the weighted subsets and of the ground set. (OpenAI, 2026)

This is a rounding theorem about certificates. It does not remove the logarithmic gap that can occur between an expectation threshold and the actual probability threshold.

The proof uses a multiscale selector. Give each $H\in \mathcal{F}$ a probability mass ${\lambda }_H$ supported on $H$. Independent random colors produce nested random sets $A_1\subseteq \cdots \subseteq A_s$. If a sufficiently cheap integral cover is unavailable, the source finds, with high probability, one common $H$ satisfying

$${\lambda }_H(A_i)\ge 1-2^{-i}(1\le i\le s).$$

If $a(x)$ is the color of $x$, the tail-sum identity then gives

$$\begin{array}{c}\sum _{x}a(x){\lambda }_H(x)\\ =1+\sum _{i=1}^s(1-{\lambda }_H(A_i))\\ \le 2.\end{array}$$

Separate selectors at each scale could choose different $H$ and would not imply this conclusion. The common witness is the new requirement.

Distribute fractional weights equally among the vertices of their supporting sets. The bounded mean color forces a positive amount of fractional mass onto sets with small average color. For a suitable base $B$, products of $Y_x=B^{4-a(x)}$ are large on those sets. Independence bounds the expectation of ${\sum }_{S}g(S){\prod }_{x\in S}{Y}_x$ from above using the original fractional cost, while the selector gives a contradictory lower bound. This comparison avoids a cardinality-dependent loss.

🏷️ Discrete convexity at the original density

For an arbitrary family $\mathcal{D}\subseteq 2^X$, let $E_k(\mathcal{D})$ consist of sets not contained in a union of $k$ members of $\mathcal{D}$. The members may repeat; $\mathcal{D}$ need not be increasing.

Discrete-convexity claim

With $k=2^{75}$, if $\mathrm{Pr}(X_p\in \mathcal{D})\ge 1-1/k$, then $E_k(\mathcal{D})$ has an integral containment cover of cost at most $1/2$ at the same density $p$. (OpenAI, 2026b)

The phrase “same density” matters. A cover affordable at a much smaller parameter would be weaker. The paper also derives a two-union version with a constant density loss from the fractional theorem and rounding, under the weaker assumption $\mathrm{Pr}(X_p\in \mathcal{D})>1/2$.

The direct proof first obtains a cover at reduced density. A signed product over 32 rows converts failure of a union cover into a high-power lower bound on orthogonal-expansion weights. Large weights provide generators directly; remaining weights are grouped and covered through a random union construction. Finally, a coupling of dependent rows preserves each row’s Bernoulli product law while prescribing the density of their union. This exact coupling returns the cover cost to $p$ without assuming monotonicity of $\mathcal{D}$.

As an elementary application, let $\varphi (S)={\sup }_{t\in T}{\sum }_{i\in S}{t}_i$ for nonnegative vectors $t$, and let $M=\mathbb{E}\varphi (X_p)$ be positive and finite. Markov’s inequality makes $\{D:\varphi (D)<kM\}$ sufficiently likely. Monotonicity and subadditivity of $\varphi$ imply that a set with $\varphi (S)\ge k^{2}M$ cannot lie in a union of $k$ such $D$‘s. The theorem supplies containment certificates for this large-value event, beyond its probability estimate.

🏷️ Decomposing graph targets

For a graph $H$ on at most $n$ vertices, use $X=E(K_n)$ and let ${\mathcal{F}}_H$ be the edge sets containing an ordinary, not necessarily induced, copy of $H$. Write $q(H;n)=q({\mathcal{F}}_H)$ and $p_c(H;n)$ for its probability threshold; both are set to zero for edgeless targets.

Graph-decomposition claim

There are absolute constants $k,L$ such that every $H$ has an edge partition into $k$ pieces $H_i$ with $p_c(H_i;n)\le Lq(H;n)$. The pieces may be empty and may share vertices. The partition is fixed before sampling the random host. (OpenAI, 2026a)

Separate embeddings of the pieces need not agree on their shared vertices. Thus the statement does not assert containment of the entire graph at density $Lq(H;n)$.

The discrete-convexity theorem supplies a deterministic cover by a bounded number of graphs belonging to a likely class. The source then splits each initial piece into high-degree, low-degree, and crossing regions. Crossing pieces require distinct images realizing prescribed neighborhoods of a fixed high-degree set. Hall’s condition involves every subfamily of these requirements.

A compression lemma reduces arbitrary families of requirements of size at most $s$ to at most $\lceil 2r^{-s}\rceil$ representative requirements, with a controlled probability of capturing an original one after Bernoulli sprinkling. Concentration for these bounded families can then certify all Hall conditions. The other regions use layered matchings and star forests. The graph theorem imports the same-parameter discrete-convexity claim as an essential companion input.

🏷️ Key steps and proof outlines

Turn a common multiscale witness into a numerical contradiction

Suppose $g$ is a fractional cover affordable at density $r>0$. Put $B=512$, $D=256$, $C=25B^4$, and $p=r/C$. The empty-set weight is at most $1/2$, so for every $H$ in the increasing family,

$$M_H=\sum _{\varnothing \ne S\subseteq H}g(S)\ge 1/2.$$

Distribute each nonempty set’s weight equally among its vertices and normalize by $M_H$, obtaining the probability law ${\lambda }_H$. If no integral cover is affordable at $p$, the multiscale selector gives, with probability at least $9/10$, one $H$ whose mean random color is at most two. (OpenAI, 2026b)

Set $Y_x=B^{4-a(x)}$ and

$$Z=\sum _{\varnothing \ne S\subseteq X}g(S)\prod _{x\in S}{Y}_x.$$

Under weights $g(S)/M_H$, the mean of the average color $\overline{a}(S)$ is at most two. Markov’s inequality leaves at least half the weight on sets with $\overline{a}(S)\le 4$, and on each such set ${\prod }_{x\in S}{Y}_x\ge 1$. Thus $Z\ge M_H/2\ge 1/4$ on the selector event, yielding $\mathbb{E}Z\ge 9/40$.

For the upper bound, choose the largest $s\ge 0$ with $p{\sum }_{i=1}^s{D}^i\le 1/2$. Colors $i\le s$ have probability $D^{i}p$, and the remaining mass gets color $s+1$. Maximality implies $B^{-(s+1)}<4p$, so

$$\mathbb{E}{Y}_x\le B^4\left(p\sum _{i=1}^s{2}^{-i}+4p\right)\le 5B^{4}p=r/5.$$

Independence across vertices gives

$$\mathbb{E}Z\le \sum _{S\ne \varnothing }g(S)(r/5{)}^{|S|}\le \frac{1}{5}\sum _{S\ne \varnothing }g(S)r^{|S|}\le 1/10,$$

contradicting the lower bound. Nonempty sets are essential to the extracted factor $1/5$; separating the empty-set weight at the start closes that boundary case.

Restore the original density with dependent rows

For discrete convexity, let $L=2^{70}$ and $k=32L$. If ${\mu }_p(\mathcal{D})\ge 1-1/k$, any coupling of $L$ rows with marginal law ${\mu }_p$ has all rows in $\mathcal{D}$ with probability at least $1-L/k=31/32$. Independence between rows is unnecessary. (OpenAI, 2026c)

When $Lp<1$, independently at each coordinate choose either no row, with probability $1-Lp$, or exactly one of the $L$ rows, each with probability $p$. Every row has independent Bernoulli-$p$ coordinates, but their union is Bernoulli with density $q=Lp$. Let $\mathcal{F}$ consist of unions of $L$ members of $\mathcal{D}$. It has ${\mu }_q$-probability at least $31/32$. The earlier reduced-density theorem gives a cover of $E_{32}(\mathcal{F})$ affordable at $q/L=p$, and grouping unions gives $E_{32}(\mathcal{F})=E_k(\mathcal{D})$ exactly.

When $Lp\ge 1$, assign each coordinate a mandatory uniformly chosen row, then include it in each other row with probability $t=(p-1/L)/(1-1/L)$. Every row again has density $p$, while their union is always the full ground set. A positive-probability outcome has all rows in $\mathcal{D}$, so $E_k(\mathcal{D})$ is empty. This includes $Lp=1$ with $t=0$. The construction uses only marginal probabilities and exact unions, so no monotonicity assumption on $\mathcal{D}$ is hidden in the transfer.

Compress neighborhood requirements by paying for probability gain

The graph-decomposition companion needs uniform control of many potential Hall obstructions. Its “Compression after a random extension” lemma has a short useful proof. Let $\mathcal{R}$ be nonempty subsets of a finite set, each of size at most $s$, and let $Z$ be a Bernoulli-$r$ set. A set satisfies a family when it contains at least one member. (OpenAI, 2026a)

Start with no selected requirements. Add $T\in \mathcal{R}$ whenever

$$\mathbb{P}(Z\text{ satisfies the selected family}\mid T\subseteq Z)<1/2.$$

Each addition raises the satisfaction probability by more than $r^{|T|}/2\ge r^s/2$. Since a probability cannot exceed one, fewer than $2r^{-s}$ additions occur. At termination, every original $T$ has conditional success probability at least one half. The conditional law given $T\subseteq Z$ is exactly $T\cup Z^{\prime }$ for a fresh Bernoulli sample $Z^{\prime }$. Therefore every set containing an original requirement satisfies a selected requirement after sprinkling with probability at least one half.

The conclusion is probabilistic after extension, not deterministic containment in the small subfamily. This bounded representative family is what makes uniform concentration and the subsequent neighborhood matching feasible. The three manuscripts connect through these distinct outputs: rounding certificates, same-density union covers, and bounded descriptions of graph-neighborhood constraints.

See Also

• Graph expectation thresholds compares containment with individual subgraph counts, a smaller parameter than a general covering threshold.
• Symmetric threshold widths controls how quickly probability changes, rather than where its midpoint lies.

🏷️ Manuscripts and verification scope

• Graph Decompositions at the Integral Expectation Threshold — pinned manuscript and companion source.
• Integral and fractional expectation thresholds are equivalent — pinned manuscript and companion source.
• Talagrand’s discrete-convexity conjecture — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects integral–fractional comparison and same-density discrete convexity. It does not document the graph-decomposition companion. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. Graph Decompositions at the Integral Expectation Threshold.

🐻  OpenAI 2026b. Integral and fractional expectation thresholds are equivalent.

🐻  OpenAI 2026c. Talagrand’s discrete-convexity conjecture.