A labelled matching host on any number of vertices
Definitionarexychen_erdos180_families_matchingarexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
For every natural , the graph on has the disjoint edges for , with an isolated last vertex when is odd. The bundle defines the two endpoint maps, the unordered edge map, and the graph. It includes the short proved endpoint-inequality lemma required for looplessness.
Definition code
import Mathlib.Analysis.Asymptotics.Theta
import Mathlib.Combinatorics.SimpleGraph.Acyclic
import Mathlib.Combinatorics.SimpleGraph.Basic
import Mathlib.Combinatorics.SimpleGraph.Finite
import Mathlib.Combinatorics.SimpleGraph.Maps
import Mathlib.Combinatorics.SimpleGraph.Matching
import Mathlib.Combinatorics.SimpleGraph.Subgraph
import Mathlib.Tactic
namespace Arexychen
open Filter
open Asymptotics
noncomputable section
namespace Erdos180
universe u v w
/-- Left endpoint of the `k`th edge in the labelled matching host on `Fin n`. -/
def matchingHostLeft (n : ℕ) (k : Fin (n / 2)) : Fin n :=
⟨2 * k.val, by have hk := k.isLt; omega⟩
/-- Right endpoint of the `k`th edge in the labelled matching host on `Fin n`. -/
def matchingHostRight (n : ℕ) (k : Fin (n / 2)) : Fin n :=
⟨2 * k.val + 1, by have hk := k.isLt; omega⟩
theorem matchingHost_left_ne_right (n : ℕ) (k : Fin (n / 2)) :
matchingHostLeft n k ≠ matchingHostRight n k := by
intro h
have hv := congrArg Fin.val h
simp [matchingHostLeft, matchingHostRight] at hv
/-- The labelled `n`-vertex host consisting of the disjoint edges
`{0,1}, {2,3}, ...`, with one isolated vertex left over when `n` is odd. -/
def matchingHost (n : ℕ) : SimpleGraph (Fin n) where
Adj x y := ∃ k : Fin (n / 2),
(x = matchingHostLeft n k ∧ y = matchingHostRight n k) ∨
(x = matchingHostRight n k ∧ y = matchingHostLeft n k)
symm := by
intro x y h
rcases h with ⟨k, h | h⟩
· exact ⟨k, Or.inr ⟨h.2, h.1⟩⟩
· exact ⟨k, Or.inl ⟨h.2, h.1⟩⟩
loopless := by
constructor
intro x h
rcases h with ⟨k, h | h⟩
· exact matchingHost_left_ne_right n k (h.1.symm.trans h.2)
· exact matchingHost_left_ne_right n k (h.2.symm.trans h.1)
/-- The unordered edge corresponding to the `k`th pair of the matching host. -/
def matchingHostEdge (n : ℕ) (k : Fin (n / 2)) : Sym2 (Fin n) :=
s(matchingHostLeft n k, matchingHostRight n k)
end Erdos180
end
end Arexychen
Source