Enumerating Minimal Balanced Collections

Abstract

In this note, we explore the combinatorics of balanced collections. A collection of subsets of the set $[n]=\{1,\dots ,n\}$ is called \emph{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 \emph{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=2^{n^2-n+1}(1+o(1))/n!$ as $n\to \infty$. We discuss applications of this result to fractional matchings in hypergraphs and to resonance arrangement