OctoInformBeta

OpenAI preprint, September 2026 · §2. The labelled tournament and nested predicates

§2 (proof of Lemma 2.1): uniform labels and the union bound: Exact probabilities and a union bound below one for M≥3M\ge3 at k=2M2+1k=2M^2+1, r=⌈M⌉r=\lceil\sqrt M\rceil

A probability bound for forbidden labellings.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The labelling problem asks whether the edges of a fixed tournament can be labelled so that no set of sixteen vertices has a common incoming label at each vertex.

Write [a]={1,…,a}[a]=\{1,\ldots,a\} for a nonnegative integer aa. A tournament TT on [k][k] is a directed graph with no loops and exactly one directed edge between each pair of distinct vertices.✦ Write i→Tji\to_T j for an edge from ii to jj. For a positive integer rr, a labelling AA of a tournament TT on [k][k] is a map from [k]×[k][k]\times[k] to [r][r]. The probability space Ω=[r][k]×[k]\Omega=[r]^{[k]\times[k]} gives all these labels independently and uniformly; write Pr\Pr for its probability measure.

For a nonnegative integer nn and maps v:[n]→[k]v:[n]\to[k] and m:[n]→[r]m:[n]\to[r], the prescribed incoming label event Ev,m⊆ΩE_{v,m}\subseteq\Omega requires distinct listed vertices and label m(j)m(j) on every internal edge ending at v(j)v(j), as in (1): Ev,m={{A∈Ω:A(v(i),v(j))=m(j) whenever v(i)→Tv(j)},v is injective,⌀,v is not injective.E_{v,m}= \begin{cases} \{A\in\Omega:\ A(v(i),v(j))=m(j) \text{ whenever }v(i)\to_T v(j)\},&v\text{ is injective},\\ \varnothing,&v\text{ is not injective}. \end{cases}(1) A bad labelling A∈ΩA\in\Omega for size nn is a labelling belonging to Ev,mE_{v,m} for some maps v:[n]→[k]v:[n]\to[k] and m:[n]→[r]m:[n]\to[r]; the set BnB_n of all such labellings is defined in (2): Bn=⋃v:[n]→[k]⋃m:[n]→[r]Ev,m.B_n=\bigcup_{v:[n]\to[k]}\ \bigcup_{m:[n]\to[r]}E_{v,m}.(2) Set t=16t=16 and B=BtB=B_t.

The Claim

Theorem 1. Let TT be a tournament on [k][k], and let rr be a positive integer. For an injective map v:[n]→[k]v:[n]\to[k] and any assignment m:[n]→[r]m:[n]\to[r], Pr⁡(Ev,m)=1r(n2).\Pr(E_{v,m})=\frac{1}{r^{\binom n2}}.(3)✦ If k2≥120k^2\ge120, then Pr⁡(B)≤k16r104.\Pr(B)\le\frac{k^{16}}{r^{104}}.(4)✦ If M≥3M\ge3, k=2M2+1k=2M^2+1, and M≤r2M\le r^2, then Pr⁡(B)<1.\Pr(B)<1.(5)✦ For M≥3M\ge3 and k=2M2+1k=2M^2+1, the numerical estimate is k16⌈M⌉104≤(3M2)16(M)104=316M20<1.\frac{k^{16}}{\lceil\sqrt M\rceil^{104}} \le\frac{(3M^2)^{16}}{(\sqrt M)^{104}} =\frac{3^{16}}{M^{20}}<1.(6)✦

In the paper, the result reads: for a fixed set II of t=16t=16 vertices and an assignment (mj)j∈I(m_j)_{j\in I}, independent uniform labels satisfy all internal edge equalities with probability r−(t2)r^{-\binom t2}, and the probability of any violation is at most k16r−104≤316M−20<1k^{16}r^{-104}\le3^{16}M^{-20}<1 for M≥3M\ge3, k=2M2+1k=2M^2+1, and r=⌈M⌉r=\lceil\sqrt M\rceil.

What Is Checked

The statements (3) and (4) concern arbitrary finite tournaments with independent uniform labels on all ordered vertex pairs, with an injective vertex list in (3) and k2≥120k^2\ge120 in (4); (5) uses M≥3M\ge3 and M≤r2M\le r^2 at k=2M2+1k=2M^2+1, while (6) concerns the choice r=⌈M⌉r=\lceil\sqrt M\rceil.