{"id":"4b06fe50-60c9-479d-9568-f70545d5ffae","arxiv_id":"1908.03315","paper_version":3,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Under any group action, a finite system of representatives of size r for a bounded family of sets can be replaced by an invariant system of representatives of size at most r times the maximum set size.","lead":"This paper proves a general symmetry-preserving version of the hitting-set problem: if finite sets can be used to meet every member of a family, then a symmetry-invariant meeting set exists whose size is at most a fixed factor larger. For graphs, this gives bounds on how many vertices or edges must be removed to destroy all copies of a forbidden subgraph while respecting all automorphisms.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No load-bearing objection to the main theorem; the unproved embedding claim in Theorem 1 is a real but non-central gap.","rationale":"The main theorem is elementary and the proof is internally sound. The definition of Y uses orbit intersections with the finite set X; each orbit is either entirely in Y or entirely out, and the bound |O| ≤ m|O∩X| for included orbits is immediate. The coset-covering step is valid because F is finite (|F| ≤ m) and each {g : gf ∈ X} is a finite union of cosets of St(f); Neumann's theorem applies even with infinite-index subgroups, and the reciprocal-sum inequality is used correctly. No hidden circularity or parameter-fitting is present. The reader's conditional verdict is based on the explicitly unproved embedding claim in Theorem 1 and on figure-based constructions; I concur that these are the weakest parts of the paper. They are not load-bearing for the main theorem, but they do support the sharpness classification, so the paper is not fully verified as written. The appropriate disposition is to keep the reader's conditional verdict.","tokens_in":13182,"tokens_out":25439,"duration_ms":282165,"concrete_test":"Write out the missing embedding exercise: for each of the six graph conventions, construct an explicit vertex-transitive graph ~K on the same vertex set as K that contains K as a spanning subgraph (e.g., complete digraph, complete graph with loops, complete multigraph with maximum multiplicity). If such a construction exists in every convention, Theorem 1's proof is complete; if not, the costly-graph classification must be revised.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theorem (Section 3) is correct: Y = {y : |Gy ∩ X| ≥ |Gy|/m} is a union of orbits, and the orbit-wise estimate |O∩Y| ≤ |O| ≤ m|O∩X| gives |Y| ≤ m|X|. For any F ∈ F, the sets {g : gf ∈ X} are finite unions of cosets of St(f), and since gF ∈ F, these cosets cover G. B. H. Neumann's theorem yields ∑_{f∈F} |Gf∩X|/|Gf| ≥ 1, so with |F| ≤ m some term is at least 1/m, giving f ∈ Y. The only genuine soft spot is in the proof of Theorem 1: the assertion that every finite graph embeds into a vertex-transitive graph on the same vertex set is stated and explicitly left as an exercise, and small-graph sharpness constructions (Figures 1, 2, 6) are figure-based rather than fully formalized. This affects the costly-graph classification and sharpness claims, but not the main theorem or Corollary 1. I find no error in the central argument; the gap is a missing proof in a supporting result, so a conditional verdict is appropriate.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":114,"tokens_out":2887,"duration_ms":158775,"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":[{"comment":"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":"Section 1, proof of Theorem 1"},{"comment":"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":"Section 1, Figures 1 and 2"},{"comment":"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.","section":"Section 2, Proposition 1 (honeycomb construction)"}],"minor_comments":[{"comment":"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":"Section 1, proof of Theorem 1, disconnected case"},{"comment":"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.","section":"Section 2, Proposition 1, directed star case"},{"comment":"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.","section":"General presentation"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nCitation 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.\n\nWho 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.","headline":"A genuinely clean main theorem with a linear bound; the sharpness sections are mostly convincing but need formalization.","tokens_in":13917,"tokens_out":3365,"would_cite":true,"duration_ms":39124,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D15","05C35","05C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["cost of symmetry","invariant systems of representatives","automorphism-invariant hitting sets","forbidden subgraphs","vertex representativeness","edge representativeness","vertex-transitive graphs","coset covering"],"falsifier":"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$.","tokens_in":13015,"feed_emoji":"⚖️","tokens_out":13695,"duration_ms":138771,"temperature":0.7,"pith_summary":"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.","feed_headline":"Making a choice symmetric costs at most a factor m","feed_subtitle":"When symmetry is required, any finite choice of representatives can be made invariant at no more than m times the cost.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the coset-covering theorem used in the proof to show that the invariant set $Y$ actually meets every member of the family.","marker":"[Neu54]"},{"why":"Provides the previous general theorem with the astronomically larger bound that the main theorem improves, and the planar boundary example where no bounded factor is possible.","marker":"[KlMi15]"},{"why":"Gives the original large-characteristic-subgroup theorem whose pattern of making a finite-index object invariant at bounded cost the paper generalizes to combinatorial systems of representatives.","marker":"[KhM07a]"}],"fun_headline_variants":["Symmetry costs at most a factor m","Making choices symmetric: at most m× cost","Invariant representatives: price tag ≤ m","Forced symmetry costs at most m times"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Symmetry costs at most a factor m","Making choices symmetric: at most m× cost","Invariant representatives: price tag ≤ m","Forced symmetry costs at most m times"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000328,"raw_usage":{"total_tokens":1811,"prompt_tokens":905,"completion_tokens":906,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":850}},"tokens_in":521,"tokens_out":906,"duration_ms":8979,"temperature":1.0,"reasoning_tokens":850,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:18:03.949458+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[],"review_version":1}