simple_graph_has_equivalence_cover
def
G can be covered by t equivalence subgraphs: there are t spanning subgraphs of G, each a disjoint union of cliques (isolated vertices allowed), whose edge sets together cover E(G). Each one is given by a labelling c_s of the vertices whose classes are cliques of G; its edges are the pairs with equal labels.
Statement
def simple_graph_has_equivalence_cover {V : Type*} (G : SimpleGraph V) (t : ℕ) : Prop
- Defined in
- arXiv:2610.15635 (Covering powers of cycles with equivalence subgraphs), Sec. 1 (equivalence subgraphs; the labelling c_s of components is the one used in the proofs of Lemma 2.2 and Theorem 3.4).
- Verified
- 17 Oct 2026
- Axioms
- none listed
- Used by 19
- 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_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_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_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_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_has_equivalence_cover_pullbackLet G and H be simple graphs on arbitrary types V and W, t a natural number, and f an injective map from V to W such that G adjacency is…
- simple_graph_has_equivalence_cover_monoIf G is covered by s equivalence subgraphs, it is covered by any larger number t of them (pad with the edgeless equivalence subgraph).
- 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_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…
- 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_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_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_equivalence_covering_numberThe equivalence covering number eq(G): the minimum number of equivalence subgraphs of G whose edge sets cover E(G).
- 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)⌉.
Lean source view module on GitHub
/-- `G` is covered by `t` equivalence subgraphs. Subgraph `s` is the partition of `V` into the classes of the labelling `c s`; each class must be a clique of `G` (so the subgraph is a disjoint union of cliques of `G`), and every edge of `G` must join two vertices with the same label in some `c s`. Labels in `V` lose nothing: a partition of `V` has at most `|V|` classes. -/ def simple_graph_has_equivalence_cover {V : Type*} (G : SimpleGraph V) (t : ℕ) : Prop := ∃ c : Fin t → V → V, (∀ s u v, u ≠ v → c s u = c s v → G.Adj u v) ∧ ∀ u v, G.Adj u v → ∃ s, c s u = c s v