Let $n$ be a positive integer. For each subset $S$ of $\{1,\dots,n\}$ let $d_S$ be a nonnegative integer. Assume that the $(d_S)$ satisfy: $$ S\subset T\implies d_S\ge d_T, $$ $$ d_{S\cap T}\ge d_S+d_T-d_{S\cup T} $$ for all $S,T\subset\{1,\dots,n\}$. [In this post $X\subset Y$ denotes what some people designate by $X\subseteq Y$.]

Is there a tuple $(V,V_1,\dots,V_n)$, such that $V$ is a finite dimensional $\mathbb Q$-vector space $V$ and the $V_i$ are sub-vector spaces of $V$, satisfying $$ \dim\left(\bigcap_{s\in S}V_s\right)=d_S $$ for all $S\subset\{1,\dots,n\}\ ?$

EDIT 1. The conditions $$ S\subset T\implies d_S\ge d_T, $$ $$ d_{S\cap T}\ge d_S+d_T-d_{S\cup T} $$ for all $S,T\subset\{1,\dots,n\}$ stated above are necessary. The first one follows from the fact that the dimension of a subspace can't exceed the dimension of the ambient space, the second one follows from the first one coupled to the equality

$(\star)\quad\dim(U+W)=\dim U+\dim W-\dim(U\cap W)$

for finite dimensional subspaces $U$ and $W$.

There is an similar question for finite sets, with cardinalities instead of dimensions; that is, one can ask which families of nonnegative integers indexed by subsets of $\{1,\dots,n\}$ come (in the obvious sense) from a tuple $(V,V_1,\dots,V_n)$ of finite sets. In this setting, we still have the trivial obstruction that the cardinality of a subset can't exceed the cardinality of the ambient set, but there are other obstructions, given by the inclusion-exclusion principle for $k$ finite subsets, for all $k$ varying from $2$ to $n$. In the case of finite dimensional vector spaces, however, the inclusion-exclusion principle holds for $k=2$ (see $(\star)$), but not for $k\ge3$: see Sebastien Palcoux's posts in this thread (see also the references therein). It seems that (for dimensional vector spaces) no obstructions other that the trivial one and the one coming from $(\star)$ have been found so far. This is perhaps because they don't exist, but, for the time being, it seems that the existence of subtler obstructions can't be ruled out.

The ground field has been chosen to be $\mathbb Q$, but this was only for the sake of concreteness. I'd be very interested in any result involving another field.

EDIT 2. In fact, if the ground field is finite, there are obvious obstructions coming from the fact that the cardinality of a union of subspaces can't exceed the cardinality the ambient space. To avoid this kind of complications, let's assume that ground field is infinite.

EDIT 3. Here is a proof of the existence of $V$ and the $V_i$ in the case $n=3$ (assuming that the ground field is infinite).

Let $K$ be the ground field, which is assumed to be infinite. For each set $Z$ let $|Z|$ be the cardinality of $Z$, and let $KZ$ be the free vector space over $Z$.

If there are sets $Z,Z_1,Z_2,Z_3$ such that $$ \left|\bigcap_{i\in S}Z_i\right|=d_S $$ for all $S\subset\{1,2,3\}$, we solve our problem by applying the functor $X\mapsto KX$.

So we can assume from now on that no such sets exist.

There are still sets $Z_1,Z_2,Z_3$ such that $$ \left|\bigcap_{i\in S}Z_i\right|=d_S $$ for all nonempty subset $S$ of $\{1,2,3\}$. We define $Z$ by $Z:=Z_1\cup Z_2\cup Z_3$. Setting $r:=|Z|-d_\varnothing$, we get $$ 1\le r\le|Z\setminus(Z_i\cup Z_j)| $$ for all $i,j$. As $K$ is infinite, there is an $r$ dimensional subspace $W$ in $KZ$ such that $W\cap(K\,(Z_i\cup Z_j))=0$ for all $i,j$. Let $\pi:KZ\to(KZ)/W$ be the canonical projection. Then it suffices to set $$ V:=(KZ)/W,\quad V_i:=\pi(KZ_i). $$


Sean Eberhard answered the question on MathOverflow. See a also Tobias Fritz's very interesting comment to Sean Eberhard's answer.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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