Pith. sign in

REVIEW 2 major objections 5 minor 21 references

Improved Decomposition Bounds for Partition Polytopes and Odd-Covers

T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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$.

desk verdict 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. read the letter →

arxiv 2507.12748 v2 pith:7FVVBOOV submitted 2025-07-17 math.CO

Steffen Borgwardt , Zdeněk Dvořák , Bryce Frederickson , Abigail Nix , Youngho Yoo This is my paper · ORCID
classification math.CO MSC 05C3805C6205C7052B05
keywords partitionpolytopecombinatorialdiameterodd-covercyclecoverpathlineararboricityEuleriangraphp-cycledecomposition
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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$.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. [Section 2.2, Lemma 2.2] 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.
  2. [Section 4.2, proof of Theorem 4.3, Subcase 1b] 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...'.
minor comments (5)
  1. [Section 3.2, Lemma 3.4] 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.
  2. [Section 4.2, Lemma 4.8] 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.
  3. [Section 4.3, proof of Theorem 4.4] The notation 'H2i−1 + H2i' should be 'H2i−1 ∪ H2i' (or '⊕') to avoid confusion with an edge sum.
  4. [Section 3.1, proof of Theorem 1.1] 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'.
  5. [Section 4.3, Lemma 4.13] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the improved bounds are derived from new, self-contained lemmas; citations supply only independent decomposition infrastructure.

full rationale

The paper's main claims do not reduce to the cited bounds they improve. Theorem 1.1 follows from the new Lemma 3.1, whose proof is self-contained (via matchings and a 2-coloring argument), together with the external polycycle-decomposition Lemma 2.2. The odd-cover results build on Theorems 4.1 and 4.2, which are proven in the paper from the Akiyama-Exoo-Harary argument and the parity/transversal-matching framework developed here. The citations to [6,7] are used for Lemma 2.2 and auxiliary technical tools; these are parameter-free external results that do not contain the target inequalities, so they are independent support rather than circular inputs. The terse remark justifying the second part of Lemma 2.2 is sound: in an Eulerian digraph, every directed cycle in a cycle decomposition contains the unique high-out-degree vertex, so any Δ−t cycles can be removed. No fitted parameters, renamed known results, or self-citation chains carry the central derivations. The paper's own contribution is a genuine new construction, not an unpacking of its assumptions.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters or invented entities. The paper relies on three background results: the polycycle decomposition of Eulerian digraphs (Lemma 2.2, cited from [6,7]), the edge characterization of transportation polytopes (from [17] via [6]), and total unimodularity of the partition polytope. The AEH linear arboricity theorem is re-proved inside the paper (Lemma 2.8).

assumptions (3)
  • domain assumption Every Eulerian directed multigraph with maximum out-degree Δ admits a decomposition into Δ edge-disjoint directed polycycles (Lemma 2.2).
    Cited from [6,7]; the second (extra condition) part is justified in a remark, but the first part is taken as a black box. Used in Corollary 2.3 and Corollary 2.4 to launch the proofs of Theorems 1.1, 4.3, and 4.4.
  • standard math Two vertices of PP(κ1,...,κn) are adjacent iff their clustering difference graph is a simple directed cycle (Klee-Witzgall [17] as presented in [6]).
    This converts the polytope diameter problem into a p-cycle decomposition problem (Proposition 2.1). It is a standard characterization of edges of transportation polytopes.
  • standard math The constraint matrix of PP(κ1,...,κn) is totally unimodular, so vertices correspond to integral assignments (Section 1.1).
    Standard background ensuring the combinatorial encoding of partitions as vertices.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Decomposition Bounds for Partition Polytopes and Odd-Covers." pith.science (2026). https://pith.science/paper/7FVVBOOV

@misc{pith2026250712748,
  author       = {Pith},
  title        = {Pith review of: Improved Decomposition Bounds for Partition Polytopes and Odd-Covers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7FVVBOOV}},
  note         = {Machine review of arXiv:2507.12748}
}
abstract

The assignments of a set of $m$ items into $n$ clusters of prescribed sizes $k_1,\dots,k_n$ can be encoded as the vertices of the partition polytope $\mathrm{PP}(k_1,\dots,k_n)$. We prove that, if $K = \max\{k_1,\dots,k_n\}$, then the combinatorial diameter of $\mathrm{PP}(k_1,\dots,k_n)$ is at most $\lceil 3K/2\rceil$. This improves the previously known upper bound of $2K$. A cycle (or path) odd-cover of a graph $G$ is a set of cycles (or paths) with symmetric difference $G$. We prove that every Eulerian graph $G$ with maximum degree $\Delta$ admits a cycle odd-cover and a path odd-cover, each of size at most $\lceil 3\Delta/4\rceil$. This improves the previously known upper bound of $\Delta$. The two proofs share many similarities and are both based on the proof of Akiyama, Exoo, and Harary that every graph with maximum degree 4 has linear arboricity at most 3.

Figures

Figures reproduced from arXiv: 2507.12748 by the authors.

Figure 1
Figure 1. Illustration of two (9, 4)-partitions p and p ′ and the corresponding clus￾tering difference graph CDG(p, p′ ). p is the matrix Mp = (yij ) ∈ {0, 1} nm with yij = 1 if and only if p(j) = i. The vertices of PP(κ1, . . . , κn) are exactly the incidence matrices of (m, n)-partitions with shape (κ1, . . . , κn). To describe the edges of PP(κ1, . . . , κn), we use the terminology of clustering difference graphs as in [6]… view at source ↗
Figure 2
Figure 2. shows an example of a p-cycle decomposition. x 1 1 x 1 2 x 1 3 x 1 4 x 2 1 x 2 2 x 2 3 x 2 4 x 2 5 x 3 1 x 3 2 x 3 3 (a) An Eulerian digraph G representing moves in the permutation π = (x 1 1 · · · x 1 4)(x 2 1 · · · x 2 5)(x 3 1 · · · x 3 3). Here, p is the identity map on {x 1 1, . . . , x1 4, x2 1, . . . , x2 5, x3 1, . . . , x3 3}, p ′ = pπ, and G = CDG(p, p′ ). x 1 1 x 1 2 x 1 3 x 1 4 x 2 1 x 2 2 x 2 3 x 2 4 x … view at source ↗
Figure 3
Figure 3. An odd-cover of the disjoint union of two [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: A path odd-cover and a cycle odd-cover of size 2 for a polycycle. [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: An example of a CDG consisting of edges from [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]
Figure 6
Figure 6. Figure 6: A CDG for n odd, as constructed in the proof of Lemma 3.3. additional count if x has “arrived” at its desired cluster (i.e., pi(x) = p ′ (x)). Clearly, we have s0 = 0, and after the final cyclic exchange, when every item x ∈ S has left p(x) and arrived at p ′ (x), we h…
Figure 7
Figure 7. Figure 7: A linear forest decomposition or odd-cover [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 19 canonical work pages

  1. [1]

    Covering and packing in graphs IV: Linear arboricity

    Jin Akiyama, Geoffrey Exoo, and Frank Harary. Covering and packing in graphs IV: Linear arboricity. Networks, 11(1):69–72, 1981. 1, 1.2, 2.4, 2.7, 2.4, 5

    work page 1981

  2. [2]

    Path decompositions of digraphs

    Brian R Alspach and Norman J Pullman. Path decompositions of digraphs. Bulletin of the Australian Mathematical Society, 10(3):421–427, 1974. 1

    work page 1974

  3. [3]

    University of Chicago, 1988

    L´ aszl´ o Babai and P´ eter Frankl.Linear algebra methods in combinatorics . University of Chicago, 1988. 1.2

    work page 1988

  4. [4]

    On the assignment polytope

    Michel L Balinski and Andrew Russakoff. On the assignment polytope. SIAM Review, 16(4), 1974. 1.1 26

    work page 1974

  5. [5]

    A proof of a conjecture of bondy concerning paths in weighted digraphs

    B´ ela Bollob´ as and Alex D Scott. A proof of a conjecture of bondy concerning paths in weighted digraphs. Journal of Combinatorial Theory, Series B , 66(2):283–292, 1996. 1

    work page 1996

  6. [6]

    On the diameter of partition polytopes and vertex-disjoint cycle cover

    Steffen Borgwardt. On the diameter of partition polytopes and vertex-disjoint cycle cover. Mathematical Programming, 141(1):1–20, 2013. 1.1, 1.1, 1.1, 1.1, 1.1, 1.2, 2.2, 2.2, 3.1, 3.2

    work page 2013

  7. [7]

    Path Odd-Covers of Graphs

    Steffen Borgwardt, Calum Buchanan, Eric Culver, Bryce Frederickson, Puck Rombach, and Youngho Yoo. Path odd-covers of graphs. arXiv preprint arXiv:2306.06487 , 2023. 1.2, 1.2, 1.2, 2.2, 2.2, 4.2, 4.2, 4.10, 4.11, 4.12

    work page Pith review arXiv 2023

  8. [8]

    The diameters of network-flow polytopes satisfy the Hirsch conjecture

    Steffen Borgwardt, Jes´ us A De Loera, and Elisabeth Finhold. The diameters of network-flow polytopes satisfy the Hirsch conjecture. Mathematical Programming, 171(1-2):283–309, 2018. 1.1

    work page 2018

Show all 21 references
  1. [9]

    Constructing Clustering Transformations

    Steffen Borgwardt and Charles Viss. Constructing Clustering Transformations. SIAM Journal on Discrete Mathematics, 35(1):152–178, 2021. 1.2

    2021

  2. [10]

    On odd covers of cliques and disjoint unions

    Calum Buchanan, Alexander Clifton, Eric Culver, P´ eter Frankl, Jiaxi Nie, Kenta Ozeki, Puck Rombach, and Mei Yin. On odd covers of cliques and disjoint unions. arXiv preprint arXiv:2408.08598 , 2024. 1.2

    2024 arXiv

  3. [11]

    Odd covers of graphs

    Calum Buchanan, Alexander Clifton, Eric Culver, Jiaxi Nie, Jason O’Neill, Puck Rombach, and Mei Yin. Odd covers of graphs. Journal of Graph Theory , doi.org/10.1002/jgt.22970, 2023. 1.2

    2023 doi

  4. [12]

    On the coverings of graphs

    Fan RK Chung. On the coverings of graphs. Discrete Mathematics, 30(2):89–93, 1980. 1.2

    1980

  5. [13]

    On some of my conjectures in number theory and combinatorics

    Paul Erd˝ os. On some of my conjectures in number theory and combinatorics. In Proceedings of the fourteenth Southeastern conference on combinatorics, graph theory and computing , volume 39, pages 3–19, 1983. 1, 1.2

    1983

  6. [14]

    Covers of Eulerian graphs

    Genghua Fan. Covers of Eulerian graphs. Journal of Combinatorial Theory, Series B , 89(2):173–187,

  7. [15]

    On the addressing problem for loop switching

    Ronald L Graham and Henry O Pollak. On the addressing problem for loop switching. The Bell System Technical Journal, 50(8):2495–2519, 1971. 1.2

    1971

  8. [16]

    On embedding graphs in squashed cubes

    Ronald L Graham and Henry O Pollak. On embedding graphs in squashed cubes. Graph theory and applications, 303:99–110, 1972. 1.2

    1972

  9. [17]

    Facets and vertices of transportation polyhedra

    Victor Klee and Christoph Witzgall. Facets and vertices of transportation polyhedra. In G. B. Dantzig and A. F. Veinott, editors, Mathematics of the decision sciences , volume 1, pages 257–282. American Mathematical Society, Providence, RI, 1968. 1.1

    1968

  10. [18]

    Odd covers of complete graphs and hypergraphs

    Imre Leader and Ta Sheng Tan. Odd covers of complete graphs and hypergraphs. arXiv preprint arXiv:2408.05053, 2024. 1.2

    2024 arXiv

  11. [19]

    On covering of graphs

    L´ aszl´ o Lov´ asz. On covering of graphs. In Theory of Graphs (Proc. Colloq., Tihany, 1966) , pages 231–236. Academic Press New York, 1968. 1, 1.2

    1966

  12. [20]

    Linear arboricity of digraphs

    A Nakayama and Bernard P´ eroche. Linear arboricity of digraphs. Networks, 17(1):39–53, 1987. 1

    1987

  13. [21]

    Die Theorie der regul¨ aren Graphs

    Julius Petersen. Die Theorie der regul¨ aren Graphs. Acta Mathematica, 15(1):193–220, 1891. 2.2 27

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.