simple_graph_reconfiguration_diam_gt_matching
The predicate on a natural number Δ asserting that there exists a finite simple graph G on a finite type V with decidable equality and decidable adjacency such that G has maximum degree equal to Δ and the sum of the cardinality of V (coerced to ℕ∞) and the matching number graph_matching_num G is strictly less than the diameter of the (Δ+2)-colouring reconfiguration graph (simple_graph_reconfiguration_graph G (Δ + 2)).diam.
Statement
def simple_graph_reconfiguration_diam_gt_matching (Δ : ℕ) : Prop
- Defined in
- arXiv:2611.17022 Sec. 8, Question 3
- Verified
- 14 Nov 2026
- Axioms
- none listed
- Built on 2
- simple_graph_reconfiguration_graphFor a simple graph G and a natural number k, the k-reconfiguration graph of G is the simple graph whose vertices are the proper…
- graph_matching_numThe matching number of a graph G is the supremum of the cardinalities of the edge sets of all matchings in G.
- Used by 3
- op_1611_target_of_eight_and_threeIf 8 satisfies the witness predicate and no Δ ≤ 3 does, then there is a unique Δ with 4 ≤ Δ ≤ 8 that is least in the set of witnesses.
- op_1611_min_max_degree_le_eightThe natural number 8 satisfies simple_graph_reconfiguration_diam_gt_matching 8.
- min_max_degree_superlinear_matching_recoloring_diameterThe minimal maximum degree for super-linear matching recoloring diameter: the infimum sInf of the set of natural numbers Δ satisfying…
Read back from the Lean
For a given natural number Δ, simple_graph_reconfiguration_diam_gt_matching Δ asserts that there exist:
1. A type V with Fintype V and DecidableEq V instances, and
2. A simple graph G on V with a DecidableRel G.Adj instance,
such that:
- The maximum degree of G is Δ (G.maxDegree = Δ), and
- The sum (in ℕ∞) of the number of vertices of V (Fintype.card V) and the matching number of G (graph_matching_num G, defined as the supremum of M.edgeSet.encard over all matching subgraphs M of G) is strictly less than the diameter (diam) of the reconfiguration graph of proper (Δ + 2)-colorings of G (where two colorings c₁, c₂ : G.Coloring (Fin (Δ + 2)) are adjacent if and only if they differ on exactly one vertex).
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
/-- Predicate on Δ : ℕ asserting existence of a finite graph with maxDegree Δ whose (Δ+2)-recoloring diameter exceeds |V| + μ. -/ def simple_graph_reconfiguration_diam_gt_matching (Δ : ℕ) : Prop := ∃ (V : Type) (_ : Fintype V) (_ : DecidableEq V) (G : SimpleGraph V) (_ : DecidableRel G.Adj), G.maxDegree = Δ ∧ (Fintype.card V : ℕ∞) + graph_matching_num G < (simple_graph_reconfiguration_graph G (Δ + 2)).diam