For every \(q\in \mathbb{N}\) let \(\text{FO}_q\) denote the class of sentences of first-order logic \(\text{FO}\) of quantifier rank at most \(q\). If a graph property can be defined in \(\text{FO}_q\), then it can be decided in time \(O(n^q)\). Thus, minimizing \(q\) has favorable algorithmic consequences. Many graph properties amount to the existence of a certain set of vertices of size \(k\). Usually this can only be expressed by a sentence of quantifier rank at least \(k\). We use the color-coding method to demonstrate that some (hyper)graph problems can be defined in \(\text{FO}_q\), where \(q\) is independent of \(k\).

It is crucial for our results that the \(\text{FO}\)-sentences have access to built-in addition and multiplication. It is known that then \(\text{FO}\) corresponds to the circuit complexity class uniform \(\text{AC}^0\). We explore the connection between the quantifier rank of \(\text{FO}\)-sentences and the depth of \(\text{AC}^0\)-circuits, and prove that \(\text{FO}_q \subsetneq \text{FO}_{q+1}\) for structures with built-in addition and multiplication.