# Largest subspace that doesn't intersect a given set

Let V be a vector space over Z/2, and let X be a subset of V. Is there an algorithm to find the largest possible subspace of V which doesn't intersect X? Is it NP complete?

-
I guess Z/2 is $\mathbb F_2=\mathbb Z/2\mathbb Z$, not $\frac12\mathbb Z$. – Wadim Zudilin Jul 23 '10 at 3:20
kevin: let V be the space of pairs of 2 bits. let X be { (1,0), (0,1) }. The space generated by X is all of V, but the space generated by (1,1) does not intersect X. – Larry D'Anna Jul 23 '10 at 3:25
Erm... Are you 100% sure about this statement? I mean, it is very easy to create a subspace $S$ and two points $x,y\notin S$ such that $x+y\in S$. – fedja Jul 23 '10 at 3:27
Yikes. Deleted. – Kevin Ventullo Jul 23 '10 at 3:41
minor nit: you're really asking if it's NP-hard since it's a maximization, not a decision problem – Suresh Venkat Jul 23 '10 at 4:26

The problem is NP hard. Here's a reduction to it from 4-colorability. Given a graph with vertex set $G$ [not $V$ because that's supposed to be a vector space] and edge set $E$, form a vector space $V$ over $\mathbb{Z}/2$ having $G$ as a basis. Identify each edge $e$ with the vector that is the difference of the two endpoints of $e$, and let $S$ be the set of these edges-qua-vectors. [I know that "difference" is the same as "sum" here, but it helps to think of the edges as differences.] Then each of the following statements is easily equivalent to the next, for any fixed natural number $t$. [In the end, I'll only need the case $t=2$.]

(1) $V$ has a subspace of codimension at most $t$ that misses $S$.

(2) There are $t$ linear functionals $f:V\to\mathbb{Z}/2$ such that each edge $e$ is sent to 1 by at least one of these functionals.

(3) There are $t$ linear functionals $f:V\to\mathbb{Z}/2$ such that, for each edge $e$, at least one of these functionals takes different values at the two endpoints of $e$.

(4) There are $t$ functions $g:G\to\mathbb{Z}/2$ such that, for each edge $e$, at least one of these functions takes different values at the two endpoints of $e$.

(5) There is a function $h$ from $G$ to $(\mathbb{Z}/2)^t$ taking different values at the two ends of each edge.

(6) The graph $(G,E)$ is $2^t$-colorable.

In particular, $V$ has a codimension-2 subspace missing $S$ if and only if $G$ is 4-colorable. Since 4-colorability is known to be an NP-complete problem, the vector subspace problem is also NP-hard.

I believe the "correct" generality for this idea is what's called the critical problem for matroids. What I've presented is the special case of graphic matroids.

-