Endpoint Pair Multiplicity Simple Graph
ProvedEndpointPairMultiplicitySimpleGraphcrossing-consequencestrellis-port
Let be a finite set of indices and let assign to each index an unordered pair of vertices of . Suppose that no assigned pair is diagonal, and that for every unordered pair in the image of , at most two indices of are assigned to . Then there is a simple graph on with finite edge set such that the edge set of is exactly the image of , and
Formalization Note This node is ported from the Trellis formalization of the crossing lemma and its consequences (wpegden/crossing-consequences, commit 8769d142, W. Pegden, Apache-2.0); the statement is the Trellis node EndpointPairMultiplicitySimpleGraph.
Preamble
import Mathlib.Analysis.InnerProductSpace.PiL2 import Mathlib.Analysis.SpecialFunctions.Pow.Real import Mathlib.Combinatorics.SimpleGraph.Finite import Mathlib.Data.Finset.Prod import Mathlib.Data.Set.Finite.Basic import Mathlib.LinearAlgebra.AffineSpace.AffineSubspace.Basic open Classical open scoped Real noncomputable section
Formal statement
lemma EndpointPairMultiplicitySimpleGraph {ι V : Type*} [DecidableEq ι] [DecidableEq V]
(A : Finset ι) (endpoint : ι → Sym2 V)
(h_nondiag : ∀ i ∈ A, ¬ (endpoint i).IsDiag)
(h_multiplicity : ∀ e ∈ A.image endpoint,
(A.filter (fun i => endpoint i = e)).card ≤ 2) :
∃ G : SimpleGraph V, ∃ (_ : Fintype G.edgeSet),
(A.card : ℝ) / 2 ≤ (G.edgeFinset.card : ℝ) ∧
G.edgeFinset = A.image endpoint := by sorrySource