On several judicious partitioning problems of graphs and hypergraphs
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-Δ_1)/2+2w_2/3$, where $w_i$ is the total weight of the edges of size $i$, and $Δ_1$ is the maximum weight of an edge of size $1$. (2) Every…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.19800
curl -X POST /api/v1/records/arxiv/2610.19800/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.19800/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'