PreprintCC BY-NC-SA 4.0arXiv
On the enumeration of polymatroids
Abstract
Let pk(n) be the number of k-polymatroids on [n]. We show that for every fixed k ≥ 1, we have ⌊ k/2 ⌋ · binomn⌊ n/2 ⌋ · (1+o(1)) ≤ log2 pk(n) ≤ k · binomn⌊ n/2 ⌋ · (1+o(1)). We also show that for k ≥ 2, almost all k-polymatroids are (i) connected, (ii) proper, and (iii) not linearly representable over any field.
Related
- Return-Growth Sequences: Euler Enumeration and Pattern Avoidance
- Enumeration of orientably-regular maps with automorphism group PGam(2,2p) for prime p
- Enumeration of Upper Triangular Symplectic Renner Monoids
- Enumeration of small vertex-transitive directed strongly regular graphs
- Weighted lattice point enumeration in lecture hall order polytopes
BibTeX
@misc{im2026enumeration,
title = {{On the enumeration of polymatroids}},
author = {Seonghyuk Im and Donggyu Kim},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.18225},
eprint = {2608.18225},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.18225},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - On the enumeration of polymatroids
AU - Seonghyuk Im
AU - Donggyu Kim
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.18225
UR - https://arxiv.org/abs/2608.18225
AB - Let p_k(n) be the number of k-polymatroids on [n]. We show that for every fixed k ≥ 1, we have ⌊ k/2 ⌋ · binomn⌊ n/2 ⌋ · (1+o(1)) ≤ log_2 p_k(n) ≤ k · binomn⌊ n/2 ⌋ · (1+o(1)). We also show that for k ≥ 2, almost all k-polymatroids are (i) connected, (ii) proper, and (iii) not linearly representable over any field.
ER -