{"id":"68e5556d-8c22-4cd6-add7-46b511f05677","arxiv_id":"2507.12748","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Improved upper bounds: diameter of partition polytopes ≤ κ1+⌈κ2/2⌉, and path/cycle odd-covers of Eulerian graphs ≤ ⌈3Δ/4⌉.","lead":"This math paper proves tighter upper bounds on two graph and polytope problems: the diameter of partition polytopes drops from 2K to about 1.5K, and odd-covers of Eulerian graphs drop from Δ to 0.75Δ. The proofs refine a classic linear-arboricity argument and leave both exact constants as open conjectures.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; Lemma 2.2's extension is terse but sound.","rationale":"The reader identified Lemma 2.2's second assertion as the most load-bearing assumption, and I agree it is the step on which the upper-bound proofs depend. However, careful analysis shows the assertion is correct: the unique vertex with out-degree greater than t has out-degree exactly Δ, and an Eulerian circuit split at its returns gives Δ directed cycles through that vertex, making the desired choice of Δ−t cycles possible. The paper's remark is too terse and should be expanded, but this is an expositional fix rather than a correctness gap. I checked the arithmetic in the main reductions (Corollaries 2.3, 2.4, Theorems 1.1, 4.3, 4.4) and found no internal inconsistency; Lemma 3.1's construction is intricate but sound, and the odd-cover arguments for degree-4 Eulerian graphs are coherent. No change to the reader's ACCEPT verdict is needed.","tokens_in":30201,"tokens_out":32138,"duration_ms":333162,"concrete_test":"Formalize Lemma 2.2's second statement: take an Eulerian circuit starting at the unique high-out-degree vertex, split it at each return to that vertex to obtain Δ simple directed cycles containing it, choose Δ−t of them as the special cycles, and check that the remaining graph has maximum out-degree at most t and decomposes into t directed polycycles.","verdict_should_be":"UNCHANGED","load_bearing_attack":"All main theorems (1.1, 4.1, 4.2, 4.3, 4.4) rest on Lemma 2.2's second assertion: when at most one vertex has out-degree > t, the excess polycycles can be chosen as directed cycles. The paper's remark is under-justified: it assumes a cycle decomposition with the unique high-out-degree vertex in the first Δ−t cycles without proving existence. This gap closes: the unique vertex with out-degree > t must have out-degree exactly Δ, so an Eulerian circuit starting at that vertex, split at every return to it, yields Δ simple directed cycles all containing the vertex. Removing any Δ−t of these cycles leaves an Eulerian digraph with maximum out-degree at most t, which the first part of Lemma 2.2 decomposes into t polycycles. Thus the lemma is true and the concern does not land; the paper should expand the remark, but no central claim is jeopardized.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies two decomposition problems: bounding the combinatorial diameter of partition polytopes PP(κ1,...,κn) and bounding the minimum size of path and cycle odd-covers of graphs. It proves Theorem 1.1, that the diameter of PP(κ1,...,κn) is at most κ1+⌈κ2/2⌉, improving the previous bound 2κ1, and Theorem 1.5, that every graph has a path odd-cover of size at most max{vodd(G)/2, ⌈(vodd(G)/2+3Δe(G))/4⌉}, with the Eulerian case giving path and cycle odd-covers of size at most ⌈3Δ(G)/4⌉. The proofs are built on a polycycle decomposition lemma (Lemma 2.2), a new factorization of the product of two p-balanced permutations into three p-cycles (Lemma 3.1), and a refinement of the Akiyama-Exoo-Harary proof that graphs of maximum degree 4 have linear arboricity at most 3.","tokens_in":30387,"tokens_out":36669,"duration_ms":383538,"significance":"If the proofs are completed as indicated below, these are the best known bounds for both problems. The paper also provides lower-bound constructions, including an exact diameter computation for PP(3,3,3,3,3,3), and formulates plausible conjectures that identify the likely remaining gap. The common framework connecting partition polytopes to odd-covers through the AEH linear arboricity proof is elegant, and the central construction in Lemma 3.1 is new and, as far as I checked, correct. The proofs are mostly detailed, but two load-bearing points need attention before the paper is ready for publication.","major_comments":[{"comment":"The second statement of Lemma 2.2 is load-bearing: it is used in Corollaries 2.3 and 2.4, and hence in Theorems 1.1, 4.1, 4.2, 4.3, and 4.4. The remark intended to prove this statement assumes a cycle decomposition with v in the first Δ−t cycles without justifying that such a decomposition exists. Please expand the argument: take an Eulerian circuit starting at the unique vertex v with out-degree Δ, split it at each return to v to obtain Δ closed trails, extract from each trail a simple directed cycle through v, and delete Δ−t of these cycles. The remaining digraph is Eulerian with maximum out-degree at most t, so the first part of the lemma applies.","section":"Section 2.2, Lemma 2.2"},{"comment":"The displayed estimate for |P| contains a false equality. For example, with |M|=3 and k=3 (so t=2 and Δ′=6), the left-hand side |M|+1+⌈3/2(k−( |M|+1)/2)⌉ equals 6, while (|M|+3Δ′+1)/4 equals 5.5; a further example is |M|=1, k=2, giving 4 versus 3.5. The intended bound |P|≤⌈(|M|+3Δ′)/4⌉ is still true, but it should be derived as 2t+⌈3(k−t)/2⌉=⌈(|M|+3Δ′)/4⌉. Please correct the displayed chain and the subsequent sentence 'Since |M| is odd and Δ′ is even...'.","section":"Section 4.2, proof of Theorem 4.3, Subcase 1b"}],"minor_comments":[{"comment":"The final step says 'it is readily verified that CDG(p2,p′) ... cannot be decomposed into two directed Hamiltonian cycles'; this is a finite but nontrivial check, and it should be expanded or moved to an appendix.","section":"Section 3.2, Lemma 3.4"},{"comment":"The step applying Lemma 4.7 to obtain an edge e∈{x1x2,x2x3} is terse; a sentence explaining which edge is chosen in each case of Lemma 4.7 would improve readability.","section":"Section 4.2, Lemma 4.8"},{"comment":"The notation 'H2i−1 + H2i' should be 'H2i−1 ∪ H2i' (or '⊕') to avoid confusion with an edge sum.","section":"Section 4.3, proof of Theorem 4.4"},{"comment":"In Eq. (2), the subscript 'κ2−κ1' appears to be a typo; it should be 'κ1−κ2' as in Corollary 2.3. Also, the sentence 'Let κ1 ≥ ··· ≥ κn ≥ 0 be integers summing to n' should say 'summing to m'.","section":"Section 3.1, proof of Theorem 1.1"},{"comment":"The proof of Lemma 4.13 is very long and dense; moving the case analysis to an appendix or adding a brief overview of the cases would help the reader.","section":"Section 4.3, Lemma 4.13"}],"recommendation":"major_revision","confidential_remarks":"The paper is strong and the main theorems appear to be correct. The needed changes are small but real: one false equality in a subcase of Theorem 4.3 and an under-justified statement in Lemma 2.2. I recommend a revision rather than acceptance as is, but I do not see any obstacle to publication once these points are fixed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the main results are real: the paper improves the partition polytope diameter bound from 2K to 1.5K and the odd-cover bound from Δ to 0.75Δ, and neither reduction is just an application of earlier machinery. Second, the key technical steps hold up under inspection—I checked Lemma 3.1 and the parity-controlled matching lemmas, and they are correct.\n\nWhat is actually new: Lemma 3.1, which expresses the product of two p-balanced permutations with disjoint supports as three p-cycles, is the core of the diameter improvement. The matching lemmas in Section 4 (4.8 and 4.13) refine the AEH linear-arboricity argument in a way that is specific to odd-covers. The paper also proves the base cases are best possible and gives honest lower bounds, leaving the conjectures open rather than overclaiming. The connection between the two problems through the AEH proof is a nice unifying observation, and the writing is generally careful.\n\nThe soft spots are mostly presentation. Lemma 2.2’s second assertion is borrowed from [6,7] but justified only in a terse remark. The stress-test note shows the gap closes via an Eulerian circuit argument: the unique high-out-degree vertex must have out-degree Δ, so splitting an Eulerian circuit at that vertex gives the needed cycles. That should be spelled out in the paper, but it is not a real flaw. Lemma 3.4 also leaves a case check as “readily verified”; that is probably fine but deserves a bit more detail. The reliance on prior work for the polycycle decomposition framework is appropriate and not circular.\n\nWho this is for: anyone working on combinatorial diameters of partition polytopes or on graph odd-covers. It improves known bounds on two active problems and the proofs are detailed enough to verify. It deserves a serious referee; I would send it out with minor revision requests, mainly expanding the Lemma 2.2 remark and the Lemma 3.4 case check.","headline":"Genuinely new bounds on two problems, with proofs that mostly check out; the main soft spot is a too-terse justification in Lemma 2.2, which is fixable and not fatal.","tokens_in":30953,"tokens_out":1858,"would_cite":true,"duration_ms":21936,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C38","05C62","05C70","52B05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two decomposition bounds improve at once: partition polytopes have diameter at most $\\kappa_1+\\lceil \\kappa_2/2 \\rceil$, and every Eulerian graph has path and cycle odd-covers of size at most $\\lceil 3\\Delta/4 \\rceil$.","keywords":["partition polytope","combinatorial diameter","odd-cover","cycle cover","path cover","linear arboricity","Eulerian graph","p-cycle decomposition"],"falsifier":"A concrete falsifier: find an Eulerian graph of maximum degree 4 that lacks either a path odd-cover or a cycle odd-cover of size 3; such a graph would directly refute Theorems 4.1 and 4.2, and an exhaustive search over 4-regular Eulerian graphs could look for it.","tokens_in":30040,"feed_emoji":"🔁","tokens_out":8456,"duration_ms":93203,"temperature":0.7,"pith_summary":"This paper proves two improved upper bounds that had previously resisted tightening. For the partition polytope whose vertices encode all ways to assign $m$ items to $n$ clusters of prescribed sizes, the combinatorial diameter is at most $\\kappa_1+\\lceil \\kappa_2/2 \\rceil$, where $\\kappa_1 \\ge \\kappa_2 \\ge \\cdots$ are the cluster sizes; this is roughly $3K/2$ in terms of the largest cluster size $K$, improving the known $2K$. Separately, every Eulerian graph with maximum degree $\\Delta$ admits a path odd-cover and a cycle odd-cover, each of size at most $\\lceil 3\\Delta/4 \\rceil$, improving the known $\\Delta$. Both results come from the same mechanism: two edge-disjoint polycycles can be replaced by three cycles or three paths, and the paper refines an old linear-arboricity argument to make that replacement work.","feed_headline":"Partition polytope diameter bound drops to 1.5K","feed_subtitle":"Old bounds were 2K and Δ; the new ones come from converting pairs of cycles into triples.","key_machinery":"The central object is the polycycle decomposition. A polycycle is a graph whose every connected component is a cycle, and a directed polycycle is the directed analogue. Lemma 2.2, taken from earlier work cited in the paper, says that an Eulerian directed multigraph with maximum out-degree $\\Delta$ splits into $\\Delta$ edge-disjoint directed polycycles, with an extra condition making some of them directed cycles when only one vertex has large out-degree. Corollaries 2.3 and 2.4 translate this into p-cycle decompositions of clustering difference graphs and into undirected polycycle decompositions. The new step, Lemma 3.1, shows that two p-balanced permutations with disjoint supports can be written as three p-cycles; this is exactly the 'two polycycles become three cycles' repair that yields the diameter bound. On the odd-cover side, the same repair is performed by refining the classical linear-arboricity proof through transversal pairs of matchings and a parity invariant $p(F)$, yielding parity-controlled path and cycle odd-covers.","core_discovery":"On its own terms, the paper establishes that the diameter of $\\mathrm{PP}(\\kappa_1,\\ldots,\\kappa_n)$ is at most $\\kappa_1 + \\lceil \\kappa_2/2 \\rceil$, and that every Eulerian graph $G$ with maximum degree $\\Delta$ has a cycle odd-cover and a path odd-cover of size at most $\\lceil 3\\Delta/4 \\rceil$. The degree-4 base case is best possible: every Eulerian graph of maximum degree 4 is the symmetric difference of at most three paths and also of at most three cycles, and some such graphs require three. The authors view these as two faces of one phenomenon, since both proofs start by decomposing an Eulerian (di)graph into polycycles and then convert a pair of polycycles into three cycles or paths; this is the essential step that improves the earlier bounds of $2K$ and $\\Delta$.","pith_inferences":["The paper's own conjectures suggest the truth lies near the lower bounds: diameter near $4\\kappa_1/3$ and odd-cover size near $\\Delta/2$, possibly plus a constant; the exact value of that constant is the remaining question.","The failure of the naive $\\kappa_1=3$ analogue (the diameter of $\\mathrm{PP}(3,3,3,3,3,3)$ is exactly 5, not 4) indicates that a full resolution will need new structural ideas beyond pairing polycycles.","A natural testable extension is whether the same 'two polycycles into three cycles' repair improves bounds for transportation polytopes with general margins, since partition polytopes are a special case.","The formal similarity between Lemma 3.1 and the path odd-cover construction suggests, as the paper itself asks, that a single algebraic statement may unify diameter bounds and odd-cover bounds; establishing such a statement would likely transfer improvements between the two problems."],"forward_implications":["The partition polytope $\\mathrm{PP}(\\kappa_1,\\ldots,\\kappa_n)$ has diameter at most $\\kappa_1+\\lceil \\kappa_2/2 \\rceil$, improving the previous $2\\kappa_1$ bound and giving $\\lceil 3K/2 \\rceil$ when $K=\\kappa_1$.","For the case $\\kappa_1=2$, the diameter is at most 3, and examples show this is tight, so the base of the diameter bound is already optimal.","Every Eulerian graph with maximum degree $\\Delta$ has both a path odd-cover and a cycle odd-cover of size at most $\\lceil 3\\Delta/4 \\rceil$, cutting the gap to the trivial lower bound $\\Delta/2$ roughly in half.","For general graphs, the path odd-cover size is at most $\\max\\{v_{\\rm odd}(G)/2, \\lceil (v_{\\rm odd}(G)/2+3\\Delta_e(G))/4 \\rceil\\}$, so graphs with many odd-degree vertices achieve the trivial lower bound $v_{\\rm odd}(G)/2$."],"supporting_citations":[{"why":"Supplies the classical result that every graph of maximum degree 4 decomposes into three linear forests; both main proofs refine its argument.","marker":"[1]"},{"why":"Gives the prior diameter bound $\\kappa_1+\\kappa_2$, the clustering-difference-graph edge characterization, the polycycle decomposition lemma, and the earlier lower-bound construction.","marker":"[6]"},{"why":"Gives the prior odd-cover bound $\\Delta$, a matching-based derivation of the polycycle decomposition lemma, and the framework for lifting degree-4 results to general graphs.","marker":"[7]"},{"why":"Characterizes edges of transportation polytopes, which identifies edge walks of partition polytopes with cyclic exchanges and p-cycle decompositions.","marker":"[17]"}],"fun_headline_variants":["Partition polytope diameter bound cut to ⌈3K/2⌉","Odd-cover size bound improved to ⌈3Δ/4⌉","Both bounds improved: ⌈3K/2⌉ and ⌈3Δ/4⌉","Diameter drops to 1.5K, odd-cover to 0.75Δ","New proofs shrink partition and odd-cover bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"All the upper-bound proofs start from the claim that every Eulerian directed multigraph splits into a bounded number of directed cycles/polycycles, with a second part (justified only by a remark) about making the extra pieces cycles; if that second part fails, the diameter and odd-cover bounds lose their foundation.","fun_headline_variants_meta":{"raw":{"variants":["Partition polytope diameter bound cut to ⌈3K/2⌉","Odd-cover size bound improved to ⌈3Δ/4⌉","Both bounds improved: ⌈3K/2⌉ and ⌈3Δ/4⌉","Diameter drops to 1.5K, odd-cover to 0.75Δ","New proofs shrink partition and odd-cover bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000858,"raw_usage":{"total_tokens":3729,"prompt_tokens":954,"completion_tokens":2775,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":570,"completion_tokens_details":{"reasoning_tokens":2669}},"tokens_in":570,"tokens_out":2775,"duration_ms":23799,"temperature":1.0,"reasoning_tokens":2669,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:43:27.035869+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete falsifier: find an Eulerian graph of maximum degree 4 that lacks either a path odd-cover or a cycle odd-cover of size 3; such a graph would directly refute Theorems 4.1 and 4.2, and an exhaustive search over 4-regular Eulerian graphs could look for it.","supporting_citations":[{"cited_title":"Covering and packing in graphs IV: Linear arboricity","cited_arxiv_id":null,"evidence_quote":"Supplies the classical result that every graph of maximum degree 4 decomposes into three linear forests; both main proofs refine its argument."},{"cited_title":"On the diameter of partition polytopes and vertex-disjoint cycle cover","cited_arxiv_id":null,"evidence_quote":"Gives the prior diameter bound $\\kappa_1+\\kappa_2$, the clustering-difference-graph edge characterization, the polycycle decomposition lemma, and the earlier lower-bound construction."},{"cited_title":"Path Odd-Covers of Graphs","cited_arxiv_id":"2306.06487","evidence_quote":"Gives the prior odd-cover bound $\\Delta$, a matching-based derivation of the polycycle decomposition lemma, and the framework for lifting degree-4 results to general graphs."},{"cited_title":"Facets and vertices of transportation polyhedra","cited_arxiv_id":null,"evidence_quote":"Characterizes edges of transportation polytopes, which identifies edge walks of partition polytopes with cyclic exchanges and p-cycle decompositions."}],"review_version":1}