Menu
This paper develops the polyhedral approach to integer partitions. We consider the set of partitions of an integer \( n \) as a polytope \( P_n \subset \mathbb{R}^n \). Vertices of \( P_n \) form the class of partitions that provide the first basis for the whole set of partitions of \( n \). Moreover, we show that there exists a subclass of vertices, from which all others can be generated with the use of two combinatorial operations. The calculation demonstrates a considerable decrease in the cardinality of these classes of basic partitions as \( n \) grows. We focus on the vertex enumeration problem for \( P_n \). We prove that vertices of all partition polytopes form a partition ideal of the Andrews partition lattice. This allows us to construct vertices of \( P_n \) by a lifting method, which requires examining only certain partitions of \( n \). A criterion of whether a given partition is a convex combination of two others connects vertices with knapsack partitions, sum-free sets, Sidon sets, and Sidon multisets introduced in the paper. All but a few non-vertices for small \( n \)’s were recognized with its help. We also prove several easy-to-check necessary conditions for a partition to be a vertex.