For a given $k,n$ such that $0<k \leq n/2$, is there a number $N_{n,k}$, such that if one has $N$ different $k$-dimensional subspaces $V_1, V_2,...,V_N$ in $\mathbb{R}^n$ satisfying:

1) $\bigcap_{i = 1}^N V_i = \{0\}$

2) $dim (\bigoplus_{i = 1}^N V_i) \geq 2k$.

Then there are at least two subspaces $V_i, V_j$ such that $V_i \cap V_j = \{0\}$.

For example if $k =2$ and $n = 4$, then $N_{n,k}$ is $\frac{1}{2} {4 \choose 2} + 1$, my guess was that for $n = 2k$, the maximal number would be $\frac{1}{2} {2k \choose k} + 1$ just by considering canonical subspaces for the canonical base of $\mathbb{R}^{2k}$.

I'm not very interested in the actual number $N_{n,k}$ but in its existence actually.

Related results are a theorem of Erdos-Ko-Rado that states that in a set of $n$ elements there are at most $n-1 \choose k-1$ subsets of $k$ elements such that all of them have non-trivial intersection. Related results where proved for vector spaces over finite fields by Hsieh, Katona and others but I'm not able to find whether this statement or something similar holds.


The number $N_{6,3}$ does not exist: let $V_1=\mathrm{span}(e_1,e_2,e_3)$, $V_2=\mathrm{span}(e_3,e_4,e_5)$, $V_3=\mathrm{span}(e_1,e_6,e_5)$, and $V_j=\mathrm{span}(e_1,e_3, e_4+j\cdot e_5)$ for $j\ge 4$.

  • $\begingroup$ Thanks a lot @Jan, that does answer my question. I feel a bit disappointed as I am in need of something of this kind to be true. I'll see if I can find a useful modification of the question. $\endgroup$
    – shurtados
    Dec 1 '17 at 1:13
  • $\begingroup$ You could extend this family $V_0=\mathrm{span}(e_1,e_3,e_5)$ along with all dimension $3$ subspaces which intersect $V$ in a subspace of dimension at least $2.$ $\endgroup$ Dec 1 '17 at 10:41

Here is a comment because you say that you want something of this kind to be true. You are not really generalizing Erdos-Ko-Rado because of your condition that the intersection be as trivial as possible. I think maybe you should change your your second condition to something like

2) There is no subspace $W$ of dimension $2k-1$ so that the subspaces $V_i \cap W$ are pairwise intersecting. (It might be that dimension $k+2$ is a strong enough condition.)

I feel that the set version (to be given shortly) should be known and that the answer is that for fixed $k$ there is an absolute bound $N_k$ so that $N_{n,k}=N_k$ for all large enough $n.$ However I've never found it. I'll define $M_{n,k}$ to be your $N_{n,k}-1$, the maximum size for a family that is pairwise intersecting.

So, in an $n$ element set what is the largest size $M_{n,k}$ (if there is one) of a family of $k$ element sets $V_1,V_2,\cdots$ such that

1) Their intersection is empty.

2) There is no set $W$ of size $2k-1$ such that the sets $V _i \cap W$ are pairwise intersecting.

3) Every pair from the family has non-empty intersection.

Without a condition 2:

  • For $k=2$ it is $3$ independent of $n.$
  • For $k=3$ you can do the set version of what @Jan did, $1+3(n-3)$ triples $V_0=\{a,b,c\}$ along with all triples intersecting it in two points. But my condition $2)$ rules that out. For that condition there better be at least $6$ points in the union. One can get $M_{n,3} \ge 10$ by taking a subset $S$ of size $6$ and for each of the $10$ pairs $T,S-T$ of $3$ element subsets taking one. That assures no disjoint pair and the sets can be chosen to satisfy the other conditions. Obviously there are only finitely many configurations up to isomorphism. Nicest is an orbit of $A_5$ (the weird embedding in $S_6$) but as long as you include four sets such as $abc,ade,bdf,cef$ you are already OK (the $\binom42=6$ intersections give all the points). That is maximal in that you can't add any $3$ element sets. I think the only other maximal family in that sense is the $7$ lines of a Fano plane. So I would conjecture that $M_{3,n}=10$ for all $n \ge 6$ and the is achieved by a family with $|\cup V_i|=6.$ I might even have proved those things (many years ago) for $k=3$ but I don't know anything about $k \gt 3.$

I strongly suspect that for larger $k$ a similar result holds and suspect the same is true in the vector version.

Set conjecture: For families satisfying the conditions 1,2,3 above there is an upper bound on the size of the union and (hence) only a finite number of configurations up to isomorphism. The upper bound might be $k^2-k+1$ when $k$ is a prime power. $M_{2k,k}=\frac12\binom{2k}{k}$ and I'd guess that is $M_{n,k}$ for all $n$ with a union of size $2k.$

I'd really be interested to find out if this a known result (or false, or conjectured.)


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.