# 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\)
Thus, up to a permutation on \(\{1,\ldots,10\}\), the sets \(U_{1},\ldots,U_{5}\) are equal to  
\[\{1,2,3,7,8,9\},\{1,4,5,7,8,10\},\{2,4,6,7,9,10\},\{3,5,6,8,9,10\},\{1,2,3,4, 5,6\}. \tag{5}\]  
Now, assume that one of the sets in the separating family contains five elements, say \(U_{5}=\{1,2,3,4,5\}\), and that no set \(U_{i}\) has more than five elements. Consider \(U^{\prime}_{i}=U_{i}\cap U_{5}\) for \(i\leq 4\) and \(V^{\prime}_{i}=U_{i}\setminus U_{5}\) for \(i\leq 4\). These are separating families for \(\{1,\ldots,5\}\) and \(\{6,\ldots,10\}\), respectively. Thus, without loss of generality, we may assume that these families (after permuting the elements and order of the sets) are as follows:  
\[\{1,2,3\},\{1,4,5\},\{2,4\},\{3,5\} \tag{6}\]  
and  
\[\{6,7,8\},\{6,9,10\},\{7,9\},\{8,10\}\,,\]  
respectively. We have to find a matching between these two lists and sum up each pair to obtain the sets \(U_{1},\ldots,U_{4}\). Note that we always have to match a set of cardinality \(2\) with a set of cardinality \(3\) in order to satisfy the assumption that no \(U_{i}\) contains more than five elements. Now, consider element \(7\). The set \(\{6,7,8\}\) is matched with some two-element set \(U^{\prime}_{i}\), while the set \(\{7,9\}\) is matched with a three-element set \(U^{\prime}_{j}\). However, note that in this case we have \(U^{\prime}_{i}\cap U^{\prime}_{j}\
eq\emptyset\) (cf. (6)). If \(b\in U^{\prime}_{i}\cap U^{\prime}_{j}\), then we cannot separate \(7\) from \(b\), which is a contradiction. It can be seen that there is no separating family consisting of five sets where at least one of the sets contains exactly five elements. We are left with the case that every set in a separating family has at most four elements. Per Lemma 4, any such separating family corresponds to a separating family in which every set contains at least \(10-4=6\) elements. All such families have been identified above. Thus, up to a permutation, by applying Lemma 4 we obtain the following family (see Figure 8):  
\[\{1,2,3\},\{1,4,\ldots\},\{2,4,\ldots\},\{3,\ldots\}\,.\]0\(\Psi(11)=6\): Per Lemma 2, \(\Psi(11)\leq\Psi(10)+1=6\); thus, it suffices to show that \(\Psi(11)>5\). We know by monotonicity of \(\Psi\) that \(\Psi(11)\geq 5\). We assume towards a contradiction that a separating family \(\mathcal{SF}\) for \(\{1,\ldots,11\}\) contains five sets. Consider an arbitrary \(F\in\mathcal{SF}\) and \(U=\{1,\ldots,11\}\setminus F\). If either \(F\) or \(U\) has cardinality at least \(7\), then we need \(\Psi(7)=5\) sets to separate elements in this set by a similar argument as in the \(\Psi(6)=4\) case. None of them is \(F\), meaning that we have at least six elements in \(\mathcal{SF}\), which is a contradiction. We can conclude that each set \(F\in\mathcal{SF}\) contains either five or six elements. First, assume that \(F\) contains five elements. Without loss of generality, let \(F=\{1,2,3,4,5\}\). Let \(F_{1}\), \(F_{2}\), \(F_{3}\), \(F_{4}\) be the remaining four sets of family \(\mathcal{SF}\). Note that \(\{F_{1}\cap F,F_{2}\cap F,F_{3}\cap F,F_{4}\cap F\}\) must be a separating family for the set \(F=\{1,2,3,4,5\}\). According to what we have learned for the case with \(r=5\), without loss of generality, we may assume that we obtain \(F_{1}\cap F=\{1,2,3\}\), \(F_{2}\cap F=\{1,4,5\}\), \(F_{3}\cap F=\{2,4\}\), \(F_{4}\cap F=\{3,5\}\). Analogously, again without loss of generality, when we intersect \(F_{1},\ldots,F_{4}\) with \(U\), we obtain the following sets: \(\{6,7,8\}\), \(\{6,9,10\}\), \(\{7,9,11\}\), \(\{8,10,11\}\) Thus far, we do not know how to link these sets to \(\{1,2,3\}\), \(\{1,4,5\}\), \(\{2,4\}\), \(\{3,5\}\) (i.e., the intersections of the \(F_{i}\)s with \(F\)), to recover the full sets \(F_{i}\). However, we may assume that \(F_{1}=\{1,2,3\}\cup\{6,7,8\}\), as we can always rename the elements. Then, of course, \(F_{1}\) cannot be used to separate \(6\) from \(1\), \(2\), and \(3\), while \(\{6,9,10\}\) remains as a candidate for a set that separates \(6\) from \(1\), \(2\), and \(3\).