Constructions and Bounds for Splitting and Separating Systems

Abstract

Suppose \(m\) and \(t\) are integers such that \(0 < t \leq m\). An \((m,t)\)-splitting system is a pair \((X, \mathcal{B})\) that satisfies for every \(Y \subseteq X\) with \(|Y| = t\), there is a subset \(B\) of \(X\) in \(\mathcal{B}\), such that \(|B \cap Y| = \left\lfloor \frac{t}{2} \right\rfloor\) or \(|(X \setminus B) \cap Y| = \left\lceil \frac{t}{2} \right\rceil\). Suppose \(m\), \(t_1\), and \(t_2\) are integers such that \(t_1 + t_2 \leq m\). An \((m, t_1, t_2)\)-separating system is a pair \((X, \mathcal{B})\) which satisfies for every \(P \subseteq X\), \(Q \subseteq X\) with \(|P| = t_1\), \(|Q| = t_2\), and \(P \cap Q = \emptyset\), there exists a block \(B \in \mathcal{B}\) for which either \(P \subseteq B\), \(Q \cap B = \emptyset\) or \(Q \subseteq B\), \(P \cap B = \emptyset\). We will give some results on splitting systems and separating systems for \(t = 5\) and \(t = 6\).