5 - Judicious partitions and related problems

Summary

Abstract

Many classical partitioning problems in combinatorics ask for a single quantity to be maximized or minimized over a set of partitions of a combinatorial object. For instance, Max Cut asks for the largest bipartite subgraph of a graph G, while Min Bisection asks for the minimum size of a cut into two equal pieces.

In judicious partitioning problems, we seek to maximize or minimize a number of quantities simultaneously. For instance, given a graph G with m edges, we can ask for the smallest f(m) such that G must have a bipartition in which each vertex class contains at most f(m) edges.

In this survey, we discuss recent extremal results on a variety of questions concerning judicious partitions, and related problems such as Max Cut.

Introduction

A wide variety of combinatorial optimization problems ask for an “optimal” partition of the vertex set of a graph or hypergraph. A good example is the Max Cut problem: given a graph G, what is the maximum of e(V₁, V₂) over partitions V(G) = V₁ ∪ V₂, where e(V₁, V₂) is the number of edges between V₁ and V₂? Similarly, Min Bisection asks for the minimum of e(V₁, V₂) over partitions V(G) = V₁ ∪ V₂ with |V₁| ≤ |V₂| ≤ |V₁| + 1 (there are k-partite versions Max k-Cut and Min k-Section of both problems).

Both of these problems involve maximizing or minimizing a single quantity over graphs from a certain class.