Title: Slicewise definability in first-order logic with bounded quantifier rank,
Abstract: For every $q\in \mathbb N$ let $\textrm{FO}_q$ denote the class of sentences
of first-order logic FO of quantifier rank at most $q$. If a graph property can
be defined in $\textrm{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 $\textrm{FO}_q$ where $q$ is independent of $k$. This property of a
graph problem is equivalent to the question of whether the corresponding
parameterized problem is in the class $\textrm{para-AC}^0$.
It is crucial for our results that the FO-sentences have access to built-in
addition and multiplication. It is known that then FO corresponds to the
circuit complexity class uniform $\textrm{AC}^0$. We explore the connection
between the quantifier rank of FO-sentences and the depth of
$\textrm{AC}^0$-circuits, and prove that $\textrm{FO}_q \subsetneq
\textrm{FO}_{q+1}$ for structures with built-in addition and multiplication.