# On the Descriptive Complexity of Color Coding +
## 4 Syntactic Proofs and Natural Problems
### Bounded Strong-Rank Description of Hitting Set
Thus, if we \"view core as our new hyperedge predicate,\" we get \"cores of cores\":  
\[\textsc{core}^{2}\,c=\exists\,p_{1}^{1}\cdots\exists\,p_{k+1}^{d} \,\bigwedge_{i\
eq j}\,\bigwedge_{r,s\in\{1,\ldots,d\}}\,\dot{p}_{i}^{r}\
eq \dot{p}_{j}^{s}\,\wedge\] \[\bigwedge_{i=1}^{k+1}\exists e^{d}(\textsc{core}\,e^{\prime}\wedge \textsc{subset}\,e^{\prime}\,\wedge\] \[\{\dot{p}_{i}^{1},\ldots,\dot{p}_{i}^{d}\}=\{v\mid\textsc{in}\,v e^{\prime}\wedge\
eg\textsc{in}\,vc\}\big{)}.\]  
Note that \(\textsc{strong-qr}(\textsc{core}^{2}\,c)=\textsc{strong-qr}(\textsc{core}\,c)+1=2\) since we had to add a new strong quantifier (\(\exists e^{\prime}\)) whose scope contains \(\textsc{core}\,e^{\prime}\), which adds its own strong quantifier (\(\exists e\)). By the same argument as earlier, we get that the number of \(e\) for which the following formula holds equals the number of cores of cores plus something that only depends on the parameters \(k\) and \(d\):  
\[\textsc{core}^{2}\,e\vee(\textsc{core}\,e\wedge\
eg\exists c( \textsc{core}^{2}\,c\wedge\textsc{subset}\,ce))\] \[\vee(\textsc{hyperedge}\,e\wedge\
eg\exists c(\textsc{core}\,c \wedge\textsc{subset}\,ce)).\]  
Still, the number of cores of cores can be large, but they all have size at most \(d-2\). Repeating the argument a further \(d-2\) times, we finally get the predicate kernel \(e\):  
\[\textsc{core}^{d}\,e\vee\bigvee_{i=1}^{d}(\textsc{core}^{i-1}\,e\wedge\
eg \exists c(\textsc{core}^{i}\,c\wedge\textsc{subset}\,ce)), \tag{23}\]  
where \(\textsc{core}^{0}\) is of course hyperedge and \(\textsc{core}^{d}\,e\) can only be true for the (sole) \(e\) representing the empty set (in which case, there is no hitting set). Unfortunately, the strong quantifier rank of \(\textsc{core}^{d}\) is \(d\) since the definition of \(\textsc{core}^{i}\) in terms of \(\textsc{core}^{i-1}\) always adds one strong quantifier nesting (through a new \(\exists e^{\prime\ldots}\)). Thus, (23) also has a strong quantifier rank of \(d\) while we need \(O(1)\). Finding pseudo-sunflowers: at this point, we need a way of describing cores of cores and so on using a bounded strong quantifier rank. The idea how this can be done was presented in [19], where the notions of pseudo-cores and pseudo-sunflowers are introduced. The definitions are somewhat technical, see below, but the interesting fact about these definitions is that they can be expressed very nicely in a way similar to (20) and (21). For a level \(L\) and a number \(k\), let \(T^{k}_{L}\) denote the rooted tree in which all leaves are at the same depth \(L\) and all inner nodes have exactly \(k+1\) children. The root of \(T^{k}_{L}\) will always be called \(r\) in the following. Thus, \(T^{k}_{1}\) is just a star consisting of \(r\) and its \(k+1\) children, while in \(T^{k}_{2}\) each of the \(k+1\) children of \(r\) has \(k+1\) new children, leading to \((k+1)^{2}\) leaves in total. For each \(l\in\operatorname{leaves}(T^{k}_{L})=\{l\mid l\text{ is a leaf of }T^{k}_{L}\}\) there is a unique path \((l^{0},l^{1},\dots,l^{L})\) from \(l^{0}=r\) to \(l^{L}=l\). **Definition 4** (Pseudo-Sunflowers and Pseudo-Cores, [19]). : _Let \(H=(V,E)\) be a hypergraph and let \(L\) and \(k\) be fixed. A set \(c\subseteq V\) is called a \(k\)-pseudo-core of level \(L\) in \(H\) if there exists a mapping \(S\colon\operatorname{leaves}(T^{k}_{L})\times\{0,1,\dots,L\}\to\{e\mid e\subseteq V\}\), called a \(T^{k}_{L}\)-pseudo-sunflower for \(H\) with pseudo-core \(c\), such that for all \(l,m\in\operatorname{leaves}(T^{k}_{L})\) with \(l\
eq m\) we have:_  
1. \(S(l,0)=c\)_._
2. \(S(l,0)\cup S(l,1)\cup\dots\cup S(l,L)\in E\)_._
3. \(S(l,i)\cap S(l,j)=\emptyset\) _for_ \(0\leq i<j\leq L\)_, but_ \(S(l,i)\
eq\emptyset\) _for_ \(i\in\{1,\dots,L\}\)_._
4. _Let_ \(z\in\{1,\dots,L\}\) _be the smallest number such that_ \(l^{z}\
eq m^{z}\)_, that is,_ \(z\) _is the depth where the path from_ \(r\) _to_ \(l\) _and the path from_ \(r\) _to_ \(m\) _diverge for the first time.