AFTD Auto-Formalizing Theoretical Domains

mixed_cage_order

def

n(r, z, g): the minimum order of an (r, z)-regular mixed graph of girth g (the order of an (r, z, g)-mixed cage).

Statement

noncomputable def mixed_cage_order (r z g : ℕ) : ℕ
Defined in
arXiv:2610.14110 (New mixed cages, bounds and computational results), Sec. 2 (mixed cages and their order n(r,z,g)).
Verified
17 Oct 2026
Axioms
none listed
Built on 4
  • mixed_graph_is_validA mixed graph on V: undirected edges E (a simple graph) and arcs A, with no loops and at most one edge or arc between two vertices (no…
  • mixed_graph_is_regularA mixed graph is (r, z)-regular when every vertex has r neighbours along edges, z out-neighbours and z in-neighbours along arcs.
  • mixed_graph_has_cycleA mixed graph has a cycle of length t ≥ 3: distinct vertices x_0, ..., x_{t-1} such that each x_i is joined to x_{i+1} (indices mod t) by…
  • mixed_graph_has_girthA mixed graph has girth g: it has a cycle of length g and no shorter cycle.
Used by 3
  • mixed_cage_order_one_girth_threeThe case g = 3 of the conjecture: n(1, z, 3) = N(z, 3), i.e. 2z + 2 for every z ≥ 1 (both parities agree).
  • mixed_cage_order_girth_threeFor all r ≥ 1 and z ≥ 1, the minimum order of an (r, z, 3)-mixed cage is n(r, z, 3) = r + 2z + 1.
  • mixed_cage_order_one_leFor z ≥ 1 and g ≥ 3, n(1, z, g) ≤ N(z, g), where N(z, g) = z(g − 1) + 2 for even z and (z + 1)(g − 1) for odd z: the circulant M(z, g) on…

Lean source view module on GitHub

/-- `n(r, z, g)`: the least `n` such that some `(r, z)`-regular mixed graph on `Fin n` has girth `g` (0 if there is none). -/
noncomputable def mixed_cage_order (r z g : ℕ) : ℕ :=
  sInf {n | ∃ (E : SimpleGraph (Fin n)) (A : Fin n → Fin n → Prop),
    mixed_graph_is_valid E A ∧ mixed_graph_is_regular E A r z ∧ mixed_graph_has_girth E A g}
See it in the graphDiscuss this resultChallenge it