Definitions with no quantifier alternation
| dc.creator | Pikhurko, Oleg | |
| dc.creator | Spencer, Joel | |
| dc.creator | Verbitsky, Oleg | |
| dc.date | 2004-05-17 | |
| dc.date | 2005-12-22 | |
| dc.date.accessioned | 2026-07-07T06:36:46Z | |
| dc.date.available | 2026-07-07T06:36:46Z | |
| dc.description | Let $D(G)$ be the minimum quantifier depth of a first order sentence $Φ$ that defines a graph $G$ up to isomorphism. Let $D_0(G)$ be the version of $D(G)$ where we do not allow quantifier alternations in $Φ$. Define $q_0(n)$ to be the minimum of $D_0(G)$ over all graphs $G$ of order $n$. We prove that for all $n$ we have $\log^*n-\log^*\log^*n-1\le q_0(n)\le \log^*n+22$, where $\log^*n$ is equal to the minimum number of iterations of the binary logarithm needed to bring $n$ to 1 or below. The upper bound is obtained by constructing special graphs with modular decomposition of very small depth. | |
| dc.description | 24 pages, we complement the lower bound proved in the first version with a tight upper bound. The title of the paper has been changed | |
| dc.identifier | https://arxiv.org/abs/math/0405326 | |
| dc.identifier | http://arxiv.org/abs/math/0405326 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/100196 | |
| dc.subject | Logic | |
| dc.subject | 03C13 | |
| dc.title | Definitions with no quantifier alternation | |
| dc.type | text |