Seven-vertex exception family from Theorem 8.35
DefinitionSparseDisc_Supplement_IsSevenExceptiongraph-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
A graph is a seven-vertex exception when it is and the edge-bearing part of is isomorphic to a subgraph of , , or . This is exactly the exception family in Theorem 8.35.
Definition code
import Mathlib
import Definitions.Def_SparseDisc_Supplement_EdgeEmbedsInto
namespace SparseDisc.Supplement
/-- The seven-vertex exceptions of Theorem 8.35: `K₇ - E(F)` where the edge-bearing part of `F`
is isomorphic to a subgraph of `C₄`, `3K₂`, or `K₃` (Zeng–Cao–Dai–Wang–Liao, *Sparse
Discrepancy Beyond Additive Functions*, STOC 2027 submission manuscript (sha256
0f09ec60…25b81), p.45).
**Formalization Note** `3K₂` has vertex type `Fin 3 × Bool`, with the two vertices sharing their
first coordinate adjacent. Isolated vertices of the omitted-edge graph are suppressed by
`EdgeEmbedsInto`, matching the paper's graph-isomorphism convention. -/
def IsSevenException {V : Type} [Fintype V] (G : SimpleGraph V) : Prop :=
Fintype.card V = 7 ∧ ∃ F : SimpleGraph V, G = (⊤ \ F) ∧
(EdgeEmbedsInto F (SimpleGraph.cycleGraph 4) ∨
EdgeEmbedsInto F (SimpleGraph.fromRel (fun a b : Fin 3 × Bool => a.1 = b.1 ∧ a.2 ≠ b.2)) ∨
EdgeEmbedsInto F (⊤ : SimpleGraph (Fin 3)))
end SparseDisc.Supplement
Source
Zeng–Cao–Dai–Wang–Liao, Sparse Discrepancy Beyond Additive Functions, STOC 2027 submission (manuscript sha256 0f09ec60…), Theorem 8.35, p.45