7
$\begingroup$

I asked this question on Mathematics Stackexchange, but got no answer.

Let $K$ be a field and $n$ a positive integer. To a finite dimensional $K$-vector space $V$, equipped with a family $V_1,\dots,V_n$ of subspaces, we attach the map $d:\mathcal P(\{1,\dots,n\})\to\mathbb N$ defined by $$ d(S)=\dim\left(\bigcap_{s\in S}V_s\right). $$ [Here $\mathcal P(\{1,\dots,n\})$ denotes the set of subsets of $\{1,\dots,n\}$.] Then we have

$(1)\quad S\subset T\implies d(S)\ge d(T)$,

$(2)\quad d(S\cap T)\ge d(S)+d(T)-d(S\cup T)$

for all $S,T\in\mathcal P(\{1,\dots,n\})$. [Here $S\subset T$ means that each element of $S$ belongs to $T$.]

Conversely, given $d:\mathcal P(\{1,\dots,n\})\to\mathbb N$ satisfying $(1)$ and $(2)$, is there a family $(V,V_1,\dots,V_n)$ as above inducing $d$ in the way just described?

The answer is No in general, a counterexample being given as follows: $K=\mathbb F_2, n=4$, $$ d(\varnothing)=2=\dim V,\quad d(\{i\})=1=\dim V_i, $$ and $d(S)=0$ if $S$ has at least two elements. [We use the fact that there are only three lines through the origin in $\mathbb F_2^2$.] There is an obvious analog for any finite field.

In view of the above observations, it seems natural to ask:

Assume that our field $K$ is infinite, and that $d:\mathcal P(\{1,\dots,n\})\to\mathbb N$ satisfies $(1)$ and $(2)$. Is there a family $(V,V_1,\dots,V_n)$ as above such that $$ d(S)=\dim\left(\bigcap_{s\in S}V_s\right) $$ for all $S\ ?$

$\endgroup$

1 Answer 1

9
$\begingroup$

I find this easier to think about if we dualize everything: replace $d(S)$ with $\dim V - d(S)$ and each subspace with its annihilator in $V'$. Recall that the annihilator of a sum is the intersection of the annihilators. Thus your question is the following:

Assume $d:\mathcal{P}(\{1,\dots,n\}) \to \mathbb{N}$ is increasing and submodular (this is just the cool name for the condition $d(S \cup T) + d(S\cap T) \leq d(S) + d(T)$) and satisfies $d(\emptyset)=0$ and $d(\{1,\dots,n\}) \leq \dim V$. Then does there exists a collection of subspaces $V_i$ of $V$ such that $\dim \sum_{i \in S} V_i = d(S)$ for each $S \subset \{1,\dots,n\}$?

If we further assume that $d(\{x\}) \leq 1$ for each $x$ then this is exactly one of the equivalent definitions of a matroid, and your question is whether every matroid is linear. Apparently the answer is no.

$\endgroup$
1
  • 7
    $\begingroup$ And the keyword to search for is "representable polymatroid". There are some additional inequalities beyond submodularity e.g. in this paper. For example, any four subspaces must satisfy the Ingleton inequality. $\endgroup$ Commented Jun 25, 2018 at 7:54

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.