# Authenticated Multicast in Tiny Networks via an Extremely Low-Bandwidth Medium
## 4 Sender Authentication
### Optimal Values for Small Number of Nodes
#### 4.5.2 Exact Values of \(\Psi(r)\) for Small \(r\)  
In the following, we derive concrete values of \(\Psi(r)\) for \(r=2,\ldots,15\), starting from the straightforward cases and gradually increasing \(r\). The results are somewhat surprising, and show (as is common in combinatorics) that focusing on special structures may bring unexpectedly good results. \(\Psi(2)=2\)Obviously, as \(1\) must be separated from \(2\) by a different set than \(2\) from \(1\). \(\Psi(3)=3\)We have \(\Psi(3)\leq 3\); thus, we assume that \(\Psi(3)=2\), and \(\mathcal{SF}\) is the corresponding minimal separating family. Each \(x\in\{1,2,3\}\) must belong to some set from \(\mathcal{SF}\); thus, by the pigeonhole principle, there is \(F\in\mathcal{SF}\) that contains two elements, say, \(a\) and \(b\). We need two sets that separate \(a\) and \(b\), say \(a\in F_{1}\), \(b\
otin F_{1}\) and \(a\
otin F_{2}\), \(b\in F_{2}\). Thus, \(F_{1}\), \(F_{2}\) are different from \(F\), and we have at least three sets in \(\mathcal{SF}\), which is a contradiction. \(\Psi(4)=4\)Similar to above, we have \(\Psi(4)\leq 4\). By way of contradiction, suppose that \(\Psi(4)\leq 3\); then, by the pigeonhole principle, there exists a set in \(\mathcal{SF}\) that contains at least two elements. Without loss of generality, we may assume that there is no four-element set in \(\mathcal{SF}\), as it would not contribute to the separation of any elements. Supposing first that there exists an set \(F\in\mathcal{SF}\) that contains \(3\) elements, say, \(F=\{1,2,3\}\), then the elements \(1\), \(2\), and \(3\) must be separated; however, \(F\) does not contribute to this separation. Thus, there must be \(\Psi(3)=3\) elements in \(\mathcal{SF}\) other than \(F\) that separate these elements. Therefore, \(\mathcal{SF}\) has at least four elements, which is a contradiction. Suppose now that there is no three-element set in \(\mathcal{SF}\). Because there must be at least one two-element set, let it be \(F=\{1,2\}\). Similarly as in the case of \(\Psi(3)=3\), the elements \(1\) and \(2\) must be separated; thus, there exist \(F_{1},F_{2}\in\mathcal{SF}\) such that \(1\in F_{1}\), \(2\
otin F_{1}\), and \(1\
otin F_{2}\), \(2\in F_{2}\). Therefore, \(\mathcal{SF}\) consists of at least the three sets: \(\{1,2\}\), \(F_{1}\), and \(F_{2}\). Because \(3\) and \(4\) must belong to some set of \(\mathcal{SF}\), and no set has three elements, we have (up to exchanging the elements \(3\) and \(4\)) \(F_{1}=\{1,3\}\), \(F_{2}=\{2,4\}\). However, in this case, elements \(1\) and \(3\) are not separated, which is a contradiction. \(\Psi(5)=4\)Because \(\Psi(4)\leq\Psi(5)\leq\Psi(6)\), and (as we later show) \(\Psi(6)=4\), we obtain \(\Psi(5)=4\) as well. However, for later use we need to show that (up to a permutation on \(\{1,\ldots,5\}\)) the only solution with four sets is the family \(\{\{1,3\},\{2,4\},\{1,2,5\},\{3,4,5\}\}\). Let \(\mathcal{SF}\) be a separating family consisting of four sets. The first observation is that \(\mathcal{SF}\) does not contain any set \(F\) of cardinality \(4\). Indeed, the elements of \(F\) must be separated from each other, and we need \(\Psi(4)=4\) sets for this purpose. As \(F\) does not separate any pair of its elements, \(\mathcal{SF}\) would contain at least \(5\) elements, which is a contradiction. Similar reasoning shows that \(\mathcal{SF}\) does not contain any one-element set. Now, \(\mathcal{SF}\) cannot contain only sets of cardinality 2, otherwise the sets from \(\mathcal{SF}\) would contain eight elements altogether (with repetitions), meaning that some element \(i\) would appear in only one set. As this set would contain another element \(j\), it would be impossible to separate \(i\) from \(j\). As \(\mathcal{SF}\) must contain a set of cardinality 3, we assume without loss of generality that \(\{1,2,3\}\in\mathcal{SF}\). In order to separate \(1,2,3\), each \(i\in\{1,2,3\}\) must be included in a set \(F_{i}\) such that \(i\in F_{i}\) and none of the remaining elements from \(\{1,2,3\}\) belongs to \(F_{i}\).