OctoInformBeta

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

§2 (setting): parameters, regular tournament, and admissible labels: Cyclic orientations and the exclusion of constant incoming labels on sixteen rows

Cyclic tournaments supply regular row orientations.

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 combinatorial setting for the Boolean function construction consists of rows with oriented edges and labels on ordered pairs of rows. The labeling condition concerns sixteen rows at a time and compares edge labels with targets attached to their destinations.

For a natural number kk, let Vk={0,…,k−1}V_k=\{0,\ldots,k-1\} be the row set. For a directed graph TT on VkV_k, write i→Tji\to_T j for an edge from ii to jj. The outneighborhood NT+(i)N_T^+(i) of a row i∈Vki\in V_k is the set in (1), and its outdegree is |NT+(i)||N_T^+(i)|. NT+(i)={j∈Vk:i→Tj}.N_T^+(i)=\{j\in V_k:i\to_T j\}.(1)

For a natural number aa, identify V2a+1V_{2a+1} with the residues modulo 2a+12a+1 and let δa(i,j)\delta_a(i,j) be the representative of j−ij-i in {0,…,2a}\{0,\ldots,2a\}. For a natural number rr, write [r]={0,…,r−1}[r]=\{0,\ldots,r-1\} for the label set.

The Claim

Definition 1. 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 (2). i↛Ti(i∈Vk),i→Tj⇔j↛Ti(i,j∈Vk,i≠j).i\not\to_T i\quad(i\in V_k), \qquad i\to_T j\ \Longleftrightarrow\ j\not\to_T i \quad(i,j\in V_k,\ i\ne j).(2)✦

A regular tournament TT with parameter M∈ℕM\in\mathbb N is a tournament on V2M2+1V_{2M^2+1} satisfying (3). |NT+(i)|=M2(i∈V2M2+1).|N_T^+(i)|=M^2\qquad(i\in V_{2M^2+1}).(3)✦

The cyclic tournament CaC_a on V2a+1V_{2a+1} is the tournament whose edges are given by (4). i→Caj⇔0<δa(i,j)≤a.i\to_{C_a}j\ \Longleftrightarrow\ 0<\delta_a(i,j)\le a.(4)✦ For every natural number aa and every vertex i∈V2a+1i\in V_{2a+1}, its outdegree satisfies (5). |NCa+(i)|=a.|N_{C_a}^+(i)|=a.(5)✦ The regular cyclic tournament RMR_M with parameter M∈ℕM\in\mathbb N is the regular tournament defined by (6). RM=CM2.R_M=C_{M^2}.(6)✦

A good edge labeling λ\lambda of a tournament TT on VkV_k with labels in [r][r] is a map λ:Vk×Vk→[r]\lambda:V_k\times V_k\to[r] satisfying (7). For every I⊆Vk with |I|=16 and every m:Vk→[r],there are i,j∈I such that i→Tj and λ(i,j)≠m(j).\begin{gathered} \text{For every }I\subseteq V_k\text{ with }|I|=16 \text{ and every }m:V_k\to[r],\\ \text{there are }i,j\in I\text{ such that } i\to_T j\text{ and }\lambda(i,j)\ne m(j). \end{gathered}(7)✦

In the paper, the result reads: fix integers d≥1d\ge1 and M≥3M\ge3, set L=d+2L=d+2, k=2M2+1k=2M^2+1, r=⌈M⌉r=\lceil\sqrt M\rceil, and t=16t=16, use a tournament on kk rows that directs exactly one edge between each pair of distinct rows and has outdegree M2M^2 at every row, such as the cyclic tournament, and call a labeling good when it forbids a set II of tt vertices whose incoming edge labels at each destination j∈Ij\in I are all equal to a selected target mjm_j.

What Is Checked

The definitions range over natural-number parameters and finite row sets, with the labeling in (7) defined on every ordered pair of rows.