Let ${\cal A}$ be a set of $k\times n $ matrices over ${\mathbb F}_2$.

We call ${\cal A}$ a (n,k)-covering, if for every subset of columns $I=(i_1,\ldots,i_k)\subseteq [n]$, there is a matrix $A \in {\cal A}$ such that the columns $(i_1,\ldots,i_k)$ in $A$ are linearly independent.

It is known that when choosing a random $k\times k$ matrix over ${\mathbb F}_2$ the probability that it is non-singular is at least half.

This means that if we pick at random a set of $r$ such matrices, the probability that for some $I=(i_1,\ldots,i_k)\subseteq [n]$ won't be covered (by any matrix $A \in {\cal A}$) is at most $2^{-r}$.

Since there are $n \choose k$ such $I$'s, the probability that one of them will not be covered is at most (union bound):

$${n \choose k} \cdot 2^{-r}.$$

If we force this probability to be strictly lower than 1 (which ensures such family of size $r$ exists), we get:

$${n \choose k} \cdot 2^{-r}<1 \Rightarrow r > k \log n.$$

Is there a deterministic build of such family of size $O(k \log n)$, or at least of size $\text{poly}(k,\log n)$?

Motivation for this problem:

I have an algorithm that searches for subgraphs of a given graph $G$ which are similar to a smaller graph $H$ on $k$ vertices. As part of the algorithm it gets a $k\times n$ matrix (each vertex in the graph is associated with a binary vector of length k) and then it checks that all of the vertices which are matched to $H$ are different by checking that the induced $k \times k$ matrix is not singular.

On the one hand, if two vertices of $H$ were mapped to the same vertex, their vectors are the same and the matrix's rank will surely be less than $k$. On the other, I'm not guaranteed that if the vertices were distinct the resulting matrix will be of full rank, so I run the algorithm for every matrix in my $(n,k)$-covering family.

Currently I can draw random matrices and get the result with high probability, but an explicit build will allow me to derandomize the algorithm.



Your Answer

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