Induced bisecting families for hypergraphs

Niranjan Balachandran, Rogers Mathew, Tapas Kumar Mishra, Sudebkumar Prasant Pal

Published 2016-10-01Version 1

A dot product of two $n$-dimensional vectors $A$ and $B$, $A,B \in \mathbb{R}^n$, is said to be \emph{trivial} 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 point in the Hamming cube has a non-trivial zero dot product with at least one vector $V \in \mathcal{V}$.