simple_graph_rotation_face_perm
For a simple graph G (explicit argument) and a rotation system given as a permutation σ : Equiv.Perm G.Dart of the darts of G, the face permutation is the permutation of the darts (an Equiv.Perm G.Dart, the product σ * reversal) that sends each dart d to σ(d.symm), where d.symm is d with its direction reversed.
Statement
def simple_graph_rotation_face_perm {V : Type*} (G : SimpleGraph V) (σ : Equiv.Perm G.Dart) : Equiv.Perm G.Dart
- Defined in
- Face tracing for rotation systems (Mohar-Thomassen, Graphs on Surfaces, Sec. 3.2); arXiv:2610.25886 (Extremal arborescences in graph orientations)
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Used by 4
- complete_three_rotation_face_countEvery rotation system of the triangle K_3 has exactly 2 faces (inside and outside), so V - E + F = 3 - 3 + 2 = 2 (sanity check of…
- plane_face_heightA height function for the rotation system σ is a function y from the darts of G to ℤ that is constant on the cycles of the face…
- simple_graph_rotation_face_countFor a finite simple graph G (explicit argument) and a permutation σ : Equiv.Perm G.Dart of its darts, the number of faces of σ is the…
- exists_plane_rotation_system_complete_fourK_4 has a plane rotation system: 4 vertices, 6 edges, 4 faces (sanity check of simple_graph_is_plane_rotation_system).
Read back from the Lean
Given a type V, a simple graph G on V, and a permutation σ of the darts of G (σ : Equiv.Perm G.Dart), simple_graph_rotation_face_perm G σ is defined as the permutation of G.Dart obtained by multiplying σ by the dart-reversal involution SimpleGraph.Dart.symm in the group Equiv.Perm G.Dart. Under standard composition order in Equiv.Perm, this sends each dart d to σ (d.symm).
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
/-- Face-tracing permutation d ↦ σ (d.symm) of a rotation system. -/ def simple_graph_rotation_face_perm {V : Type*} (G : SimpleGraph V) (σ : Equiv.Perm G.Dart) : Equiv.Perm G.Dart := σ * Function.Involutive.toPerm SimpleGraph.Dart.symm (fun d => d.symm_symm)