On the enumeration of polymatroids

Abstract

Let $p_k(n)$ be the number of $k$-polymatroids on $[n]$. We show that for every fixed $k\ge 1$, we have \[ \left\lfloor \frac{k}{2} \right\rfloor \cdot \binom{n}{\lfloor n/2 \rfloor} \cdot (1+o(1)) \le \log_2 p_k(n) \le k \cdot \binom{n}{\lfloor n/2 \rfloor} \cdot (1+o(1)). \] We also show that for $k\ge 2$, almost all $k$-polymatroids are (i) connected, (ii) proper, and (iii) not linearly representable over any field.

11 pages