Cyclic successor is fixed-point-free
ProvedBookSixth.cycSucc_ne_selfcombinatorics
Cyclic successor on a finite set with at least two elements has no fixed point. For , the wraparound map never fixes a point: a fixed point would force , impossible for with . This supplies the distinctness needed to read cycles as edge sets in the random graph model. Formalization Note Lean states it for the explicit cycSucc wraparound function.
Preamble
import Definitions.Def_BookSixthRandomGraph set_option autoImplicit false
Formal statement
theorem BookSixth.cycSucc_ne_self (l : Nat) (hl0 : 0 < l) (hl1 : 1 < l) :
forall i : Fin l, Ne (BookSixth.cycSucc hl0 i) i := by sorrySource
Fixed-point-freeness of cyclic successor, used in the high-girth high-chromatic-number argument, Aigner and Ziegler, Proofs from THE BOOK, Sixth Edition (2018), Chapter 45, https://doi.org/10.1007/978-3-662-57265-8_45