{"id":"0ab780b9-bdf9-4a3b-b560-b3aa6c80f079","arxiv_id":"2607.07939","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every connected graph embeds isometrically into an abelian Cayley host of order at least max(n, 2 diam), binary dimension at least max(diam, ceil(log2 n)), with exact values for stars and odd cycles and a census showing 57% of small graphs gain from non-binary hosts.","lead":"This paper proves lower bounds on the size of the smallest abelian Cayley graph that can host any given connected graph isometrically, and shows exact values for stars, cycles, and hypercubes. A full census of all 995 small graphs finds that most admit a strictly smaller non-binary abelian host than the best binary one, a phenomenon the authors call the abelian dividend.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the cyclic-interval lemma as the sole open technical piece and correctly notes that it is scoped only to unconditional k_min(C_m)=m-1 for all odd m. Theorems 1–3, the star sum-free argument, the attained lower-bound families, and the certified census (with explicit caveats that both sides are algorithmic upper bounds) stand independently. Because that open lemma is not load-bearing for the strongest claims, no verdict adjustment is warranted. The suggested concrete test simply reconfirms one of the paper’s sharpest empirical numbers using the promised data release.","tokens_in":12560,"tokens_out":415,"duration_ms":4619,"concrete_test":"Independently re-verify the 17 graphs claimed to attain the order floor max(n,2 diam) by extracting their certified host groups and generators from the released census records and re-running BFS distance checks against the graph metrics; if all 17 remain isometric and match the floor, the optimality count is solid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims (Theorems 1–3 lower bounds and equality characterization, exact dimensions for stars/hypercubes/even cycles, and the certified n≤7 census documenting the abelian dividend) rest on standard geodesic-independence, injectivity, vertex-transitivity diameter, and sum-free extremal arguments that are self-contained and correctly scoped. The cyclic-interval lemma is the only incomplete piece, but it is isolated to the odd-cycle exactness claim, proved for m≤17, and honestly labeled Conjecture 1; it is not required for the strongest claims the reader highlights. Census caveats (algorithmic upper bounds on both sides, restricted Hermite search) are already stated and do not reverse the direction of the dividend. No internal inconsistency or hidden assumption undermines the load-bearing results.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies the minimal binary dimension k_min(G) and the minimal abelian host order ν(G) for isometric embeddings of a finite connected graph G into Cayley graphs of finite abelian groups. It proves the lower bounds k_min(G) ≥ max(diam(G), ⌈log_{2} n⌉) and ν(G) ≥ max(n, 2 diam(G)), and the characterization that ν(G) = n if and only if G itself is an abelian Cayley graph (Theorems 1–3). Exact binary dimensions are obtained for hypercubes, complete graphs of order 2^t, even cycles (all attaining the lower bound), stars (k_min(K_{1,q}) = ⌈log_{2} q⌉ + 1 via maximal sum-free sets in ℤ_{2}^k), and odd cycles (k_min(C_m) = m-1 for odd m ≤ 17, reduced in general to a cyclic-interval lemma). An exhaustive certified census of all 995 connected graphs on 2 ≤ n ≤ 7 vertices documents an “abelian dividend”: 57% admit a certified abelian host strictly smaller than the best binary host found, and 71% admit an optimal host with a cyclic factor ℤ_m, m > 2.","tokens_in":12766,"tokens_out":1148,"duration_ms":9579,"significance":"The lower bounds and the equality characterization (Theorems 1–3) are clean, self-contained, and fill a natural gap left by the classical partial-cube and Hamming-embedding literature. The star result gives a sharp exponential gap even for trees, correctly reducing to the classical maximal sum-free size 2^{k-1}. The census is a genuine contribution: every reported abelian host is certified by exact BFS distance checks, the methodology and its limitations (algorithmic upper bounds on both sides, restricted Hermite search) are stated honestly, and the direction of the dividend is therefore robust. The work supplies concrete, reproducible data that non-binary abelian hosts are typical rather than exceptional on small graphs, while binary hosts remain the universal construction. These strengths make the paper a solid addition to metric graph theory and abelian Cayley embeddings.","major_comments":[{"comment":"Section 4 / Lemma 3 / Conjecture 1: the exact claim k_min(C_m) = m-1 for all odd m rests on the cyclic-interval lemma, which is proved only in the covering-arc regime and verified by exhaustive search for m ≤ 17. The manuscript already isolates this as Conjecture 1 and does not use it for Theorems 1–3 or the census; the limitation should be kept explicit in the abstract and introduction so that the unconditional results are not overstated.","section":null},{"comment":"Section 5.1: both sides of the dividend comparison are algorithmic upper bounds (binary pipeline vs. portfolio of certified abelian hosts). The paper correctly notes that every abelian win is a genuine isometric embedding, so the direction is robust, but the abstract and Figure 2 should state more prominently that the reported percentages are lower bounds on the true dividend rather than exact optima.","section":null}],"minor_comments":[{"comment":"Abstract vs. body: the abstract writes floor(log_{2} n) and 2^{diam(G)}; the body (Theorem 1, Theorem 2) correctly uses ⌈log_{2} n⌉ and 2 diam(G). Align the abstract with the theorems.","section":null},{"comment":"Table 1: the Petersen entry claims k_min = 4 attained; a one-line reference or sketch of the embedding (or a pointer to the companion) would help the reader.","section":null},{"comment":"Figure 1 caption and surrounding text: the window is written both as [max(diam, log_{2} n), n-1] and with ceilings; make the notation uniform with Theorem 1.","section":null},{"comment":"Section 2.2, Lemma 2: the appeal to 2-connectivity of vertex-transitive graphs of degree ≥ 2 is standard; a precise citation to Godsil–Royle (already in the bibliography) would be cleaner than the parenthetical sketch.","section":null},{"comment":"Data availability: the census records and runner scripts are said to be available from the authors; for a computational centerpiece of this kind, a public repository or permanent archive link would strengthen reproducibility.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is tightly coupled to the companion [35] for the constructive upper bound and the embedding pipeline. That dependence is disclosed and does not undermine the self-contained lower bounds or the census, but the editor may wish to ensure that [35] is available to readers (or that the present manuscript can stand alone for the claims it makes). Fit for a combinatorics journal is good; the signal-processing motivation is secondary and does not dilute the mathematical content."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The punchline is simple: they give the first general lower bounds on binary dimension and abelian host order for isometric embeddings, prove exact values for stars (via sum-free sets) and odd cycles up to 17, and ship a certified census of all 995 connected graphs on n≤7 that shows a majority get a strictly smaller non-binary abelian host.\n\nWhat is new is Theorems 1–3 (k_min ≥ max(diam, ⌈ log2 n⌉), \nu ≥ max(n, 2 diam), and \nu = n iff G is itself abelian Cayley), the star formula k_min(K1,q) = ⌈ log2 q⌉ + 1, the odd-cycle tightness, and the empirical “abelian dividend” numbers. The geodesic-independence lemma and the vertex-transitive diameter argument are short and standard; the star proof correctly reduces to the classical 2^{k-1} sum-free bound. The census is careful: every reported host is BFS-certified, the caveats (algorithmic upper bounds on both sides, restricted Hermite search on hard instances) are stated up front, and the direction of the dividend is therefore robust even if individual optima are not claimed.\n\nSoft spots are minor and proportional. The cyclic-interval lemma is proved only in the covering-arc regime and machine-checked for odd m≤17; the general claim is Conjecture 1 and is not needed for the strongest theorems. Petersen order is left open in [11,16], which is honest. Companion dependence for the universal construction is normal for a multi-paper program. Citation pattern is appropriate; self-cites are to the constructive pipeline and applications papers.\n\nThis is for people who work on isometric embeddings, partial cubes, or abelian Cayley hosts, and for anyone who wants a clean reference for the extremal window. Math and data look solid. I would send it to referees without hesitation; it is a useful, reproducible contribution that closes natural questions and documents a genuine phenomenon.","headline":"Clean lower bounds, exact star and cycle results, and a certified n≤7 census that documents a real abelian compression phenomenon; the only open piece is isolated and flagged.","tokens_in":13353,"tokens_out":530,"would_cite":true,"duration_ms":5603,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C12","05C25","05C30","11B75","20K01"],"pacs":[],"model":"grok-4.5","headline":"Most small graphs pack isometrically into strictly smaller non-binary abelian Cayley hosts than binary ones, while binary dimension is at least max(diameter, log n) and host order at least max(n, 2 diameter).","keywords":["isometric embedding","Cayley graph","abelian group","sum-free set","partial cube","graph census","binary dimension","abelian dividend"],"falsifier":"Either find an odd cycle of length greater than 17 that embeds isometrically into a binary Cayley graph of dimension less than m-1, or exhibit a counter-example subset that violates the cyclic-interval lemma for some larger odd m.","tokens_in":13426,"feed_emoji":"▦","tokens_out":795,"duration_ms":6496,"temperature":0.7,"pith_summary":"Every connected graph on n vertices embeds isometrically into some finite abelian Cayley graph, and a companion construction always works with a binary host of dimension at most n-1. This paper asks how small the host can be. It proves that any binary host needs dimension at least the larger of the graph's diameter and log2 of n, while any abelian host needs order at least the larger of n and twice the diameter; equality to n holds exactly when the graph is already an abelian Cayley graph. Exact binary dimensions are settled for several families: hypercubes, power-of-two completes and even cycles meet the lower bound, stars improve exponentially over the naive embedding via sum-free sets, and odd cycles force the full n-1 dimension (proved up to 17 and reduced to a cyclic-interval lemma). An exhaustive certified census of all 995 connected graphs on at most seven vertices then shows that 57 percent admit a strictly smaller abelian host than the best binary host found, 71 percent use a cyclic factor larger than 2, and only 17 graphs sit exactly on the order floor. Compact non-binary hosts are therefore the typical outcome on small graphs, while binary hosts remain the universally guaranteed construction.","feed_headline":"Most small graphs get smaller abelian hosts than binary ones","feed_subtitle":"Census of 995 graphs finds a 57% abelian dividend; binary hosts remain the universal guarantee","key_machinery":"The geodesic-independence lemma (subset sums of a geodesic word in a binary Cayley graph are distinct) supplies the diameter half of the binary lower bound; the vertex-transitive diameter bound diam(H) ≤ ⌊|H|/2⌋ supplies the order lower bound; maximum sum-free sets in (Z/2Z)^k give the exact star dimension; and a certified search over Hermite-normal-form sublattice compactifications produces the abelian-dividend census.","core_discovery":"The paper establishes matching lower bounds on binary dimension and abelian host order for isometric embeddings of any connected graph, characterises when the host order equals n, computes exact binary dimensions for stars, cycles and other families that fill the entire dimension window, and documents via a certified census of all 995 connected graphs on 2 to 7 vertices that a majority admit a strictly smaller non-binary abelian host than their best binary host.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["57% of graphs n≤7 beat binary hosts via abelian Cayley embeddings","Census: 569 of 995 graphs get abelian hosts smaller than best binary","Abelian dividend: non-binary hosts cut size for most graphs on ≤7 verts","Only 17 graphs meet max(n,2^diam) abelian host order; rest larger","Stars need floor(log2 q)+1 binary dim via sum-free sets, not n-1"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The claim that every odd cycle needs the full naive binary dimension rests on a cyclic-interval lemma that is only proved for covering arcs and verified by computer for cycles of length at most 17.","fun_headline_variants_meta":{"raw":{"variants":["57% of graphs n≤7 beat binary hosts via abelian Cayley embeddings","Census: 569 of 995 graphs get abelian hosts smaller than best binary","Abelian dividend: non-binary hosts cut size for most graphs on ≤7 verts","Only 17 graphs meet max(n,2^diam) abelian host order; rest larger","Stars need floor(log2 q)+1 binary dim via sum-free sets, not n-1"]},"model":"grok-4.5","effort":"low","cost_usd":0.002074,"raw_usage":{"total_tokens":1029,"prompt_tokens":929,"num_sources_used":0,"completion_tokens":100,"cost_in_usd_ticks":20740000,"prompt_tokens_details":{"text_tokens":929,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":0,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":929,"tokens_out":100,"duration_ms":1654,"temperature":1.0,"reasoning_tokens":0,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T15:03:55.973426+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Either find an odd cycle of length greater than 17 that embeds isometrically into a binary Cayley graph of dimension less than m-1, or exhibit a counter-example subset that violates the cyclic-interval lemma for some larger odd m.","supporting_citations":[],"review_version":1}