An Erdős-Ko-Rado theorem for signed sets (Q1388967): Difference between revisions

Let \([n]=\{1,\dots,n\}\). A signed \(r\)-set on \([n]\) is a pair \((A,f)\), where \(A\subseteq [n]\), \(| A| =r\) and \(f:A\to\{-1,1\}\). A family \(\mathcal A\) of signed \(r\)-sets is called intersecting if for any \((A,f),(B,g)\in\mathcal A\) there exists \(x\in A\cap B\) such that \(f(x)=g(x)\). It is shown that \(| {\mathcal A}| \leq 2^{r-1}{n-1\choose r-1}\) for any intersecting family \(\mathcal A\) of signed \(r\)-sets. In the case \(r<n\) all maximum intersecting families are specified. As an application of this result the authors provide another proof to their published result on constructing a maximum-sized set of vertices of a grid \([-k,k]^n\), which has a fixed diameter \(d\). This problem is more difficult if \(d\) is odd. In the case \(d\geq n(k+1)\) it is shown how the result mentioned above can be applied to simplify the original proof.