AFTD Auto-Formalizing Theoretical Domains

cyclic_two_orientation

def

The orientation of the complete graph on n vertices with arcs i -> i+1 and i -> i+2 (mod n).

Statement

def cyclic_two_orientation (n : ℕ) (i j : Fin n) : Bool
Defined in
Fair Orientations: Proportionality and Equitability, arXiv:2602.18098 v2, Sec. 2 (relevant items, proportional share PROP_i = sum_{e in E_i} v_i(e)/n_e); PROPm as introduced at IJCAI 2021, with the maximin value restricted to relevant items as PROPX is in Def. 2.2; formalized by the operator (Claude), 2026-10-03
Verified
03 Oct 2026
Axioms
none listed
Used by 2
  • propm_orientation_exists_of_le_fiveEvery loopless multigraph on at most five agents with nonnegative additive valuations admits a PROPm orientation (with the PROPm slack…
  • propm_cyclic_two_orientationFor n at most 5, the cyclic orientation i -> i+1, i+2 of the complete graph covers every pair and has out-degree at most two.

Lean source view module on GitHub

/-- The orientation `i → i + 1, i → i + 2 (mod n)` of the complete graph on `Fin n`. -/
def cyclic_two_orientation (n : ℕ) (i j : Fin n) : Bool :=
  decide ((j.val + n - i.val) % n = 1 ∨ (j.val + n - i.val) % n = 2)
See it in the graphDiscuss this resultChallenge it