Invariant systems of representatives, or the cost of symmetry

DOI10.1016/J.DISC.2021.112361zbMATH Open1476.05070arXiv1908.03315OpenAlexW2969065491MaRDI QIDQ2022146FDOQ2022146

Natalia M. Luneva, Anton A. Klyachko

Publication date: 28 April 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Suppose that one can destroy all 100-gons in a graph by removing 2019 edges. How many edges must be removed to destroy all 100-gons in such a way that the set of removed edges is invariant with respect to all automorphisms the initial graph? This paper contains solutions to such kind of problems. Several open questions are raised.

Full work available at URL: https://arxiv.org/abs/1908.03315

zbMATH Keywords

automorphisms of graphsinvariant systems of representatives

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Groups Covered By Permutable Subsets
• Large normal nilpotent subgroups of finite groups
• Large characteristic subgroups satisfying multilinear commutator identities
• A short proof of the Khukhro-Makarenko theorem on large characteristic subgroups with laws
• Automorphism invariance and identities
• Characteristic subgroups in locally finite groups.
• A NOTE ON NILPOTENT-BY-ERNIKOV GROUPS
• A Measuring Argument for Finite Groups
• Bounds in groups with finite abelian coverings or with finite derived groups
• CHARACTERISTIC NILPOTENT SUBGROUPS OF BOUNDED CO-RANK AND AUTOMORPHICALLY INVARIANT NILPOTENT IDEALS OF BOUNDED CODIMENSION IN LIE ALGEBRAS
• Automorphically-invariant ideals satisfying multilinear identities, and group-theoretic applications
• Large characteristic subgroups and abstract group classes
• Large characteristic subgroups with modular subgroup lattice
• A Note on Large Characteristic Subgroups
• Large characteristic subgroups in which normality is a transitive relation
• Large and symmetric: the Khukhro-Makarenko theorem on laws -- without laws.

Cited In (2)

• Achievable sets in \(\mathbb Z^n\).
• The cost of symmetry in connected graphs

This page was built for publication: Invariant systems of representatives, or the cost of symmetry

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2022146)