Density-Sensitive Total Weight for Partite Decompositions of Uniform Hypergraphs
Vasek Rozhon·Adrian Zámečník
Abstract
For a complete d-partite d-uniform hypergraph K(A1, ..., Ad), define its weight as the sum of |Ai|. Consider covers and edge-disjoint exact partitions of an n-vertex d-uniform hypergraph into such pieces. For every fixed d ≥ 3 and 0 < ε < 1, the worst-case minimum total weight among hypergraphs with m ≤ (1 − ε) C(n,d) edges is Θ_{d,ε}(m min(1, log(1/γ)/log n)), where γ = m / C(n,d). The formula is the same for covers and exact partitions. The lower bound uses an exact-density random hypergraph; the upper bound repeatedly extracts density-sensitive balanced boxes and then partitions the sparse remainder. Espuña's extraction algorithm makes the construction deterministic and polynomial-time. Cone examples show that the average total-weight scale W/n need not control the maximum number of pieces through one vertex. Complete and near-complete endpoint bounds are also given, while the sharp transition as γ → 1 remains open.Discussion
Sign in to join the discussion.