OctoInformBeta

OpenAI preprint, September 2026 · §2. From a counterexample to a strict subset inequality

Lemma 2.3: The mm-fold blow-up of an oriented digraph with positive indegree keeps both properties and, when mm exceeds the number of vertices, turns the subset deficit into strict growth

Tournament blow-ups and the passage to strict growth.

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 DD be a digraph on a finite vertex set VV, with arcs written u→wu \to w, and let mm be a natural number. The mm-fold blow-up of DD is the digraph GG on the vertex set V×[m]V \times [m], where [m]={1,…,m}[m] = \{1, \dots, m\}, with an arc (u,a)→(w,b)(u, a) \to (w, b) whenever u→w,oru=w and a<b.u \to w, \quad\text{or}\quad u = w \text{ and } a < b.(1)✦

The lemma asks which properties of DD pass to GG, and how a set of vertices of GG grows in one and in two steps along arcs, compared with the set of its first coordinates in DD. The library states eight facts: three properties of GG, four facts on how sets of vertices of GG grow along arcs, and an inequality between the sizes of three finite sets.

Images and Conditions on Digraphs

The image F(S)F(S) of a set SS of vertices of a digraph is the set of vertices that receive an arc from a vertex of SS: F(S)={y:x→y for some x∈S}.F(S) = \{\, y : x \to y \text{ for some } x \in S \,\}.(2)✦ The set F(S)F(S) can meet SS. The map F2F^2 is the composition F∘FF \circ F of the image map with itself. Where both graphs are in play, FDF_D and FGF_G are the images in DD and in GG.

A digraph DD is oriented when it has no loop v→vv \to v and no pair of opposite arcs u→wu \to w and w→uw \to u✦, and DD has positive indegree when every vertex vv has an in-neighbor, a vertex uu with u→vu \to v.✦

A set SS of vertices of a digraph on VV is proper when S≠VS \neq V. A digraph DD satisfies the subset deficit when every nonempty proper set SS of its vertices has |F2(S)\F(S)|<|F(S)\S|,|F^2(S) \setminus F(S)| < |F(S) \setminus S|,(3)✦ and DD has strict growth when every nonempty proper set SS of its vertices has |S|+|F2(S)|<2|F(S)|.|S| + |F^2(S)| < 2|F(S)|.(4)✦

The Claim

Theorem 1. Let DD be a digraph on a finite vertex set VV, let mm be a natural number, and let GG be the mm-fold blow-up of DD. If DD is oriented, then G is oriented.G \text{ is oriented}.(5)✦ If DD has positive indegree, then G has positive indegree.G \text{ has positive indegree}.(6)✦ If DD is oriented, has positive indegree, satisfies the subset deficit and has fewer than mm vertices, then G has strict growth.G \text{ has strict growth}.(7)✦ For every set UU of vertices of GG, with S={v:(v,a)∈U for some a}S = \{v : (v, a) \in U \text{ for some } a\} the set of first coordinates of its vertices, (FD(S)\S)×[m]⊆FG(U)\U,(F_D(S) \setminus S) \times [m] \subseteq F_G(U) \setminus U,(8)✦ FG2(U)\FG(U)⊆(FD2(S)\FD(S))×[m],F_G^2(U) \setminus F_G(U) \subseteq (F_D^2(S) \setminus F_D(S)) \times [m],(9)✦ |U\FG(U)|≤|V|,|U \setminus F_G(U)| \le |V|,(10)✦ and if DD has positive indegree and S=VS = V, then FG(U)=V×[m].F_G(U) = V \times [m].(11)✦ For finite subsets UU, XX and YY of any set, if |U\X|+|Y\X|<|X\U||U \setminus X| + |Y \setminus X| < |X \setminus U|, then |U|+|Y|<2|X|.|U| + |Y| < 2|X|.(12)✦

In the paper, the result reads: if DD is an oriented graph on n=|V|≥1n = |V| \ge 1 vertices, all of positive indegree, that satisfies the subset deficit, and m>nm > n is an integer, then the digraph GG obtained by replacing each vertex by a transitive tournament on mm vertices and each arc v→wv \to w by all arcs from the block at vv to the block at ww is oriented, has all indegrees positive, and satisfies |U|+|FG2(U)|<2|FG(U)||U| + |F_G^2(U)| < 2|F_G(U)| for every nonempty proper set UU of its vertices.

What Is Checked

The claim is stated over a digraph DD on a finite vertex set VV and its mm-fold blow-up GG, the images FDF_D and FGF_G, and four conditions on a digraph: being oriented, positive indegree, the subset deficit and strict growth.