OctoInformBeta

OpenAI preprint, September 2026 · §3. Restricting to the edges incident with a vertex block

§3: Vertex blocks and uniform block sampling: Supported permutations fix exterior vertices, and blocks of a prescribed size are sampled uniformly

Vertex blocks free their incident edges.

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

Let VV be a set of nn labelled vertices, and let EnE_n be the set of all two-element subsets of VV, called potential edges.✦ A graph on VV is an assignment x∈{0,1}Enx\in\{0,1\}^{E_n}, with xe=1x_e=1 meaning that ee is present. A vertex block B⊆VB\subseteq V specifies the free coordinates in a restriction of a graph property.

For a finite set UU and a nonnegative integer mm, let (Um)\binom{U}{m} denote the family of mm-element subsets of UU. Let PP be a predicate on subsets of UU.

The Definition

Definition 1. The incident edge set FB⊆EnF_B\subseteq E_n of a vertex block B⊆VB\subseteq V is the set of potential edges incident with BB, meaning those that meet BB, as in (1): FB={e∈En:e∩B≠⌀}.F_B=\{e\in E_n:e\cap B\ne\varnothing\}.(1)✦ The coordinates indexed by FBF_B are free; an exterior assignment specifies xex_e for every e∈En\FBe\in E_n\setminus F_B.

A permutation π\pi of VV is supported on BB when it satisfies (2): π(v)=vfor every v∈V\B.\pi(v)=v\qquad\text{for every }v\in V\setminus B.(2)✦

The uniform mm-subset probability ℙU,m(P)\mathbb{P}_{U,m}(P) is the proportion of members of (Um)\binom{U}{m} satisfying PP, as in (3), with value zero when the denominator is zero: ℙU,m(P)=|{B∈(Um):P(B)}|(|U|m).\mathbb{P}_{U,m}(P) =\frac{\bigl|\{B\in\binom{U}{m}:P(B)\}\bigr|}{\binom{|U|}{m}}.(3)✦

In the paper, the result reads: for an mm-element vertex block BB, FBF_B consists of every edge with at least one endpoint in BB, including edges within BB, only edges with both endpoints outside BB are fixed, BB is chosen uniformly among all mm-element subsets of VV, and permutations supported on BB fix every exterior assignment individually.

What Is Checked

The definitions are stated over potential edges on nn labelled vertices, blocks B⊆VB\subseteq V and permutations of VV, and over predicates on subsets of an arbitrary finite set UU with a prescribed nonnegative size mm.