A *polymatroid* is a finite set $X$ and a rank function $d : P(X) \to {\mathbb N}$ such that


1) $d(\varnothing)=0$,


2) $A \subset B$ implies $d(A) \leq d(B)$, and


3) $d(A \cap B) + d(A \cup B) \leq d(A) + d(B)$ for all $A,B \in P(X)$.


A polymatroid is said to be *representable* over $GF(2)$ (the field with two elements), if there exists a collection of subvectorspaces $\lbrace V\_x \mid x \in X \rbrace$ of $GF(2)^{\oplus d(X)}$, such that


$$d(A) = \dim\_{GF(2)} \bigvee\_{x \in A} V\_x, \quad \forall A \in P(X).$$


(It is clear that any function $d$, which is defined this way is indeed a polymatroid.)


A polymatroid is called *matroid* if $d(\lbrace x\rbrace)=1$ for all $x \in X$.
Tutte proved that a matroid is representable over $GF(2)$ if and only if the matroid $U\_{2,4}$ does not appear as a minor. Here, $U\_{2,4}$ is the matroid formed by four points that lie on one line, i.e. the underlying set is $\lbrace x\_1,\dots,x\_4 \rbrace$ and $d(\lbrace x\_i,x\_j\rbrace) = 2$ for $i \neq j$ and $d(\lbrace x\_1,\dots,x\_4\rbrace)=2$. (The necessity of this condition is obvious, since $GF(2)^{\oplus 2}$ has only $3$ non-zero elements.)



> 
> **Question:** Is there any useful characterization of the representability of a polymatroid over $GF(2)$ ? What is known about this question ?
> 
> 
> 



Representability of polymatroids over $GF(2)$
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. 


