Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?

share|improve this question
    
Minor correction. A matroid is binary if and only if it does not contain a 4-point line as a minor. Note that a matroid may have a 4-point line as a minor, but not as a restriction, e.g. $U_{3,5}$. –  Tony Huynh Sep 2 '10 at 22:54
    
Thanks, I have corrected the question. –  Andreas Thom Sep 3 '10 at 5:10
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.