Invariant systems of representatives, or The cost of symmetry

Anton A. Klyachko; Natalia M. Luneva

REVIEW 3 major objections 3 minor 4 references

Invariant systems of representatives, or The cost of symmetry

T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that any finite system of representatives for a group-invariant family of bounded-size sets can be replaced by an invariant one of at most m times the size, where m is the largest member size.

desk verdict A genuinely clean main theorem with a linear bound; the sharpness sections are mostly convincing but need formalization. read the letter →

arxiv 1908.03315 v3 pith:IS22YZDI submitted 2019-08-09 math.CO math.GR

Anton A. Klyachko , Natalia M. Luneva This is my paper · ORCID

classification math.COmath.GR MSC 05D1505C3505C25

keywords costofsymmetryinvariantsystemsrepresentativesautomorphism-invarianthittingsetsforbiddensubgraphsvertexrepresentativenessedgevertex-transitivegraphscosetcovering

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves a general bound on what it calls the cost of symmetry. If a group acts on a set, and a family of finite subsets of bounded size is invariant under the action, then any finite hitting set for the family can be replaced by a group-invariant hitting set no more than $m$ times as large, where $m$ is the maximum size of a set in the family. For graphs this means that destroying every copy of a forbidden finite graph by deleting vertices or edges can be done symmetrically at a cost of at most $|V(K)|$ or $|E(K)|$ times the original cost. The paper also identifies exactly when this factor is unavoidable for vertex deletion: the forbidden graph must be connected. The proof is short and rests on a classical coset-covering fact, and the paper leaves several natural sharpness questions open, especially for the edge version.

What carries the argument

The load-bearing object is the orbit-hitting filter $Y=\{y\in U: |Gy\cap X|\ge |Gy|/m\}$, which converts an arbitrary finite representative system $X$ into a $G$-invariant one by keeping exactly the points whose orbit $Gy$ is well hit by $X$, meaning at least one $m$-th of the orbit lies in $X$. Its size bound follows from summing $|Y\cap Gy|\le m|X\cap Gy|$ over orbits. The second ingredient is the coset-covering theorem for groups: when $G$ is covered by finitely many cosets of subgroups, the sum of the reciprocal indices is at least $1$. Applied to the cosets $\{g\in G: gf\in X\}$ for $f\in F$, this forces one point of every $F\in\mathcal F$ to survive in $Y$.

What would settle it

For the main theorem, a counterexample would be an explicit group action on a set $U$ and an invariant family $\mathcal F$ of sets of size at most $m$, together with a finite hitting set $X$, for which every invariant hitting set has size greater than $m|X|$; the paper's proof rules this out by computing $Y=\{y\in U: |Gy\cap X|\ge |Gy|/m\}$ and showing $Y$ is an invariant hitting set, so the falsifier is any explicit instance where $Y$ misses some $F\in\mathcal F$.

Watch

Extended reading notes

Core claim

The main theorem states that for a group $G$ acting on a set $U$ and a $G$-invariant family $\mathcal F$ of finite subsets of $U$ with $m=\max_{F\in\mathcal F}|F|<\infty$, every finite system of representatives $X$ for $\mathcal F$ is dominated by a $G$-invariant system of representatives $Y$ with $|Y|\le m|X|$. The construction is $Y=\{y\in U: |Gy\cap X|\ge |Gy|/m\}$, i.e. the points whose orbit is hit by $X$ at least a fraction $1/m$ of the time; this set is $G$-invariant and the orbit-by-orbit count gives $|Y|\le m|X|$. The proof that $Y$ still intersects every $F\in\mathcal F$ proceeds by covering $G$ with finitely many cosets of the stabilizers of the points of $F$; since each $gF$ meets $X$, the coset-covering theorem implies that some $f\in F$ has $|Gf\cap X|/|Gf|\ge 1/m$, so $f\in Y$. In graph language this yields Corollary 1: destroying all copies of a finite forbidden graph $K$ by deleting vertices symmetrically costs at most $|V(K)|$ times the minimum unsymmetric cost, and deleting edges symmetrically costs at most $|E(K)|$ times the minimum unsymmetric cost, in any of the six standard graph conventions.

Load-bearing premise

The proof that exactly the connected graphs are vertex-costly assumes, as an unproved exercise, that every finite graph in each of the six graph conventions embeds into a vertex-transitive graph with the same number of vertices, on which the main theorem's bound does not depend but the sharpness classification does.

Editorial extensions

If this is right

For any finite forbidden graph $K$, a graph that can be freed of all copies of $K$ by removing finitely many vertices has an automorphism-invariant set of at most $|V(K)|$ times as many vertices doing the same; the edge analogue holds with $|E(K)|$.
The vertex factor is sharp exactly for connected $K$: every connected graph $K$ is vertex-costly, meaning there are arbitrarily large host graphs where the symmetric cost equals the unsymmetric cost multiplied by $|V(K)|$.
Connected graphs without hanging edges are vertex-costly even when the host graph is required to be connected, and so are chains; the five-vertex graph $D_5$ shown in the paper is not costly among vertex-transitive connected hosts.
The fairness reading of the theorem is quantitative: for the Mars-expedition problem with five-person compatibility constraints and ten expulsions, symmetry costs at most 50 expulsions, and this bound is achieved in the worst case.
For edge-costliness the situation is less complete: every finite edge-transitive connected graph is edge-costly, some disconnected graphs are edge-costly even among connected hosts, and whether any undirected simple graph fails to be edge-costly is left open.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The orbit-density proof suggests a constructive algorithm for the invariant representative: compute orbit-hit fractions $|Gy\cap X|/|Gy|$ and retain the points above the $1/m$ threshold; the paper does not discuss algorithmic cost, but the bound is uniform for any group action.
The same method may extend to weighted costs over orbits, since the proof only uses that $|Y\cap Gy|$ is bounded by $m|X\cap Gy|$ per orbit; such an extension is not claimed in the paper.
A computational search over small undirected simple graphs $K$ and finite host graphs $\Gamma$ would directly probe the edge-costliness question: finding any $K$ with $\Upsilon_{\rm e}^{\rm sym}(K,\Gamma)$ arbitrarily larger than $|E(K)|\Upsilon_{\rm e}(K,\Gamma)$ would confirm the edge-costly conjecture, while a universal smaller bound would refute it.
The planar-graph boundary example shows that the main theorem's hypothesis of bounded member size is essential; a weighted or unbounded analogue of the factor-$m$ bound cannot hold in general.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The real result here is the main theorem: if a group G acts on a set U and F is a G-invariant family of finite subsets of size at most m, then any finite hitting set X can be replaced by a G-invariant hitting set Y with |Y| ≤ m|X|. The proof is short, elementary, and correct—define Y by orbit-densities and apply B. H. Neumann's coset-covering theorem. This is a genuine improvement over the multilinear-property theorem's astronomical bound, and it is the kind of clean statement that will get cited.

The paper also does a good job on sharpness for vertex representativeness. The characterization that a finite graph K is vertex-costly iff it is connected is plausible and the main idea—embed K into a vertex-transitive graph on the same vertex set, then take disjoint union of m copies—works. The authors leave that embedding claim as an exercise. I checked the obvious constructions: in each of the six graph conventions, the complete object (complete graph, complete digraph with loops where allowed, etc.) is vertex-transitive and contains K, so the claim is true. Still, it should be stated with a proof; the current wording is too casual. The argument that disconnected graphs are not costly is neat.

The soft spots are in the sharpness sections. Several constructions (Figures 2 and 6, the honeycomb, the torus doubling) are figure-based and rely on "obvious modifications." A rigorous referee would want these formalized. The proof of Theorem 2 is a case analysis that is sketched rather than fully detailed. These issues do not touch the main theorem, and they are fixable, but they are real gaps in presentation.

Citation pattern looks appropriate. The paper positions itself against the known Khukhro–Makarenko type results and correctly identifies the previous bound as uselessly large. Self-citation is not a problem here because the cited results are directly relevant.

Who is this for? Combinatorialists and group theorists who care about symmetry-invariant versions of hitting problems. The main theorem is a useful tool and deserves to be in the literature. I would send this to peer review, but I would ask the authors to prove the embedding claim and either formalize or clearly reduce the diagrammatic constructions. A conditional accept is the right call, with the main theorem already solid.

Referee Report

3 major / 3 minor

Summary. The paper studies the following kind of problem for group actions and graphs: given a family of finite objects, if some finite set of representatives (or vertices/edges hitting all forbidden subgraphs) exists, how much larger must an automorphism-invariant set of representatives be? The main theorem states that, for a group G acting on a set U and a G-invariant family F of finite subsets of U of maximum size m, every finite system of representatives X can be dominated by a G-invariant system of representatives Y with |Y| ≤ m|X|. The proof in Section 3 defines Y as the union of orbits whose intersection with X has size at least 1/m of the orbit size, estimates |Y| by m|X|, and uses B. H. Neumann's coset-covering theorem to show Y meets every F in F. This yields Corollary 1 for graph vertex- and edge-transversals. Sections 1 and 2 discuss sharpness, introducing costly graphs, proving a characterization of vertex-costly connected graphs, proving that edge-transitive connected graphs are edge-costly, and listing several open questions.

Significance. The main theorem is a clean, parameter-free linear estimate that substantially improves the previously known gigantic bounds of the Khukhro–Makarenko type in a combinatorial setting. The proof is elementary, short, and fully self-contained apart from the standard Neumann covering theorem, and it has no fitted constants. The orbit-fraction construction is elegant and the derivation of |Y| ≤ m|X| plus the covering argument are correct. The paper also gives a nice dictionary between algebraic characteristic-subgroup results and combinatorial automorphism-invariant transversals, and it identifies interesting open questions. However, several of the sharpness claims, especially the costly-graph classification of Theorem 1, rest on unproved embedding assertions and diagrammatic constructions; these do not affect the central theorem but must be repaired before the sharpness results can be regarded as fully established.

major comments (3)

[Section 1, proof of Theorem 1] The proof relies on the statement that every finite graph K, in each of the six graph conventions, embeds into a vertex-transitive graph on the same vertex set. This is asserted and explicitly left as an exercise, with a proof given only for the undirected multi-edge-free loop-free case (the complete graph). The assertion is needed to construct Gamma_m from disjoint copies of a vertex-transitive supergraph, and it is not obvious for conventions allowing loops or multiple edges or for directed/mixed graphs. If it fails in one of the conventions, the classification of costly graphs would need to be adjusted. Please provide a proof, a reference, or a precise construction covering all six conventions, or state the theorem with the conventions for which the assertion is known to hold.
[Section 1, Figures 1 and 2] The sharpness of vertex-costliness for connected graphs with hanging edges is established by Figure 2, which shows an infinite doubly periodic pattern on the plane, and then the finite graphs Gamma_m are obtained by drawing the pattern on a torus. The manuscript itself notes that 'strictly speaking, Figure 2 proves this assertion only if the word graph means an undirected graph without loops and multiple edges' and that 'obvious modifications' handle the other cases. This is a load-bearing gap for Theorem 1's 'moreover' part and for the claim that all connected graphs with at most four vertices are costly in the class of connected graphs. A formal verification is needed that the finite torus quotients exist for arbitrarily large m and that every subgraph isomorphic to K in those tori contains a marked vertex, for each relevant graph convention.
[Section 2, Proposition 1 (honeycomb construction)] The proof that a star K = K_{1,3} is edge-costly uses an infinite 'honeycomb' graph with one third of the edges marked and then asserts that finiteness is obtained by drawing this doubly periodic pattern on a torus. This construction is plausible but not formalized; the claim that the torus quotient here is edge-transitive and that exactly one third of its edges are marked requires care, especially for the boundary conditions of the quotient. Please provide a precise description of the finite graphs Gamma_m and a proof of the equality Υ_sym^e(K, Gamma_m) = m·|E(K)| = 3m.

minor comments (3)

[Section 1, proof of Theorem 1, disconnected case] In the inequality for disconnected K, the notation assumes K = K1 ⊔ K2 with k2 ≤ k1, but the components K1 and K2 are chosen arbitrarily; it would be clearer to state 'where K1 is a component of largest order and K2 is any other component, so that k2 ≤ k1'.
[Section 2, Proposition 1, directed star case] In the directed star case, the proof says 'Assuming that there is one source, take the complete bipartite graph K_{m,l} in which all edges are directed from the first part to the second part' and asserts Υ_sym^e = ml; it would be helpful to spell out why this graph is edge-transitive as a directed graph and why every copy of K contains exactly one marked edge.
[General presentation] There are a number of typographical and OCR artifacts in the text, such as 'graph have' instead of 'graph has' and the rendering 'greaterorequalslant' in displayed inequalities; a careful copyedit would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main theorem is proved from first principles using B. H. Neumann's coset-covering theorem, with no fitted parameters and no load-bearing self-citations; the unproved graph-embedding exercise in Theorem 1 is a non-circular gap.

full rationale

The central derivation in Section 3 is self-contained: the invariant system Y is defined directly from an arbitrary finite system of representatives X by the orbit-fraction condition |Gy ∩ X| ≥ |Gy|/m, and the proof that Y meets every F ∈ F uses only the G-invariance of F, the decomposition of G into cosets of stabilizers, and B. H. Neumann's covering theorem. There is no fitted constant, no normalization chosen to force the conclusion, and no dependence on any theorem proved or claimed by the authors themselves; the cited prior Khukhro–Makarenko results appear only as motivating context and are not used in the proof of the main theorem or Corollary 1. The paper's own text flags two genuine limitations that are nevertheless not circular: the assertion that every finite graph embeds into a vertex-transitive graph with the same number of vertices is stated and explicitly left as an exercise ('in other cases, this fact remains valid (we leave it to readers as an exercise, see graphs K and ~K in Figure 1)'), and the sharpness construction for four-vertex graphs is admitted to be figure-based ('Strictly speaking, Figure 2 proves this assertion only if the word graph means an undirected graph without loops and multiple edges'). These are gaps in supporting sharpness claims, not instances of a prediction reducing to its input by construction. No circular step can be exhibited with a specific equation or definitional equivalence, so the appropriate finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

No numbers are fitted to data, no free parameters appear, and no new postulated entities are introduced. The central theorem depends only on standard group-action facts and the external Neumann covering theorem; the sharpness theorem additionally depends on the unproved vertex-transitive embedding claim.

assumptions (2)

standard math B. H. Neumann's coset-covering theorem: if a group is covered by finitely many cosets of subgroups, then the sum of the reciprocals of the indices is at least 1.
Section 3: after writing G as the union over f in F of cosets of St(f), the proof invokes [Neu54] to conclude that the sum of |Gf intersect X| / |Gf| is at least 1. This is an external theorem with a standard proof, not derived in the paper.
domain assumption Every finite graph K embeds into a vertex-transitive graph on the same vertex set, in each of the six graph conventions used.
Used in the proof of Theorem 1 to build vertex-transitive Gamma_m from copies of such a supergraph. The authors call it an exercise and give no proof; it is clear for simple undirected graphs (the complete graph) but not for all conventions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Invariant systems of representatives, or The cost of symmetry." pith.science (2026). https://pith.science/paper/IS22YZDI

@misc{pith2026190803315,
  author       = {Pith},
  title        = {Pith review of: Invariant systems of representatives, or The cost of symmetry},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IS22YZDI}},
  note         = {Machine review of arXiv:1908.03315}
}

read the original 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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

[1]

Bruno, F

[BrNa04] B. Bruno, F. Napolitani, A note on nilpotent-by- ˇCernikov groups, Glasgow Math. J., 46 (2004), 211-215. [ChD89] A. Chermak, A. Delgado, A measuring argument for ﬁnite gr oup. Proc. Amer. Math. Soc., 107 (1989), 907-914. [dGT18a] F. de Giovanni, M. Trombetti, A note on large characterist ic subgroups. Communications in Algebra, 46:11 (2018), 4654...

work page 2004
[40]

[KhKMM09] E. I. Khukhro, Ant. A. Klyachko, N. Yu. Makarenko, an d Yu. B. Melnikova Automorphism invariance and identities. Bull. London Math. Soc. (2009), 41(5): 804-816. S ee also arXiv:0812.1359 . [KlMe09] A. A. Klyachko, Yu. B. Mel’nikova, A short proof of the Khuk hro–Makarenko theorem on large charac- teristic subgroups with laws, Sbornik: Mathematic...

work page Pith review arXiv 2009
[68]

Khukhro-Makarenko type theorems for algebras

[dGT19b] F. de Giovanni, M. Trombetti, Large characteristic subgr oups and abstract group classes, Quaestiones Mathematicae (to appear). [Fr18] E. Frolova, Khukhro-Makarenko type theorems for algebr as, arXiv:1804.00268. [Is08] I. M. Isaacs, Finite group theory, GSM 92, American Math. S oc., Providence RI,

work page Pith review arXiv
[1979]

[KhM07a] E. I. Khukhro, N. Yu. Makarenko, Large characteristic subgroups satisfying multilinear commutator identities, J. London Math. Soc., 75:3 (2007), 635-646. [KhM07b] E. I. Khukhro, N. Yu. Makarenko, Characteristic nilpote nt subgroups of bounded co-rank and automorphically-invariant ideals of bounded codimension in Lie algebra s, Quart. J. Math., 58...

work page 2007

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Bruno, F

[BrNa04] B. Bruno, F. Napolitani, A note on nilpotent-by- ˇCernikov groups, Glasgow Math. J., 46 (2004), 211-215. [ChD89] A. Chermak, A. Delgado, A measuring argument for ﬁnite gr oup. Proc. Amer. Math. Soc., 107 (1989), 907-914. [dGT18a] F. de Giovanni, M. Trombetti, A note on large characterist ic subgroups. Communications in Algebra, 46:11 (2018), 4654...

work page 2004

[2] [40]

[KhKMM09] E. I. Khukhro, Ant. A. Klyachko, N. Yu. Makarenko, an d Yu. B. Melnikova Automorphism invariance and identities. Bull. London Math. Soc. (2009), 41(5): 804-816. S ee also arXiv:0812.1359 . [KlMe09] A. A. Klyachko, Yu. B. Mel’nikova, A short proof of the Khuk hro–Makarenko theorem on large charac- teristic subgroups with laws, Sbornik: Mathematic...

work page Pith review arXiv 2009

[3] [68]

Khukhro-Makarenko type theorems for algebras

[dGT19b] F. de Giovanni, M. Trombetti, Large characteristic subgr oups and abstract group classes, Quaestiones Mathematicae (to appear). [Fr18] E. Frolova, Khukhro-Makarenko type theorems for algebr as, arXiv:1804.00268. [Is08] I. M. Isaacs, Finite group theory, GSM 92, American Math. S oc., Providence RI,

work page Pith review arXiv

[4] [1979]

[KhM07a] E. I. Khukhro, N. Yu. Makarenko, Large characteristic subgroups satisfying multilinear commutator identities, J. London Math. Soc., 75:3 (2007), 635-646. [KhM07b] E. I. Khukhro, N. Yu. Makarenko, Characteristic nilpote nt subgroups of bounded co-rank and automorphically-invariant ideals of bounded codimension in Lie algebra s, Quart. J. Math., 58...

work page 2007