is_strongly_symmetric_instance
def
The problem max{f(S) : S independent in M} is strongly symmetric with respect to a permutation group G: f(σ(S)) = f(S) for all S and σ ∈ G, and two sets with equal symmetrized indicator vectors E_σ[1_{σ(S)}] are both independent or both dependent.
Statement
def is_strongly_symmetric_instance {m : ℕ} (M : Matroid (Fin m)) (f : Finset (Fin m) → ℝ) (G : Subgroup (Equiv.Perm (Fin m))) : Prop
- Defined in
- arXiv:2610.07387 (Stronger hardness for submodular maximization subject to a matroid constraint), Definition 2.1 (strong symmetry)
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 2
- perm_group_symmetrizeThe symmetrization x̄ = E_{σ∈G}[σ(x)] of a vector x over a group G of permutations of the coordinates, where σ(x)_{σ(u)} = x_u.
- finset_indicator_vecThe indicator vector 1_S ∈ ℝ^m of a set S ⊆ {0, …, m−1}.
- Used by 5
- is_strongly_symmetric_instance_botEvery matroid together with any set function is a strongly symmetric instance for the trivial permutation group: a witness that the…
- perm_group_symmetrize_mem_matroid_polytopeFor a strongly symmetric instance, symmetrizing a point of the matroid polytope stays inside the matroid polytope.
- matroid_symmetry_gap_le_oneFor every strongly symmetric instance max{f(S) : S independent in M} with respect to a permutation group G, the best symmetrized…
- symmetry_gap_numerator_eq_sSup_fixedFor a strongly symmetric instance the numerator of the symmetry gap, sup_{x∈P(M)} F(x̄), equals the supremum of F over the points of the…
- symmetrize_image_matroid_polytope_eq_fixedFor a strongly symmetric instance, the image of the matroid polytope under symmetrization is exactly the set of points of the polytope…
Lean source view module on GitHub
/-- The problem `max {f(S) : S independent in M}` is strongly symmetric with respect to the permutation group `G`: `f(σ(S)) = f(S)` for every `σ ∈ G`, and two sets with the same symmetrized indicator vector are both independent or both dependent. -/ def is_strongly_symmetric_instance {m : ℕ} (M : Matroid (Fin m)) (f : Finset (Fin m) → ℝ) (G : Subgroup (Equiv.Perm (Fin m))) : Prop := (∀ σ ∈ G, ∀ S : Finset (Fin m), f (S.map σ.toEmbedding) = f S) ∧ ∀ S S' : Finset (Fin m), perm_group_symmetrize G (finset_indicator_vec S) = perm_group_symmetrize G (finset_indicator_vec S') → (M.Indep ↑S ↔ M.Indep ↑S')