Induced bisecting families for hypergraphs

Abstract

Two $n$-dimensional vectors $A$ and $B$, $A,B\in {\mathbb{R}}^n$, are said to be \emph{trivially orthogonal} if in every coordinate $i\in [n]$, at least one of $A(i)$ or $B(i)$ is zero. Given the $n$-dimensional Hamming cube $\{0,1{\}}^n$, we study the minimum cardinality of a set $\mathcal{V}$ of $n$-dimensional $\{-1,0,1\}$ vectors, each containing exactly $d$ non-zero entries, such that every `possible' point $A\in \{0,1{\}}^n$ in the Hamming cube has some $V\in \mathcal{V}$ which is orthogonal, but not trivially orthogonal, to $A$. We give asymptotically tight lower and (constructive) upper bounds for such a set $\mathcal{V}$ except for the even values of $d\in \Omega (n^{0.5+\epsilon })$, for any $\epsilon$, $0<\epsilon \le 0.5$.

9 pages, 1 figure