# On the Descriptive Complexity of Color Coding +
###### Abstract
Clearly, this is a now a very easy problem and if we do, indeed, find \(k\) triangles having \(k\) different colors, we have found \(k\) vertex-disjoint triangles. The ingenious idea behind the color coding technique of [PERSON], [PERSON], and [PERSON] [3] is to reduce the hard triangle packing problem to the much simpler colored version by simply randomly coloring the graph. Of course, even if there are \(k\) disjoint triangles, we will most likely not color them monochromatically and differently, but the probability of \"getting lucky\" is nonzero (at least \(k^{-3k}\)) and depends only on the parameter \(k\). Even better, [PERSON] et al. point out that one can derandomize the coloring easily by using universal hash functions to color each vertex with its hash value. Applying this idea in the setting of descriptive complexity was recently pioneered by [PERSON] et al. [4]. Transferred to the triangle packing problem, their argument would roughly be: \"Testing for each color \(i\), whether there is a monochromatic triangle of color \(i\), can be done in first-order logic using something like \(\bigwedge_{i=1}^{k}\exists x\exists y\exists z(Exp\wedge Eyz\wedge Exz \wedge C_{i}x\wedge C_{i}y\wedge C_{i}z)\). Next, instead of testing whether \(x\) has color \(i\) using the formula \(C_{i}x\), we can test whether \(x\) gets hashed to \(i\) by a hash function. Finally, since computing appropriate universal hash functions only involves addition and multiplication, we can express the derandomized algorithm using an arithmetic first-order formula of low quantifier rank.\" Phrased differently, [PERSON] et al. would argue that \(\bigwedge_{i=1}^{k}\exists x\exists y\exists z(Exp\wedge Eyz\wedge Exz\wedge C_{ i}x\wedge C_{i}y\wedge C_{i}z)\) together with the requirement that the \(C_{i}\) are pairwise disjoint is (ignoring some details) equivalent to \(\delta_{k}=\exists p\exists q\bigwedge_{i=1}^{k}\exists x\exists y\exists z(Exp \wedge Eyz\wedge Exz\wedge\textsc{hash}_{k}(x,p,q)=i\wedge\textsc{hash}_{k}( y,p,q)=i\wedge\textsc{hash}_{k}(x,p,q)=i\wedge\textsc{hash}_{k}(x,p,q)=i\wedge\textsc{hash}_{k}( x,p,q)=i\), where \(\textsc{hash}_{k}(x,p,q)=i\) is a formula that is true when \"\(x\) is hashed to \(i\) by a member of a universal family of hash functions indexed by \(q\) and \(p\).\"  
The family \((\delta_{k})_{k\in\mathbb{N}}\) may seem rather technical and, indeed, its importance becomes visible only in conjunction with another result by [PERSON] et al. [4]: They show that a parameterized problem lies in para-AC\({}^{0}\), one of the smallest \"sensible\" subclasses of FPT, if it can be described by a family \((\phi_{k})_{k\in\mathbb{N}}\) of \(\mathrm{FO}[+,\times]\) formulas of bounded quantifier rank such that the finite models of \(\phi_{k}\) are exactly the elements of the \(k\)th slice of the problem. Since the triangle packing problem can be described in this way via the family \((\delta_{k})_{k\in\mathbb{N}}\) of formulas, all of which have a quantifier rank 5 plus the constant number of quantifiers used to express the arithmetics in the formulas \(\textsc{hash}_{k}(x,p,q)=i\), we get \(\textsc{p}_{k}\textsc{-triangle-packing}\in\textsc{FPT}\). Clearly, this beautiful idea cannot work in all situations: If it also worked for the formula mentioned earlier expressing 3-colorability, 3-colorability would be first-order expressible, which is known to be impossible. Our first main contribution is a syntactic characterization of when the color coding technique is applicable, that is, of why color coding works for triangle packing but not for 3-colorability: For triangle packing, the colors \(C_{i}\) are applied to variables only inside existential scopes (\"\(\exists x\exists y\exists z\)\") while for 3-colorability the colors \(R\), \(G\), and \(B\) are also applied to variables inside universal scopes (\"for all adjacent vertices\").