An Explicit Obstruction to Uniform Two-Word π-Representability

Abstract

Adamson, Dietz, Fleischmann, Huch, and Sacher introduced the hierarchy 𝒢_k of graphs represented by two k-uniform words under equality of two-letter projections. They proved that no fixed level contains every graph and asked for an explicit graph outside 𝒢₂. We first recast the word condition: G ∈ 𝒢_k if and only if Ḡ is the image of a permutation graph under a graph compaction whose fibres all have size k. Equivalently, G is obtained from a dimension-at-most-two poset partitioned into k-element chains, with two distinct quotient vertices adjacent when the union of their chains is a chain. Using the two-order form of this characterization, we encode every outside-neighborhood trace on an m-vertex set by two weak compositions and obtain the bound binom(k(m + 1), k)². For k = 2 and m = 20 this bound is 741321, so the bipartite graph with parts [20] and {0,…,741321}, where i is adjacent to j exactly when bit i of j is 1, lies outside 𝒢₂. The same trace estimates place the standard open-neighborhood VC-dimension of 𝒢₂ between 10 and 19. We quantify the gap between this explicit construction, a 35-vertex counting argument, and exact small trace capacities. A reproducible artifact supplies independent exact checks and a scoped Lean 4 formalization of the order bridge and finite arithmetic.