AFTD Auto-Formalizing Theoretical Domains

is_threshold_sequence

def

A degree sequence d on n vertices is a threshold degree sequence if there exists a simple graph G on n vertices with degree sequence d having no induced 2K_2, C_4, or P_4.

Statement

def is_threshold_sequence {n : ℕ} (d : Fin n → ℕ) : Prop
Defined in
arXiv:2611.02191 Sec. 11.2; Chvátal and Hammer (1977)
Verified
05 Nov 2026
Axioms
none listed
Used by 2
  • threshold_loopless_digraph_ge_oneFor every natural number n and every threshold degree sequence d on n vertices, there exists at least one loopless digraph with in-degree…
  • threshold_loopless_digraph_twoFor every threshold degree sequence d on 2 vertices, the number of loopless digraphs with in-degree and out-degree equal to d is 1.

Read back from the Lean

Given $n \in \mathbb{N}$ and a sequence of natural numbers $d : \text{Fin } n \to \mathbb{N}$, is_threshold_sequence d asserts that there exists a simple graph $G$ with vertex set $\text{Fin } n$ such that: 1. For all four vertices $a, b, c, d' \in \text{Fin } n$, if $a, b, c, d'$ are pairwise distinct (i.e., $[a, b, c, d']$ has no duplicates), then none of the following three induced subgraph configurations hold: - $G$ has edges $\{a, b\}$ and $\{c, d'\}$, and no edges among $\{a, c\}$, $\{a, d'\}$, $\{b, c\}$, and $\{b, d'\}$ (an induced $2K_2$); - $G$ has edges $\{a, b\}$, $\{b, c\}$, $\{c, d'\}$, and $\{d', a\}$, and no edges $\{a, c\}$ or $\{b, d'\}$ (an induced $C_4$); - $G$ has edges $\{a, b\}$, $\{b, c\}$, and $\{c, d'\}$, and no edges among $\{a, c\}$, $\{a, d'\}$, and $\{b, d'\}$ (an induced $P_4$). 2. For every vertex $v \in \text{Fin } n$, the degree of $v$ in $G$ equals $d(v)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A degree sequence d on Fin n is a threshold degree sequence if it is realized by a simple graph with no induced 2K₂, C₄, or P₄. -/
def is_threshold_sequence {n : ℕ} (d : Fin n → ℕ) : Prop := open scoped Classical in
  ∃ G : SimpleGraph (Fin n),
    (∀ a b c d : Fin n, [a, b, c, d].Nodup →
      ¬ (G.Adj a b ∧ G.Adj c d ∧ ¬ G.Adj a c ∧ ¬ G.Adj a d ∧ ¬ G.Adj b c ∧ ¬ G.Adj b d) ∧
      ¬ (G.Adj a b ∧ G.Adj b c ∧ G.Adj c d ∧ G.Adj d a ∧ ¬ G.Adj a c ∧ ¬ G.Adj b d) ∧
      ¬ (G.Adj a b ∧ G.Adj b c ∧ G.Adj c d ∧ ¬ G.Adj a c ∧ ¬ G.Adj a d ∧ ¬ G.Adj b d)) ∧
    ∀ v : Fin n, G.degree v = d v
See it in the graphDiscuss this resultChallenge it