# On the Descriptive Complexity of Color Coding +
## 4 Syntactic Proofs and Natural Problems
### Bounded Strong-Rank Description of Hitting Set
For the large instances, we now have a universe that is \"large enough\" to contain an element for each subset of a hyperedge and it is not difficult (but technical) to use the bit predicate to define the correct predicates hyperedge, vertex, and in in terms of the original structure. Thus, in the following, we may assume that for every hyperedge in the input structure for all subsets of this hyperedge we already have an element in the universe representing this subset. Finding sunflowers: we first show a way of kernelizing the hitting set problem, due to [PERSON] et al. [4], that \"almost works.\" The core idea is to detect and collapse sunflowers in the input hypergraph [20]. A sunflower of size \(k+1\) with core \(c\) is a set \(\{p_{1},\ldots,p_{k+1}\}\subseteq E\) of distinct hyperedges, called petals, such that for all \(i\
eq j\) we have \(p_{i}\cap p_{j}=c\). In other words, all petals contain the core but are otherwise pairwise distinct. For convenience, we also assume that all petals are proper supersets of the core. The important observation is that if a sunflower of size \(k+1\) has a hitting set of size \(k\), then the core must also be hit--and when the core is hit, all petals are hit. This means that we can just replace a sunflower by its core when we are looking for size-\(k\) hitting sets. The following formula tests whether \(\text{set}(c)\) is the core of a sunflower of size \(k+1\):  
\[\textsc{core}\,c=\exists p_{1}^{1}\cdots\exists p_{k+1}^{d}\bigwedge _{i\
eq j}\bigwedge_{\pi,s\in\{1,\ldots,d\}}p_{i}^{\tau}\
eq p_{j}^{s}\wedge \tag{20}\] \[\bigwedge_{i=1}^{k+1}\exists e\big{(}\textsc{hyperedge}\,e\wedge \textsc{subset}\,ce\wedge\] \[\{p_{1}^{1},\ldots,p_{i}^{d}\}\big{\}}=\{v\mid\textsc{IN}\,vc \wedge\
eg\textsc{IN}\,vc\}\big{)}. \tag{21}\]Here, (20) guarantees that the petals are pairwise disjoint outside the core and (21) checks that the petals are supersets of \(c\) and when we add \(p_{i}^{1}\) to \(p_{i}^{d}\) (which are not necessarily distinct) to \(c\), we get a present hyperedge. The \"collapsing\" of sunflowers to their cores can now be done as follows: We define a formula with \(e\) as a free variable that is true when \(\operatorname{set}(e)\) is a core or when \(\operatorname{set}(e)\) is not a superset of any core (otherwise, we need not include \(\operatorname{set}(e)\) since we include the core of a sunflower that contains it, instead):  
\[\textsc{core}\,e\vee(\textsc{hyperedge}\,e\wedge\
eg\exists c(\textsc{ core}\,c\wedge\textsc{subset}\,e)). \tag{22}\]  
The importance of the above formula lies in the following fact: The number of hyperedges for which the second part of the formula is true (that is, which are not supersets of a core of a sunflower of size \(k+1\)), is bounded by a function in \(k\) and \(d\). This is due to the famous Sunflower Lemma [20] which states that if a hypergraph has more than \(k^{d}d!\) hyperedges, it contains a sunflower of size \(k+1\) (which has a core). This means that if \(\textsc{core}\,e\) were to hold for just a few hyperedges, (22) would describe a kernel for the hitting set problem, meaning that the number of hyperedges remaining would be bounded by a purely parameter-dependent value. We could then proceed as in the proof of Theorem 5: In order to determine whether the original hypergraph has a hitting set of size \(k\), we only need to check whether the hypergraph induced on the remaining hyperedges has such a hitting set--and since a kernel has a purely parameter-dependent size, we could use the induced notation to solve the hitting set problem on the vertices and hyperedges for which (22) holds. Unfortunately, it is possible to construct hypergraphs such that \(\textsc{core}\,e\) still holds for a very large (not only parameter-dependent) number of hyperedges. However, we know that a core always has a smaller size than any petal in its sunflower. In particular, all cores have maximum size \(d-1\).