Metraipolis › archive › dc_8bd88f89978f
On several judicious partitioning problems of graphs and hypergraphs — arXiv:2610.19800
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.19800
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T21:52:41.400Z
- SHA-256 of the archived text
b1145df69d3ad88de66f7dbefa161e460e820631b47e6067320db9f50df3e20a- Stable URL of this page
https://metraipolis.com/documento/dc_8bd88f89978f
How to cite
On several judicious partitioning problems of graphs and hypergraphs — arXiv:2610.19800 — arXiv (en), https://arxiv.org/abs/2610.19800 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8bd88f89978f (Metraipolis archive dc_8bd88f89978f, sha256 b1145df69d3ad88de66f7dbefa161e460e820631b47e6067320db9f50df3e20a)
BibTeX
@misc{dc8bd88f89978f,
title = {On several judicious partitioning problems of graphs and hypergraphs — arXiv:2610.19800},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.19800},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8bd88f89978f; sha256 b1145df69d3ad88de66f7dbefa161e460e820631b47e6067320db9f50df3e20a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.19800. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Judicious partition problems ask for vertex partitions of graphs or hypergraphs that optimize several quantities simultaneously. In this paper, we investigate judicious partitions of graphs and hypergraphs in which each class meets many edges and establish the following results. (1) Every hypergraph with nonnegative edge weights and all edges of size at most $2$ has a bipartition in which each vertex class meets edges of total weight at least $(w_1-\Delta_1)/2+2w_2/3$, where $w_i$ is the total weight of the edges of size $i$, and $\Delta_1$ is the maximum weight of an edge of size $1$. (2) Every hypergraph with all edges of size at most $3$ has a bipartition in which each vertex class meets at least $m_1/2+3m_2/4+7m_3/8+o(m_1+m_2+m_3)$ edges, where $m_i$ is the number of edges of size $i$. (3) For any integer $k\ge4$, every graph with $m\ge2(k-1)(k-2)$ edges has a partition into $k$ classes, each meeting at least $2m/(2k-1)$ edges. Both the coefficient of $m$ and the edge threshold are best possible. (4) For all sufficiently large $m$, every $4$-uniform hypergraph with $m$ edges has a partition into four classes, each meeting at least $4m/7$ edges. The first three statements are conjectures of Bollobás and Scott, and the last is a conjecture of Bollobás and Thomason on 4-uniform hypergraphs. All of the above results are best possible. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno). Categorie arXiv: Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2610.19800 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-15T21:37:14.426Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).