simple_graph_cycle_power
def
The k-th power C_n^k of the cycle C_n: vertices are the residues mod n, and two distinct vertices are adjacent when their distance along the cycle, min((u - v) mod n, (v - u) mod n), is at most k.
Statement
def simple_graph_cycle_power (n k : ℕ) : SimpleGraph (ZMod n)- Defined in
- arXiv:2610.15635 (Covering powers of cycles with equivalence subgraphs), Sec. 1 (definition of the k-th power of a cycle).
- Verified
- 17 Oct 2026
- Axioms
- none listed
- Used by 53
- simple_graph_cycle_power_clique_arcFor n at least 3k+1, every nonempty clique of the k-th cycle power lies in a forward arc of k+1 vertices whose first vertex belongs to the…
- simple_graph_equivalence_covering_number_cycle_power_large_upperFor every natural k at least one and natural n at least max(2*k+2, twice the square of k), the equivalence covering number of the k-th…
- simple_graph_cycle_power_seven_adj_iffFor n ≥ 22, u and v are adjacent in C_n^7 iff v = u + e for an integer e with 0 < |e| ≤ 7.
- simple_graph_cycle_power_seven_cover_four_tight_alternateIn a tight cover of C_n^7 (n >= 22) by 4 equivalence subgraphs in which every class starting at i (the class of the distance-7 pair (i,…
- simple_graph_cycle_power_dyadic_class_model_vertex_layersFor an optimal (m+1)-layer dyadic cover, with ell(p) the unique layer covering the endpoint pair (p, p+2^m-1) and the class of p cut to…
- simple_graph_has_equivalence_cover_cycle_power_large_upperFor natural k at least one and n at least max(2k+2,twice the square of k), the k-th cycle power on n vertices has an equivalence cover…
- simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvdFor every n ≥ 10 not divisible by 4, the cube C_n^3 of the n-cycle cannot be covered by 3 equivalence subgraphs; with the lower bound eq ≥…
- simple_graph_cycle_power_dyadic_cover_fibre_endpoint_uniqueIn any clique labeling of the cycle power C_n^{2^m-1} with n ≥ 3(2^m-1)+1, each clique contains at most one pair at distance 2^m-1.
- simple_graph_equivalence_covering_number_cycle_power_geFor k ≥ 1 and n ≥ 2k + 2, eq(C_n^k) ≥ 1 + ⌈log₂(k + 1)⌉.
- simple_graph_equivalence_covering_number_cycle_power_three_of_mod_four_eq_twoFor every n ≥ 10 with n ≡ 2 (mod 4), eq(C_n^3) = 4 = 2 + ⌈log₂ 4⌉. This settles the case k = 3 (m = 2) of the open problem: for even n ≥…
- simple_graph_equivalence_covering_number_cycle_power_fifteen_of_not_dvdFor every even n ≥ 3825 = 15²·17 not divisible by 16, the equivalence covering number of the 15th power of the n-cycle is 6 = 2 + ⌈log₂…
- simple_graph_equivalence_covering_number_cycle_power_dyadic_upperFor natural k,m,n with k at least one, k+1 equal to 2 to the power m, and n at least max(2*k+2, twice the square of k), the equivalence…
- simple_graph_cycle_power_seven_cover_four_tight_one_iff_sixIn a tight cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs (every distance-7, 6, 4 pair covered exactly once, every class spanned by a…
- simple_graph_not_has_equivalence_cover_cycle_power_seven_of_not_dvdFor n ≥ 22 not divisible by 8, C_n^7 cannot be covered by 4 equivalence subgraphs; this is the lower bound eq(C_n^7) ≥ 5 = m + 2 of the…
- simple_graph_cycle_power_rooted_clique_arcLet n,k be natural numbers with n nonzero and n at least3k+1. Let c label the vertices of the k-th cycle power so that two distinct…
- simple_graph_cycle_power_dyadic_layer_weight_leIn any clique labelling of a cycle power with dyadic bandwidth 2^m-1 and n at least three times the bandwidth plus one, the total layer…
- simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvdFor every n ≥ 98 not divisible by 8, the equivalence covering number of the 7th power of the n-cycle is 5 = 2 + ⌈log₂ 8⌉. This settles the…
- simple_graph_cycle_power_dyadic_class_model_layer_choiceThere is a periodic integer layer map ell assigning to each integer p the unique layer covering the endpoint pair (p, p+2^m-1), with…
- simple_graph_cycle_power_dyadic_cover_class_modelEvery optimal dyadic cycle-power equivalence cover admits a faithful periodic integer class model with the original rooted classes and…
- simple_graph_cycle_power_seven_layer_weight_leLet n ≥ 22 and let c label the vertices of C_n^7 so that every label class is a clique. Then Σ_i (2·[i ~ i+7] + [i ~ i+6] + [i ~ i+4]) ≤…
- simple_graph_cycle_power_six_one_sanitySanity check: in C_6 (the first power of the 6-cycle), vertices 0 and 5 are adjacent (they wrap around) and 0 and 2 are not.
- simple_graph_equivalence_covering_number_cycle_power_forty_six_threeeq(C_46^3) = 4: the smallest case of the open problem (k = 3, n = 46 even, 4 ∤ 46, 46 ≥ 45), where the paper only knows eq ∈ {3, 4, 5}.
- simple_graph_cycle_power_dyadic_cover_card_boundFor dyadic bandwidth 2^m-1 and n at least three times the bandwidth plus one, every equivalence cover of the cycle power uses at least m+1…
- simple_graph_equivalence_covering_number_cycle_power_two_pow_even_not_dvd_of_fold_countConditional reduction of OP-205 to a single count identity plus a middle-bit lemma: if for every t ≥ 4 every model at exponent t+1 has…
- simple_graph_cycle_power_fifteen_adj_iffFor n at least 46, adjacency in the fifteenth power of the cycle is displacement by a nonzero integer of absolute value at most 15.
- simple_graph_cycle_power_three_layer_weight_eq_impIn the situation of the weight inequality, if Σ_i (2·[c i = c(i+3)] + [c i = c(i+2)]) = n then every class contains a pair at distance 3…
- simple_graph_equivalence_covering_number_cycle_power_two_pow_even_not_dvd_of_alternating_endpointConditional reduction of OP-205 to alternation and endpoint-only classes: if for every m ≥ 5 every tight, exactly dyadically covered,…
- simple_graph_has_equivalence_cover_cycle_power_dyadic_upperFor natural k at least one with k+1 equal to2 to the power m and n at least max(2k+2,twice the square of k), the k-th cycle power on n…
- simple_graph_cycle_power_dyadic_cover_edge_spanIf a monochromatic clique contains v and v+d with 1 ≤ d < 2^m, its root v-a (with a ≤ 2^m-1) satisfies a < 2^m - d, so the entire edge {v,…
- cycle_strong_product_not_has_equivalence_cover_threeFor every m ≥ 6 and n ≥ 5, the strong product of cycles C_m and C_n (simple_graph_strong_prod of simple_graph_cycle_power m 1 and…
- simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shapeUnder the numerical hypotheses of OP-205, the equivalence covering number is m+2 PROVIDED that every tight, exactly dyadically covered,…
- simple_graph_cycle_power_adj_iff_val_ltFor a nonzero natural n, natural k, and vertices u,v of ZMod n with u.val less than v.val, adjacency in the k-th cycle power is equivalent…
- simple_graph_cycle_power_dyadic_cover_class_spanningEvery label class of an optimal m+1-layer cover at dyadic bandwidth is spanned by an endpoint-distance pair: each vertex lies in a class…
- simple_graph_cycle_power_dyadic_class_model_exact_dyadicFor every j < m and every integer vertex v there is exactly one offset a < 2^j such that the rooted class at a from v is active at both a…
- simple_graph_cycle_power_seven_cover_four_tight_dvdA tight cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs (every distance-7, 6, 4 pair covered exactly once, every class spanned by a…
- simple_graph_cycle_power_seven_cover_four_tightIn any cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs, every pair at distance 7, 6 or 4 is covered by exactly one layer, and every…
- simple_graph_cycle_power_three_cover_three_tightIf three equivalence subgraphs (labellings c_0, c_1, c_2 with clique classes) cover C_n^3, n ≥ 10, then every pair at distance 3 and every…
- simple_graph_equivalence_covering_number_cycle_power_of_leIf 2 ≤ n ≤ 2k + 1 then every two vertices of C_n are at cyclic distance at most k, so C_n^k = K_n and eq(C_n^k) = 1.
- simple_graph_cycle_power_seven_layer_weight_eq_class_five_imp_one_two_imp_sixLet c label the vertices of C_n^7 (n ≥ 22) so that every label class is a clique, with total weight Σ_i (2·[i ~ i+7] + [i ~ i+6] + [i ~…
- simple_graph_cycle_power_dyadic_cover_layer_root_uniqueIn an optimal (m+1)-layer cover of C_n^{2^m-1}, for each layer s and each vertex v, there is a unique offset a ≤ 2^m-1 such that v-a is…
- simple_graph_cycle_power_three_layer_weight_leLet n ≥ 10 and let c label the vertices of C_n^3 so that every label class is a clique. Then Σ_i (2·[i and i+3 share a class] + [i and i+2…
- simple_graph_cycle_power_dyadic_cover_tight_long_edgesIn an m+1-layer equivalence cover at dyadic bandwidth, every endpoint-distance edge and every other positively weighted dyadic long edge…
- simple_graph_cycle_power_dyadic_class_model_ordinary_coverFor every distance 1 ≤ d < 2^m and every integer vertex v there is a rooted offset a < 2^m - d whose class is active at both v-a and v-a+d.
- simple_graph_has_equivalence_cover_cycle_power_three_of_mod_four_eq_twoFor every n ≥ 10 with n ≡ 2 (mod 4), the cube C_n^3 of the n-cycle is covered by 4 equivalence subgraphs: on 0..n−1, layer 0 has the…
- simple_graph_cycle_power_three_cover_three_tight_dvdIf three labellings with clique classes satisfy the tight structure (each distance-3 pair and each distance-2 pair in exactly one layer,…
- simple_graph_cycle_power_dyadic_class_model_tight_weightsEvery rooted dyadic class of an optimal cover is tight: the dyadic class weight of the arc equals its cardinality.
- simple_graph_equivalence_covering_number_cycle_power_dvdFor k ≥ 1 and q ≥ 2, the k-th power of the cycle on q(k + 1) vertices has equivalence covering number exactly 1 + ⌈log₂(k + 1)⌉.
- simple_graph_cycle_power_seven_cover_four_layer_weight_eqIn any cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs, every layer has weight exactly n: the sum over i of 2·[i ~ i+7] + [i ~ i+6] +…
- cycle_power_floor_map_inducedFor natural n,N,k,K with n positive, N at least n, k*N at most K*n, and (K+1)*n at most (k+1)*N, the balanced floor map from ZMod n to…
- simple_graph_cycle_power_dyadic_class_model_disjoint_coloursTwo active rooted classes at a common vertex with distinct offsets have distinct layer colours.
- simple_graph_cycle_power_adj_iff_of_bandwidth_ltWhen k<n, two vertices of the k-th cycle power are adjacent exactly when their difference has a nonzero signed integer representative of…
- simple_graph_equivalence_covering_number_cycle_power_two_pow_even_not_dvd_of_alternating_pairedConditional resolution of OP-205: if, for every m ≥ 5, every tight, exactly dyadically covered, fully ordinarily covered integer Boolean…
- simple_graph_cycle_power_three_adj_iffFor n ≥ 10, u and v are adjacent in C_n^3 iff v = u + e for an integer e with 0 < |e| ≤ 3.
Lean source view module on GitHub
/-- The `k`-th power `C_n^k` of the `n`-cycle on `ZMod n`: distinct `u, v` are adjacent iff their cyclic distance `min ((u - v).val) ((v - u).val)` is at most `k`. -/ def simple_graph_cycle_power (n k : ℕ) : SimpleGraph (ZMod n) where Adj u v := u ≠ v ∧ min (u - v).val (v - u).val ≤ k symm := ⟨fun (u v : ZMod n) (h : u ≠ v ∧ min (u - v).val (v - u).val ≤ k) => ⟨h.1.symm, by rw [min_comm]; exact h.2⟩⟩ loopless := ⟨fun (u : ZMod n) (h : u ≠ u ∧ min (u - u).val (u - u).val ≤ k) => h.1 rfl⟩