10
$\begingroup$

Let $V$ be a vector space over a field with $5$ elements, $A,B \subseteq V$ independent subsets. Must there be a subspace of $V$ of codimension 1 disjoint from $A \cup B$?

$\endgroup$
4
  • $\begingroup$ What does "independent subsets" mean? $\endgroup$
    – abx
    Aug 23, 2014 at 6:35
  • $\begingroup$ Each of them is an independent set. $\endgroup$
    – Pablo
    Aug 23, 2014 at 6:37
  • $\begingroup$ And by "independent" you mean that no $n+2$ elements of $A$ belong to the same $n$-dimensional subspace of $V$? So, for examples, if $V$ is 1-dimensional, $A$ can contain at most 2 points? $\endgroup$ Aug 23, 2014 at 7:57
  • 1
    $\begingroup$ I consider a set independent if there is no nontrivial linear combination of its elements giving $0$. $\endgroup$
    – Pablo
    Aug 23, 2014 at 8:35

2 Answers 2

2
$\begingroup$

Not an answer, but this might get you more help by phrasing it in terms of a common combinatorics problem - finding a lower bound for the size of a transversal of a hypergraph. A hypergraph is a collection of points and edges like a graph, but each edge can contain any number of vertices. A transversal for a hypergraph is a set of vertices which intersect every edge.

Let $V=\mathbb{F}_q^k$ be a $k$-dimensional vector space over the finite field of $q$ elements. The naive hypergraph construction would be to take each non-zero point as a vertex, and each hyperplane as an edge. We must exclude zero because it is on every hyperplane, and would give a trivial transversal. Finding a minimal transversal here will tell you how many points you need to make sure that every hyperplane is hit, hence if it is larger than $|A \cup B|$, which can be at most $2k$, then there will be a hyperplane disjoint from them. This may not be the best construction however, because points on a line in $V$ will always appear together on each edge, so we lose some symmetry. Two arbitrary points will be contained in a different number of hyperplanes depending on whether or not they are collinear with the origin.

Instead, for a point $v \in V$, write $L(v) = \{v,2v,\ldots, (q-1)v\}$ for the line of points through $v$ and the origin. Construct the hypergraph $H$ with vertices $L(v)$, discarding duplicates, and hyperplanes for edges. Certainly if $v$ is on a hyperplane $P$, then $L(v)$ is also contained in $P$, so a transversal for the naive construction also gives us a transversal here, and conversely by choosing any point on the line $L(v)$. This construction has nice properties: it has $\frac{q^{k}-1}{q-1}$ vertices and the same number of edges; it is uniform, meaning all edges have the same number of vertices, $\frac{q^{k-1}-1}{q-1}$; it is regular, meaning every vertex is on the same number of edges, again $\frac{q^{k-1}-1}{q-1}$; and every pair of vertices is on the same number of edges, $\lambda = \frac{q^{k-2}-1}{q-1}$. These sorts of hypergraphs are often studied for small orders, and are related to block designs, but I could not find or produce anything that applied to your specific family of spaces. At this point, you can try looking through the literature with these terms (maybe Berge's book Hypergraphs), or ask a noted expert in the field like Noga Alon, who is also conveniently at Tel-Aviv University.

$\endgroup$
1
  • $\begingroup$ I think that it is rather apparent that there is a transversal of size $q+1$ which is smaller than $2k$ for large enough $k$. In your suggestion, you only use the independence of $A$ and $B$ in bounding their size which is clearly too coarse. $\endgroup$
    – Pablo
    Aug 24, 2014 at 22:04
0
$\begingroup$

Say $V$ has dimension $n>1$. Assume, WLOG, and throwing in extra vectors if necessary, that $A$ is the set of elementary vectors in $V$. Consider a matrix of the form $$M=\left(\begin{matrix} 1&0 &\cdots&0\\ 0&1&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&1\\ a_1&a_2&\cdots&a_{n-1} \end{matrix}\right).$$ The columns of $M$ span an $(n-1)$-dimensional subspace, and if $a_i\ne 0$ for $\ 1\le i\le n-1,$ this subspace avoids $A$.

Now the question is whether given a linearly independent set $B\subset V$, there is a choice of $a_i\in F\setminus\{0\},\ 1\le i\le n-1,$ such that the span of these $n-1$ vectors also avoids $\ B$.

Let $B=\{\mathbf v_1,\mathbf v_2,\ldots,\mathbf v_n\}$ such that at least one of $\mathbf v_i=(v_{i1},v_{i2},\ldots,v_{in})^T$ is in the span of the columns of $M$, for any choice of $(a_1,a_2,\ldots,a_n)$. Since $B$ is linearly independent, we can re-order the elements of $B$ till $v_{ii}\ne0$ for all $1\le i\le n$. This gives at least $|F|-2$ choices of $a_{1}$ such that $v_{1n}\ne\sum_{i=1}^{n-1}a_iv_{1i}$. Same again up to $a_{n-1}$. Finally we can assure $v_{nn}\ne\sum_{i=1}^{n-1}a_iv_{ni}$, by changing at most one of the $a_i$s.

Comment: It seems to me that the only assumption we need on $F$ is that $|F|>3$, and I'm not sure if even that is necessary when $n\ge 3.$

$\endgroup$
3
  • $\begingroup$ The way you choose $a_1$ is dependent on $a_2,...,a_{n-1}$. How do you make a coherent choice? $\endgroup$ Aug 24, 2014 at 10:22
  • $\begingroup$ The assumption $|F|\geq 4$ is surely unavoidable in the general case. Indeed, in the case $V$ has dimension $n$ the conjecture is equivalent to proving that one cannot find two families $(G_1,...,G_n)$ and $(H_1,...H_n)$ of independent hyperplanes which cover $V$. If $|F|<=3$ then $4$ hyperplanes suffice to cover $V$. $\endgroup$ Aug 24, 2014 at 10:27
  • $\begingroup$ @ClémentdeSeguinsPazzis: Ah! It seems some sort of row reduction of $B$ is in order. I will think a bit more carefully about this. You are right that $|F|>3$ is necessary. $\endgroup$ Aug 24, 2014 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.