{"id":"ccc3b495-e307-4650-b306-e0db72b228b1","arxiv_id":"2411.11124","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Strong parity edge-colorings are exactly refinements of canonical edge-colorings from injective binary labelings, yielding exact and asymptotic color counts and a bipartite counterexample.","lead":"This paper characterizes strong parity edge-colorings of graphs as refinements of canonical colorings built from binary vertex labels. The authors use this characterization to settle conjectures on complete bipartite graphs, hypercubes, path powers, and bipartite differences between two coloring numbers.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.5's lower-bound proof asserts |T∩Y_d| ≥ ⌈k/d⌉ from saturation, but saturation only gives |T∩Y_d| ≥ lg|Y_d|; for k=64, r=4, d=4 this would require 5 ≥ 16. The Ω(k log k) lower bound for the bipartite construction is therefore unsupported as written.","rationale":"The reader identified the cut-vertex analogue of Lemma 5.1 as the main gap in the bipartite application. I agree that the upper-bound proof in Construction 5.4 is under-specified, but I find a more basic problem in the lower-bound proof. The central algebraic characterization, Theorem 1.5/2.7, appears sound: the coset argument is standard, the quotient space is a binary vector space, and the canonical coloring uses no more colors than the original spec. The path-power results also appear internally consistent. However, Theorem 5.5 contains a numerically false inequality, and the proof of the lower bound depends on it directly. Saturating sets only require logarithmically many selected vertices in each prefix; they cannot force |T∩Y_d| ≥ k/d for all d. A concrete saturating set selecting one vertex per dyadic interval has back-degree sum far below k ln k. Therefore the advertised separation p̂/p → ∞ is not established by the written proof. The paper should be accepted conditionally only after a corrected lower-bound proof for Theorem 5.5 is supplied, or Theorem 1.14 is downgraded to a conjecture.","tokens_in":17092,"tokens_out":25928,"duration_ms":335421,"concrete_test":"Compute, by dynamic programming over the vertex ordering in Theorem 5.5 for k = 64, 128, ..., 10^4, the exact minimum over saturating sets T of ∑_{v∈T} d⁻(v). An optimal saturating set has ⌈lg n⌉ elements with the i-th selected position at most 2^{i−1}, so a standard prefix DP yields the minimum. If the minimum is o(k ln k), as expected (O(k^{2/3} log k)), then Lemma 3.3 cannot imply Theorem 5.5 and a new lower-bound argument is required.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 5, Theorem 5.5, is the only support for the advertised lower bound in Theorem 1.14. The proof uses Lemma 3.3 and the ordering of G_k. It defines Y_d = ⋃_{ℓ=d}^r V(Z_ℓ) and correctly notes that saturation gives |T∩Y_d| ≥ lg|Y_d|. It then asserts |T∩X_d| ≥ lg|Y_d| − (r−d+1)(2d−2) ≥ ⌈k/d⌉ − (r−d+1)(2d−2). The middle inequality is false in this construction: |V(Z_d)| = 2⌈k/d⌉, but |Y_d| is only a sum of terms 2⌈k/ℓ⌉, at most 2k(1+ln r), so lg|Y_d| = O(log k), whereas ⌈k/d⌉ ≥ k^{2/3} when d=r. For k=64 (r=4, d=4), |Y_4| = 32, so saturation gives at most lg 32 = 5, but the proof needs ⌈64/4⌉ = 16. Since Lemma 3.3's lower bound is a minimum over all saturating sets, this inequality is exactly what forces every saturating T to have large back-degree sum. Without it, a saturating set can be obtained by selecting one vertex in each dyadic interval of the ordering, giving sum O(k^{2/3} log k) rather than (1/3−o(1))k ln k. Thus the proof of Theorem 5.5, and hence the claimed p̂(G)/p(G) ratio in Theorem 1.14, is unsupported as written. This is independent of the cut-vertex gap in the upper-bound proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops an algebraic characterization of strong parity edge-colorings: it defines a binary-vector-space analogue of edge colors and shows (Theorem 1.5 / Theorem 2.7) that every strong parity edge-coloring of a connected graph is a refinement of a canonical edge-coloring arising from an injective binary vertex labeling. This reduces the strong parity edge-chromatic number to a canonical labeling problem. The paper then uses this characterization to prove that \\hat p(K_{s,t}) equals the Hopf–Stiefel function s∘t, to characterize connected graphs with \\hat p(G)=⌈lg n⌉ as subgraphs of the hypercube, to give nearly tight bounds for powers of paths, and to construct bipartite graphs with \\hat p(G)/p(G) arbitrarily large. The first three applications are derived cleanly from the algebraic framework and external results. The bipartite construction, however, contains a serious gap in the proof of the advertised lower bound.","tokens_in":17500,"tokens_out":11450,"duration_ms":112807,"significance":"The algebraic framework in Section 2 is elegant and appears correct; Theorem 2.7 is a genuine structural result that unifies earlier work of Bunde, Milans, West, and Wu and yields the Hopf–Stiefel formula and the hypercube characterization as short corollaries. These contributions alone make the paper valuable. The paper also makes good use of external theorems (Yuzvinsky's sumset theorem, the Havel–Morávek hypercube characterization) without circularity. However, the proof of the lower bound for the bipartite ratio construction contains a false inequality, so the advertised Theorem 1.14 is not established as written. The paper should not be accepted in its current form.","major_comments":[{"comment":"The proof of the lower bound asserts the chain |T∩X_d| ≥ lg|Y_d| − (r−d+1)(2d−2) ≥ ⌈k/d⌉ − (r−d+1)(2d−2). The second inequality is false. Saturating only gives |T∩Y_d| ≥ lg(1+|Y_d|), which is O(log k) because |Y_d| is a sum of terms 2⌈k/ℓ⌉ and is at most 2k(1+ln r). For example, if k=64, r=4, and d=4, then |Y_4|=32 and lg|Y_4|=5, but ⌈k/d⌉=16. Thus the bound |T∩X_d| ≥ ⌈k/d⌉−2rd is unsupported, and the subsequent sum ∑_{d=1}^r |T∩X_d| ≥ (1/3−o(1))k ln k does not follow. Since this is the only argument for the lower bound in Theorem 1.14, the claim that \\hat p(G_k)/p(G_k) is unbounded for bipartite graphs is not proved.","section":"Section 5, Theorem 5.5"},{"comment":"The proof cites “Proposition 1.3” when deriving p(G)=n+1, but no Proposition 1.3 appears in the manuscript. The equality p(G)=n+1 is load-bearing for the disproof of Conjecture 1.12, because the subsequent lower bound on \\hat p(G) is compared to this value. Please supply the correct reference or a proof of the needed bound on p(K_{n,n}) (or on the relevant component).","section":"Section 5, Theorem 5.2"},{"comment":"Lemma 5.1 is stated only for a graph with one cut-edge, but G_k is formed by identifying a vertex u across r blocks, leaving r cut-edges incident to u. The sentence “Lemma 5.1 now yields p(G_k) < 2k + k^{1/3}” skips the necessary induction over these r cut-edges. The bound is plausible and can be obtained by iterating Lemma 5.1 while giving a distinct fresh color to each new cut-edge, but the manuscript should state this explicitly because the proof as written does not formally cover the multi-cut-edge setting.","section":"Section 5, Construction 5.4"}],"minor_comments":[{"comment":"Theorem 1.3 is stated and proved twice: once after Example 2.8 using Theorem 1.5 and again in Section 3 using Lemma 3.1. One of the two proofs should be removed or the duplication should be noted.","section":"Section 2 and Section 3"},{"comment":"Remark 5.3 claims stronger bounds 2n−(2+o(1))√n ≤ \\hat p(G) ≤ 2n−lg n+1 for the graph of Theorem 5.2 and says the details are omitted. As written these are unproved assertions; they should be labeled as conjectural or a proof should be supplied, especially since the wording suggests they follow from the earlier tools.","section":"Section 5, Remark 5.3"},{"comment":"The statement that X_d consists of Y_d except for 2d−2 vertices at the beginning of each Z_ℓ appears off by one: for d=1, the first vertex of each Z_ℓ has back-degree 0, so one vertex is excluded per block, not zero. The subtraction term should be adjusted consistently.","section":"Section 5, Theorem 5.5 proof"},{"comment":"There are several typographical errors: “establishs” in Section 4, “color clases” in the proof of Theorem 2.7, and a formatting artifact “Ha/suppress luszczak” in reference [1]. These should be corrected.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The algebraic characterization of strong parity edge-colorings is the clear strength of this paper and is likely correct. The main obstacle is the lower-bound proof for Theorem 1.14, which rests on a demonstrably false inequality in Theorem 5.5. If the authors can repair that proof, or alternatively remove the bipartite ratio claim from the abstract and present the remaining results, the paper would be publishable. Given the current state, I cannot recommend acceptance without a corrected proof of the advertised ratio result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere’s my honest take on the Bradshaw–Norin–West paper. The core is real: Theorem 1.5—that every strong parity edge-coloring of a connected graph is a refinement of a canonical edge-coloring—is a clean, new structural result. The proof via cosets over F2 is elegant, and the applications to K_{s,t} (proving the Hopf–Stiefel formula) and to the hypercube equality characterization (Theorem 1.3) are solid and genuinely answer questions from the 2007–2008 papers. The path-power bounds also look plausible and are built on a clever Gray-code construction.\n\nBut the last application—the bipartite counterexample in Theorem 5.5—has a serious gap. The proof claims that for the saturating set T, |T∩X_d| ≥ lg|Y_d| − ... ≥ ⌈k/d⌉ − ... . The second inequality is false: lg|Y_d| is O(log k), while ⌈k/d⌉ grows polynomially for d near k^{1/3}. For k=64, d=4, |Y_d|=32, so saturation gives at most 5, but the proof needs 16. Without this inequality, the lower bound (1/3−o(1))k ln k does not follow. The Ω(k log k) lower bound in Theorem 1.14 is therefore unsupported as written. This is a load-bearing flaw, not a typo.\n\nThere are smaller issues: Lemma 5.1 is stated for a cut-edge, but Construction 5.4 uses a cut vertex with many cut-edges; the intended iterative argument is probably correct, but it isn’t written. Theorem 5.2 cites a nonexistent Proposition 1.3. Remark 5.3 asserts bounds without proof. These are fixable.\n\nThe algebraic framework and the first three applications are worth publishing. The bipartite construction may also be salvageable—the upper bound is likely fine, and the lower bound might hold by a more careful argument—but the current manuscript cannot be accepted as is. I’d send it to a serious referee, with the clear instruction that the lower-bound proof in Theorem 5.5 must be corrected or replaced. If the authors fix that, this will be a very good paper.","headline":"Strong algebraic characterization, but the bipartite lower bound rests on a false inequality and needs fixing.","tokens_in":18039,"tokens_out":5740,"would_cite":true,"duration_ms":126989,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every strong parity edge-coloring of a connected graph is a refinement of a coloring generated by an injective binary labeling, and this characterization yields exact values and answers open questions.","keywords":["strong parity edge-coloring","parity edge-coloring","canonical edge-coloring","binary labeling","Hopf-Stiefel function","hypercube embeddings","path powers","bipartite graphs"],"falsifier":"Compute $p(G_k)$ exactly for small $k$ in Construction 5.4 by exhaustive search. If $p(G_k)$ exceeds $2k+k^{1/3}$ for some $k$, the cut-vertex reuse step fails and the claimed unbounded ratio is not established; a direct display of a parity path in the reused branch coloring would also refute it.","tokens_in":16883,"feed_emoji":"🎨","tokens_out":11930,"duration_ms":114762,"temperature":0.7,"pith_summary":"Strong parity edge-colorings forbid open walks in which every color appears an even number of times. This paper proves that all such colorings of connected graphs have one rigid shape: they are exactly the colorings obtained by splitting the color classes of a canonical edge-coloring, where the color of an edge is the binary sum of an injective labeling of its endpoints. With that characterization in hand, the minimum number of colors becomes an optimization over binary labelings, and the paper uses it to settle exact values and open questions that previously resisted direct coloring arguments. The payoff includes the conjectured value for complete bipartite graphs, a hypercube characterization of graphs with smallest possible strong parity number, near-tight bounds for powers of paths, and bipartite graphs where the strong parity number exceeds the parity number by an arbitrarily large factor.","feed_headline":"Strong parity edge-colorings are binary labelings in disguise","feed_subtitle":"One characterization yields exact complete-bipartite values, hypercube criterion, and bipartite counterexamples.","key_machinery":"The load-bearing construction is the family of walk-sum sets $S_v$: for a fixed root $r$, each $S_v$ collects the binary sums (symmetric differences of color sets) of all walks from $r$ to $v$. Lemma 2.4 shows a coloring is strong exactly when these sets are pairwise disjoint; Lemma 2.5 shows they are cosets of the subspace $S_r$ of closed-walk sums; Lemma 2.6 shows the cosets form a binary vector space. The edge $uv$ is then assigned the coset $S_u+S_v$, producing the canonical coloring that refines the original one. The atomic encoding of colors as unit vectors in $\\mathbb{F}_2^\\infty$ is what makes these sums meaningful. This mechanism is what converts a coloring problem into a linear algebra problem and drives every application.","core_discovery":"The paper's central theorem is that every strong parity edge-coloring $\\phi$ of a connected graph is isomorphic to a refinement of a canonical edge-coloring. A canonical edge-coloring is generated by an injective binary labeling $f$ that assigns each vertex a vector over $\\mathbb{F}_2$; the color of edge $uv$ is $f(u)+f(v)$. Because splitting color classes of a strong parity coloring preserves the property, every canonical coloring is automatically strong; Theorem 1.5 supplies the converse. Consequently $\\hat{p}(G)$, the minimum number of colors in a strong parity edge-coloring, equals the minimum number of colors in any canonical edge-coloring of $G$, reducing the problem to an injective labeling problem. The theorem is proved by encoding colors as unit vectors, fixing a root, and collecting for each vertex $v$ the set $S_v$ of binary sums of colors along all walks from the root to $v$; for a strong parity coloring these sets are pairwise disjoint cosets that themselves form a binary vector space, and the map sending edge $uv$ to the coset $S_u+S_v$ is exactly the required canonical coloring.","pith_inferences":["If the characterization is correct, computing $\\hat{p}(G)$ for small graphs can be reduced to a search over injective binary labelings rather than over colorings; an exhaustive check on graphs up to eight vertices would be a quick way to test the theorem and to tabulate the parameter.","The bipartite counterexample points to cut structure as the engine of the gap between $p$ and $\\hat{p}$. A natural next question, not addressed in the paper, is whether bounded-degree bipartite graphs can already force an unbounded ratio; the construction here uses vertices of degree growing with $k$.","The Gray-code coloring of path powers is conjectured optimal. If true, exact values for $\\hat{p}(P_n^\\ell)$ with small fixed $\\ell$ would follow, and the conjecture could be checked by computing the walk-sum lower bound on small instances.","The sumset argument for $K_{s,t}$ suggests a coding-theoretic reading: a canonical coloring with $k$ colors is a map from vertices to $\\mathbb{F}_2^k$ whose edge-difference set is small, so optimizing $\\hat{p}$ is a finite-dimensional difference-set minimization that may support algorithmic or probabilistic bounds not explored here."],"forward_implications":["The strong parity chromatic number of $K_{s,t}$ is the Hopf–Stiefel function $s\\circ t$, resolving the conjecture from the papers that introduced these parameters; in particular $\\hat{p}(K_{n,n})$ is the least power of $2$ at least $n$.","A connected $n$-vertex graph satisfies $\\hat{p}(G)=\\lceil \\log_2 n\\rceil$ exactly when it is a subgraph of the hypercube $Q_{\\lceil \\log_2 n\\rceil}$, answering the equality question posed in [3].","For the $\\ell$th power of an $n$-vertex path, $\\hat{p}(P_n^\\ell)$ lies between $\\ell\\lceil \\log_2 n\\rceil-\\binom{\\ell+1}{2}$ and $\\ell\\lceil \\log_2 n\\rceil-\\ell(\\lfloor \\lg \\ell\\rfloor-1)$, so the bounds agree to $O(\\ell^2)$ and are asymptotically $\\ell\\lceil \\log_2 n\\rceil$ for fixed $\\ell$.","There exist bipartite graphs with $\\hat{p}(G)/p(G)$ arbitrarily large; for each $k$ there is a bipartite $G_k$ with $p(G_k)\\le 2k+k^{1/3}$ and $\\hat{p}(G_k)\\ge(\\frac13-o(1))k\\ln k$, disproving the conjecture that the two parameters agree on bipartite graphs.","Because every strong parity edge-coloring is a refinement of a canonical coloring, finding an optimal strong coloring is equivalent to finding an injective binary labeling that minimizes the number of distinct edge-difference vectors, so future lower bounds can be phrased in this algebraic language."],"supporting_citations":[{"why":"introduces strong parity edge-colorings, proves the complete-graph case, and supplies Observation 1.4 that canonical colorings are specs.","marker":"[4]"},{"why":"introduces the parameters, proves the ceil(log2 n) lower bound, and poses the questions and conjecture answered in this paper.","marker":"[3]"},{"why":"provides the hypercube-subgraph characterization used to prove Theorem 1.3.","marker":"[7]"},{"why":"gives the sumset lower bound |A+B| >= s o t with equality, which together with Theorem 1.5 yields p-hat(K_{s,t}) = s o t.","marker":"[17]"},{"why":"provides the closed formula for the Hopf–Stiefel function used to evaluate the diagonal and related cases.","marker":"[12]"},{"why":"supplies the binary reflected Gray code underlying the upper bound construction for powers of paths.","marker":"[6]"}],"fun_headline_variants":["Binary labels unlock strong parity edge-coloring","Hypercube criterion for optimal parity coloring","Complete bipartite parity coloring conjecture proven","Bipartite graphs break parity coloring equality","Characterizing strong parity edge-colorings via bits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the bipartite ratio application, the argument assumes that joining several components at a single vertex behaves like joining them by an edge: the reused color sets in the components together with one fresh color for the attachment edges never create a parity path, so the upper bound on $p(G_k)$ holds.","fun_headline_variants_meta":{"raw":{"variants":["Binary labels unlock strong parity edge-coloring","Hypercube criterion for optimal parity coloring","Complete bipartite parity coloring conjecture proven","Bipartite graphs break parity coloring equality","Characterizing strong parity edge-colorings via bits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000351,"raw_usage":{"total_tokens":2020,"prompt_tokens":1159,"completion_tokens":861,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":775,"completion_tokens_details":{"reasoning_tokens":796}},"tokens_in":775,"tokens_out":861,"duration_ms":9530,"temperature":1.0,"reasoning_tokens":796,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:55:08.384992+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute $p(G_k)$ exactly for small $k$ in Construction 5.4 by exhaustive search. If $p(G_k)$ exceeds $2k+k^{1/3}$ for some $k$, the cut-vertex reuse step fails and the claimed unbounded ratio is not established; a direct display of a parity path in the reused branch coloring would also refute it.","supporting_citations":[{"cited_title":"Havel and J","cited_arxiv_id":null,"evidence_quote":"provides the hypercube-subgraph characterization used to prove Theorem 1.3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces strong parity edge-colorings, proves the complete-graph case, and supplies Observation 1.4 that canonical colorings are specs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces the parameters, proves the ceil(log2 n) lower bound, and poses the questions and conjecture answered in this paper."},{"cited_title":"Yuzvinsky, Orthogonal pairings of Euclidean spaces","cited_arxiv_id":null,"evidence_quote":"gives the sumset lower bound |A+B| >= s o t with equality, which together with Theorem 1.5 yields p-hat(K_{s,t}) = s o t."},{"cited_title":"Plagne, Additive number theory sheds extra light on t he Hopf–Stiefel ◦ function","cited_arxiv_id":null,"evidence_quote":"provides the closed formula for the Hopf–Stiefel function used to evaluate the diagonal and related cases."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the binary reflected Gray code underlying the upper bound construction for powers of paths."}],"review_version":1}