Is there a hyperplane avoiding two independent sets?

Question

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$?

Answer 1

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.

Answer 2

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.$