Improved Decomposition Bounds for Partition Polytopes and Odd-Covers
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916867816292352 |
|---|---|
| author | Borgwardt, Steffen Dvořák, Zdeněk Frederickson, Bryce Nix, Abigail Yoo, Youngho |
| author_facet | Borgwardt, Steffen Dvořák, Zdeněk Frederickson, Bryce Nix, Abigail Yoo, Youngho |
| contents | 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 $Δ$ admits a cycle odd-cover and a path odd-cover, each of size at most $\lceil 3Δ/4\rceil$. This improves the previously known upper bound of $Δ$.
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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_12748 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Decomposition Bounds for Partition Polytopes and Odd-Covers Borgwardt, Steffen Dvořák, Zdeněk Frederickson, Bryce Nix, Abigail Yoo, Youngho Combinatorics 05C38, 05C62, 05C70, 52B05 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 $Δ$ admits a cycle odd-cover and a path odd-cover, each of size at most $\lceil 3Δ/4\rceil$. This improves the previously known upper bound of $Δ$. 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. |
| title | Improved Decomposition Bounds for Partition Polytopes and Odd-Covers |
| topic | Combinatorics 05C38, 05C62, 05C70, 52B05 |
| url | https://arxiv.org/abs/2507.12748 |