The cost of symmetry for tailed stars
Pith reviewed 2026-05-18 10:32 UTC · model grok-4.3
The pith
For infinitely many tailed-star graphs K, every automorphism-invariant K-hitting set in some connected Γ exceeds |V(K)| times the minimum hitting-set size.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
There exists an infinite set of connected graphs K such that, for each such K, there exist connected graphs Γ possessing a K-hitting set of size n for which every automorphism-invariant K-hitting set has size strictly larger than |V(K)|·n.
What carries the argument
The explicit infinite family of tailed-star graphs K together with the auxiliary graphs Γ that separate minimal hitting sets from their invariant counterparts.
If this is right
- The known multiplicative bound on invariant hitting-set size is not tight for the constructed tailed stars.
- Symmetry constraints can force strictly super-linear growth in the number of vertices that must be deleted to destroy all copies of K.
- The separation between ordinary and invariant hitting numbers is witnessed by infinitely many distinct connected graphs K.
Where Pith is reading between the lines
- Similar strict separations may exist for other natural families of forbidden subgraphs beyond tailed stars.
- Algorithms that search for minimal invariant hitting sets would have to accept a multiplicative overhead that depends on the shape of K rather than a uniform |V(K)| factor.
- The construction may be adaptable to directed graphs or hypergraphs, producing analogous symmetry costs in those settings.
Load-bearing premise
For each constructed K there exists at least one connected graph Γ whose smallest K-hitting set cannot be made automorphism-invariant without strictly increasing its size beyond |V(K)| times the minimum.
What would settle it
A single explicit K from the claimed infinite family together with a concrete connected Γ in which an automorphism-invariant K-hitting set of size exactly |V(K)|·n exists.
read the original abstract
It is known that if $n$ vertices can be removed from a connected graph $\Gamma$ so that no subgraphs isomorphic to the graph $K$ remain, then no more than $|V(K)|\cdot n$ vertices can be removed, forming a set invariant with respect to all automorphisms of the graph $\Gamma$, so that no subgraphs isomorphic to the graph $K$ remain. We construct an infinite set of (connected) graphs $K$ for which this estimate is not exact.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript constructs an infinite family of connected tailed-star graphs K together with, for each such K, a connected host graph Γ that admits a K-hitting set of size n while every Aut(Γ)-invariant K-hitting set has size strictly larger than |V(K)|·n. This shows that the general bound of |V(K)|·n for the size of an automorphism-invariant K-hitting set is not always tight.
Significance. The explicit infinite construction supplies concrete counter-examples to tightness of the known estimate in the special case of tailed stars. If the orbit analysis and hitting-set enumeration hold, the result isolates a setting in which symmetry imposes a strictly larger cost than the naive multiple of the minimum hitting-set size.
major comments (1)
- [§3] §3, construction of Γ and the orbit argument: the claim that no Aut(Γ)-invariant set of cardinality |V(K)|·n can hit all copies of K rests on the assertion that every minimum hitting set intersects the orbits in a non-invariant way; an explicit listing of the orbits of the minimum hitting sets under Aut(Γ) (or a proof that no union of orbits yields an invariant set of the target size) is needed to make this load-bearing step fully verifiable.
minor comments (2)
- [§2] The notation for the tailed-star family (e.g., the precise attachment points of the tails) should be fixed in a single definition early in the paper rather than re-introduced in each construction.
- [§4] A small table summarizing, for the first few members of the family, the values of |V(K)|, n, and the size of the smallest invariant hitting set would improve readability.
Simulated Author's Rebuttal
We thank the referee for the thorough review and for identifying a point where the orbit argument can be made more explicit. The construction demonstrates that the |V(K)|·n bound is not tight for an infinite family of tailed-star graphs K, and we will strengthen the verifiability of the key step without altering the main results.
read point-by-point responses
-
Referee: [§3] §3, construction of Γ and the orbit argument: the claim that no Aut(Γ)-invariant set of cardinality |V(K)|·n can hit all copies of K rests on the assertion that every minimum hitting set intersects the orbits in a non-invariant way; an explicit listing of the orbits of the minimum hitting sets under Aut(Γ) (or a proof that no union of orbits yields an invariant set of the target size) is needed to make this load-bearing step fully verifiable.
Authors: We agree that an explicit enumeration of the orbits would improve readability and verifiability. In the revised manuscript we will add a dedicated paragraph in §3 that lists the orbits of V(Γ) under Aut(Γ): the orbit of the attachment vertex of each tail, the orbits of the star-center vertices, and the orbits of the pendant leaves. We will then prove, by exhaustive case analysis on how a minimum hitting set can intersect these orbits, that any selection of exactly |V(K)|·n vertices that hits every copy of K must choose vertices from distinct orbits in a non-symmetric fashion. Consequently, the smallest Aut(Γ)-invariant hitting set is obtained only by taking the union of full orbits and necessarily has cardinality strictly larger than |V(K)|·n. This addition supplies the requested explicit listing and proof while leaving the combinatorial construction and the infinite family unchanged. revision: yes
Circularity Check
Explicit construction of counterexamples; no circularity
full rationale
The paper states a known bound on automorphism-invariant K-hitting sets and then constructs an explicit infinite family of connected tailed-star graphs K together with host graphs Γ to exhibit cases where the bound is not tight. This is a direct, self-contained mathematical construction of specific graphs and verification of their hitting-set properties. No step reduces by definition, by fitting, or by load-bearing self-citation to the claim itself; the result is independent of the prior bound and externally falsifiable by inspecting the constructed objects.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption If n vertices can be removed from a connected graph Γ so that no subgraphs isomorphic to K remain, then an automorphism-invariant set of size at most |V(K)|*n exists that achieves the same.
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We construct an infinite set of (connected) graphs K for which this estimate is not exact.
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Υ_sym^v(K,Γ) = |V(K)| · Υ_v(K,Γ)
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.