is_threshold_sequence
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