simple_graph_equivalence_covering_number
def
The equivalence covering number eq(G): the minimum number of equivalence subgraphs of G whose edge sets cover E(G).
Statement
noncomputable def simple_graph_equivalence_covering_number {V : Type*} (G : SimpleGraph V) : ℕ
- Defined in
- arXiv:2610.15635 (Covering powers of cycles with equivalence subgraphs), Sec. 1 (definition of eq(G)).
- Verified
- 17 Oct 2026
- Axioms
- none listed
- Built on 1
- simple_graph_has_equivalence_coverG can be covered by t equivalence subgraphs: there are t spanning subgraphs of G, each a disjoint union of cliques (isolated vertices…
- Used by 14
- simple_graph_equivalence_covering_number_topSanity check: a complete graph with at least two vertices has equivalence covering number 1.
- 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_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_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_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_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_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_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_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_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_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…
Lean source view module on GitHub
/-- The equivalence covering number `eq(G)`: the least `t` such that `G` is covered by `t` equivalence subgraphs (0 if there is none, which cannot happen for a finite graph). -/ noncomputable def simple_graph_equivalence_covering_number {V : Type*} (G : SimpleGraph V) : ℕ := sInf {t | simple_graph_has_equivalence_cover G t}