$L$-balancing families

Abstract

P. Hrube\v s, S. Natarajan Ramamoorthy, A. Rao and A. Yehudayoff proved the following result: Let $p$ be a prime and let $f\in {\mathbb{F}}_p[x_1,\dots ,x_{2p}]$ be a polynomial. Suppose that $f({\mathbf{v}}_{\mathbf{F}})=0$ for each $F\subseteq [2p]$, where $|F|=p$ and that $f(0)\ne 0$. Then $\mbox{deg}(f)\geq p$. We prove here the following generalization of their result. Let $p$ be a prime and $q=p^{\alpha }>1$, $\alpha \ge 1$. Let $n>0$ be a positive integer and $q-1\le d\le n-q+1$ be an integer. Let $\mathbb{F}$ be a field of characteristic $p$. Suppose that $f({\mathbf{v}}_{\mathbf{F}})=0$ for each $F\subseteq [n]$, where $|F|=d$ and $\mbox{deg}(f)\leq q-1$. Then $f({\mathbf{v}}_{\mathbf{F}})=0$ for each $F\subseteq [n]$, where $|F|\equiv d \mbox{ (mod }q)$. Let $t=2d$ be an even number and $L\subseteq [d-1]$ be a given subset. We say that $\mbox{$\cal F$}\subseteq 2^{[t]}$ is an {\em $L$-balancing family} if for each $F\subseteq [t]$, where $|F|=d$ there exists a $G\subseteq [n]$ such that $|F\cap G|\in L$. We give a general upper bound for the size of an $L$-balancing family.