Return to Answer

Here's a construction due to Stefan van Zwam.

Let $U_{2,4}$ be a 4-point line with ground set $[4]$, and rank function $r$. For each $A \subset [4]$, let $\chi(A)$ be 1, if $1 \in A$, and 0 if $1 \notin A$. For each $k \in \mathbb{N}$, let $S_k$ be the polymatroid with ground set $[4]$ and rank function $r+k\chi$.

Lemma. $S_k$ is not representable over $\mathbb{F}_2$, for every $k$.

Proof. Let $(V_i : i \in [4])$ be a representation of $S_k$ over $\mathbb{F}_2$. Choose a basis $B_i$ for each $V_i$. Since {1} has rank $k+1$ and {1,2} has rank $k+2$, we may assume that $B_1$ consists of the first $k+1$ standard basis vectors in $\mathbb{F}_2^{k+2}$ and that $B_2=\epsilon_{k+2}$. Now, since {1,3} and {1,4} both have rank $k+2$, it follows that the last coordinate of $B_3$ and $B_4$ must be 1. In particular, $B_2 + B_3 +B_4 \neq 0$. Also, since every two element subset of {2,3,4} has rank 2, it follows that $B_2, B_3$ and $B_4$ are distinct. But now {2,3,4} must have rank 3 in $S_k$, a contradiction. $\square$

Moreover, it is easy to check that every minor of $S_k$ is representable over $\mathbb{F}_2$, where minors of polymatroids are defined in the obvious way. Therefore, the set of binary polymatroids has an infinite set of excluded minors.

Here's a construction due to Stefan van Zwam.

Let $U_{2,4}$ be a 4-point line with ground set $[4]$, and rank function $r$. For each $A \subset [4]$, let $\chi(A)$ be 1, if $1 \in A$, and 0 if $1 \notin A$. For each $k \in \mathbb{N}$, let $S_k$ be the polymatroid with ground set $[4]$ and rank function $r+k\chi$.

Lemma. $S_k$ is not representable over $\mathbb{F}_2$, for every $k$.

Proof. Let $(V_i : i \in [4])$ be a representation of $S_k$ over $\mathbb{F}_2$. Choose a basis $B_i$ for each $V_i$. Since {1} has rank $k+1$ and {1,2,3,4} has rank $k+2$, we may assume that $B_1$ consists of the first $k+1$ standard basis vectors in $\mathbb{F}_2^{k+2}$. Now, since {1,2}, {1,3}, and {1,4} all have rank $k+2$, it follows that $B_2, B_3$, and $B_4$ all must have last coordinate equal to 1. In particular, $B_2 + B_3 +B_4 \neq 0$. Also, since every two element subset of {2,3,4} has rank 2, it follows that $B_2, B_3$ and $B_4$ are distinct. But now {2,3,4} must have rank 3 in $S_k$, a contradiction. $\square$

Moreover, it is easy to check that every minor of $S_k$ is representable over $\mathbb{F}_2$, where minors of polymatroids are defined in the obvious way. Therefore, the set of binary polymatroids has an infinite set of excluded minors.

Here's a construction due to Stefan van Zwam.

Let $U_{2,4}$ be a 4-point line with ground set $[4]$, and rank function $r$. For each $A \subset [4]$, let $\chi(A)$ be 1, if $1 \in A$, and 0 if $1 \notin A$. Let $S_k$ be the polymatroid with ground set $[4]$ and rank function $r+k\chi$.

Lemma. $S_k$ is not representable over $\mathbb{F}_2$, for every $k$.

Proof. Let $(V_i : i \in [4])$ be a representation of $S_k$ over $\mathbb{F}_2$. Choose a basis $B_i$ for each $V_i$. Since {1} has rank $k+1$ and {1,2} has rank $k+2$, we may assume that $B_1$ consists of the first $k+1$ standard basis vectors in $\mathbb{F}_2^{k+2}$ and that $B_2=\epsilon_{k+2}$. Now, since {1,3} and {1,4} both have rank $k+2$, it follows that the last coordinate of $B_3$ and $B_4$ must be 1. In particular, $B_2 + B_3 +B_4 \neq 0$. Also, since every two element subset of {2,3,4} has rank 2, it follows that $B_2, B_3$ and $B_4$ are distinct. But now {2,3,4} must have rank 3 in $S_k$, a contradiction. $\square$

Moreover, it is easy to check that every minor of $S_k$ is representable over $\mathbb{F}_2$, where minors of polymatroids are defined in the obvious way. Therefore, the set of binary polymatroids has an infinite set of excluded minors.

Here's a construction due to Stefan van Zwam.

Let $U_{2,4}$ be a 4-point line with ground set $[4]$, and rank function $r$. For each $A \subset [4]$, let $\chi(A)$ be 1, if $1 \in A$, and 0 if $1 \notin A$. For each $k \in \mathbb{N}$, let $S_k$ be the polymatroid with ground set $[4]$ and rank function $r+k\chi$.

Lemma. $S_k$ is not representable over $\mathbb{F}_2$, for every $k$.

Proof. Let $(V_i : i \in [4])$ be a representation of $S_k$ over $\mathbb{F}_2$. Choose a basis $B_i$ for each $V_i$. Since {1} has rank $k+1$ and {1,2} has rank $k+2$, we may assume that $B_1$ consists of the first $k+1$ standard basis vectors in $\mathbb{F}_2^{k+2}$ and that $B_2=\epsilon_{k+2}$. Now, since {1,3} and {1,4} both have rank $k+2$, it follows that the last coordinate of $B_3$ and $B_4$ must be 1. In particular, $B_2 + B_3 +B_4 \neq 0$. Also, since every two element subset of {2,3,4} has rank 2, it follows that $B_2, B_3$ and $B_4$ are distinct. But now {2,3,4} must have rank 3 in $S_k$, a contradiction. $\square$

Moreover, it is easy to check that every minor of $S_k$ is representable over $\mathbb{F}_2$, where minors of polymatroids are defined in the obvious way. Therefore, the set of binary polymatroids has an infinite set of excluded minors.

Here's a construction due to Stefan van Zwam.

Let $U_{2,4}$ be a 4-point line with ground set $[4]$, and rank function $r$. Let $\chi_1$ be the characteristic function of {1}. Let $S_k$ be the polymatroid with ground set $[4]$ and rank function $r+k\chi_1$.

Lemma. $S_k$ is not representable over $\mathbb{F}_2$, for every $k$.

Proof. Let $(V_i : i \in [4])$ be a representation of $S_k$ over $\mathbb{F}_2$. Choose a basis $B_i$ for each $V_i$. Since {1} has rank $k+1$ and {1,2} has rank $k+2$, we may assume that $B_1$ consists of the first $k+1$ standard basis vectors in $\mathbb{F}_2^{k+2}$ and that $B_2=\epsilon_{k+2}$. Now, since {1,3} and {1,4} both have rank $k+2$, it follows that the last coordinate of $B_3$ and $B_4$ must be 1. In particular, $B_1 + B_2 +B_3 \neq 0$. Also, since every two element subset of {2,3,4} has rank 2, it follows that $B_1, B_2$ and $B_3$ are distinct. But, now {2,3,4} must have rank 3 in $S_k$, a contradiction. $\square$

Moreover, it is easy to check that every minor of $S_k$ is representable over $\mathbb{F}_2$, where minors of polymatroids are defined in the obvious way. Therefore, the set of binary polymatroids has an infinite set of excluded minors.

Here's a construction due to Stefan van Zwam.

Let $U_{2,4}$ be a 4-point line with ground set $[4]$, and rank function $r$. For each $A \subset [4]$, let $\chi(A)$ be 1, if $1 \in A$, and 0 if $1 \notin A$. Let $S_k$ be the polymatroid with ground set $[4]$ and rank function $r+k\chi$.

Lemma. $S_k$ is not representable over $\mathbb{F}_2$, for every $k$.

Proof. Let $(V_i : i \in [4])$ be a representation of $S_k$ over $\mathbb{F}_2$. Choose a basis $B_i$ for each $V_i$. Since {1} has rank $k+1$ and {1,2} has rank $k+2$, we may assume that $B_1$ consists of the first $k+1$ standard basis vectors in $\mathbb{F}_2^{k+2}$ and that $B_2=\epsilon_{k+2}$. Now, since {1,3} and {1,4} both have rank $k+2$, it follows that the last coordinate of $B_3$ and $B_4$ must be 1. In particular, $B_2 + B_3 +B_4 \neq 0$. Also, since every two element subset of {2,3,4} has rank 2, it follows that $B_2, B_3$ and $B_4$ are distinct. But now {2,3,4} must have rank 3 in $S_k$, a contradiction. $\square$

Moreover, it is easy to check that every minor of $S_k$ is representable over $\mathbb{F}_2$, where minors of polymatroids are defined in the obvious way. Therefore, the set of binary polymatroids has an infinite set of excluded minors.