Enumerating Minimal Balanced Collections

2025/11/24 by Mikhail V. Bludov, Nikolai K. Zuev, Bludov, Mikhail V. +1
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Combinatorial Mathematics #Computational Geometry and Mesh Generation

paper · pdf · doi:10.48550/arxiv.2511.19323

Abstract

In this note, we explore the combinatorics of balanced collections. A collection of subsets of the set [n] = \1, …, n\ is called balanced if the relative interior of the convex hull of the corresponding characteristic vectors intersects the main diagonal of the n-dimensional cube at a point other than the origin, and it is called minimal if it contains no proper balanced subcollections. We determine the asymptotic number of minimal balanced collections. Specifically, if B_n denotes their total number, then B_n=\frac2^n2-n+1n!(1+o(1)) \qquadas n→∞.

Related

• Maximal unbalanced families
• Note on the number of balanced independent sets in the Hamming cube
• The balancing number and list balancing number of some graph classes
• On Balanced Colorings of the n-Cube
• On a counting theorem for weakly admissible lattices