OctoInformBeta

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

Lemma 2.1 [Existence of the edge labeling]: For a natural number M≥3M\geq3, construction tournaments admit ⌈M⌉\lceil\sqrt M\rceil labels with no agreement at every edge head

Labellings exclude a sixteen-vertex configuration.

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 in the sensitivity and block sensitivity construction concerns a finite tournament and the labels attached to its directed edges. For natural numbers kk and rr, write Vk={0,…,k−1}V_k=\{0,\ldots,k-1\} for the vertex set and [r]={1,…,r}[r]=\{1,\ldots,r\} for the label set. A tournament TT on VkV_k is a directed graph with no loops and exactly one directed edge between each pair of distinct vertices, as in (1); write i→Tji\to_T j for its adjacency relation.✦ i↛Ti,i≠j⇒(i→Tj⇔j↛Ti).i\not\to_T i, \qquad i\ne j\ \Longrightarrow\ \bigl(i\to_T j\ \Longleftrightarrow\ j\not\to_T i\bigr).(1)

A tournament TT with natural parameter MM is regular if it has k=2M2+1k=2M^2+1 vertices and every vertex has exactly M2M^2 outgoing neighbours.✦ For a natural number aa, the cyclic tournament CaC_a is the tournament on V2a+1V_{2a+1} whose edges are given by (2), where (j−i)mod⁡(2a+1)(j-i)\bmod(2a+1) is the least nonnegative residue of j−ij-i.✦ i→Caj⇔1≤(j−i)mod⁡(2a+1)≤a.i\to_{C_a}j \quad\Longleftrightarrow\quad 1\leq (j-i)\bmod(2a+1)\leq a.(2) The regular cyclic tournament TMT_M with natural parameter MM is defined by TM=CM2T_M=C_{M^2}.

Good Labellings

Fix t=16t=16. A good labelling λ\lambda of a tournament TT on VkV_k with rr labels is a map λ:Vk×Vk→[r]\lambda:V_k\times V_k\to[r] satisfying (3).✦ For a tournament TT on VkV_k, 𝒢(T,r)\mathcal G(T,r) is the set of good labellings of TT with rr labels. For every I⊆Vk with |I|=t and every m:Vk→[r],there are i,j∈I such that i→Tjandλ(i,j)≠m(j).\begin{gathered} \text{For every }I\subseteq V_k\text{ with }|I|=t \text{ and every }m:V_k\to[r],\\ \text{there are }i,j\in I\text{ such that } i\to_T j\quad\text{and}\quad\lambda(i,j)\ne m(j). \end{gathered}(3)

The Claim

Theorem 1. Let M≥3M\geq3 be a natural number, and put k=2M2+1k=2M^2+1 and r=⌈M⌉r=\lceil\sqrt M\rceil. For the regular cyclic tournament TMT_M, 𝒢(TM,r)≠⌀.\mathcal G(T_M,r)\ne\varnothing.(4)✦ More generally, let M≥3M\geq3 and rr be natural numbers satisfying M≤r2M\leq r^2, and let TT be any tournament on 2M2+12M^2+1 vertices. Then 𝒢(T,r)≠⌀.\mathcal G(T,r)\ne\varnothing.(5)✦ Let TT be a tournament on VkV_k, let λ∈𝒢(T,r)\lambda\in\mathcal G(T,r), and let I⊆VkI\subseteq V_k have |I|=16|I|=16. For every map m:I→[r]m:I\to[r], ∃i,j∈I:i→Tjandλ(i,j)≠m(j).\exists\,i,j\in I:\qquad i\to_T j\quad\text{and}\quad\lambda(i,j)\ne m(j).(6)✦

In the paper, the result reads: with the stated parameters and regular tournament, the edges admit labels a(i,j)∈[r]a(i,j)\in[r] such that no set II of size tt admits choices mj∈[r]m_j\in[r], j∈Ij\in I, satisfying a(i,j)=mja(i,j)=m_j for every edge i→ji\to j within II.

What Is Checked

The existence assertions (4) and (5) concern finite tournaments with M≥3M\geq3, using respectively r=⌈M⌉r=\lceil\sqrt M\rceil and any rr with M≤r2M\leq r^2; the subset assertion (6) concerns a good labelling and a prescribed label map on a sixteen-vertex subset.