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 \geq 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 \geq 2$, almost all $k$-polymatroids are (i) connected, (ii) proper, and (iii) not linearly representable over any field.

Disclosure

“any field in the sense of [1]. Acknowledgments SI was supported by a KIAS Individual Grant (AP109501) at the Korea Institute for Advanced Study. DK was partially supported by an AMS–Simons Travel Grant. AI Declaration The authors used Gemini and GPT to develop the initial idea of the proof of Theorem 1.1. The full proof of Theorem 1.1 was written and verified by the authors. In the rest of the paper, LLM-based tools are only used to polish the writing. References [1] Matthe”

PDF page 10

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-22T02:23:52.192532Z

Structural counts