pipette
ENEnglish

On several judicious partitioning problems of graphs and hypergraphs

Siwei Lin, Qinghou Zeng

Preprint

En palabras de los autores

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 has a bipartition in which each vertex class meets edges of total weight at least , where is the total weight of the edges of size , and is the maximum weight of an edge of size . (2) Every hypergraph with all edges of size at most has a bipartition in which each vertex class meets at least edges, where is the number of edges of size . (3) For any integer , every graph with edges has a partition into classes, each meeting at least edges. Both the coefficient of and the edge threshold are best possible. (4) For all sufficiently large , every -uniform hypergraph with edges has a partition into four classes, each meeting at least edges. The first three statements are conjectures of Bollob\'as and Scott, and the last is a conjecture of Bollob\'as and Thomason on 4-uniform hypergraphs. All of the above results are best possible.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.