AFTD Auto-Formalizing Theoretical Domains

simple_graph_rotation_face_perm

def

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)
See it in the graphDiscuss this resultChallenge it