2
$\begingroup$

Assuming that one needs $k$ quantifiers to express that a graph contains an $k$-cycle, $\lfloor n/2 \rfloor$ counting quantifiers suffice to express that a graph is an $n$-cycle:

G has exactly $n$ nodes, each node has exactly 2 neighbors, and G doesn't contain a 3-cycle, a 4-cycle, ... and an $\lfloor n/2 \rfloor$-cycle.

Question: Can be shown, that one needs at least $\lfloor n/2 \rfloor$ counting quantifiers to express that a graph is an $n$-cylce? And how?

$\endgroup$

2 Answers 2

2
$\begingroup$

The previous answer showed that quantifier rank $\log_2(k) \pm 1$ is sufficient and necessary for expressing "A is a $k$-cycle". This implies a lower bound of at least $\log_2(k)$ quantifiers, but not an upper bound since quantifier rank counts nesting-depth of quantifiers and not the number of quantifiers. However, it is possible to express "A is a $k$-cycle" with $O(\log k)$ quantifiers. Here is an explicit expression:

You start saying that every vertex has degree exactly two. These are $4$ quantifiers. Next we need to say that every two vertices $x$ and $y$ of the graph are connected by a path of length at most $k$. Let $P_k(x,y)$ denote this predicate. The naive way to express $P_k(x,y)$ requires $k$ quantifiers. A less naive way could use divide-and-conquer but, if we do it directly without any additional trick, the result would still be $k$ quantifiers. The final solution will be to add a trick to the divide and conquer solution.

The divide and conquer solution goes as follows: you quantify the middle vertex $z$ and then recurse on the halfs $x$-$z$ and $z$-$y$ by requiring that both $P_{k/2}(x,z)$ and $P_{k/2}(z,y)$ hold. An easy computation shows that this method produces $k$ quantifiers. To improve and achieve $O(\log k)$ quantifiers we make use of a "reusing trick" that those familiar with computational complexity will recognize from the proof that QBF is PSPACE-complete: you quantify the middle vertex $z$ and then say: for every $u$ and $v$, if $u = x$ and $v = z$, or $u = z$ and $v = y$, then $P_{k/2}(u,v)$. This recursive formula expresses the same as before but now $P_{k/2}$ is used recursively only once. This gives the $O(\log k)$ quantifiers that we want.

Finally, in order to complete the formula expressing "A is a $k$-cycle" we need to say that every vertex $x$ is connected by a path of length exactly $k$ to itself. This we can do with $O(\log k)$ quantifiers using the same trick that we used for $P_k$.

(Note: all this is much easier to argue if $k$ is an exact power of $2$ but can be made to work for any $k$).

$\endgroup$
3
$\begingroup$

If A and B are cycles of length m, n, then the duplicator can win the k-long Ehrenfeucht-Fraisse game iff m, n > 2^(k-1).

Basically, whatever player I moves in A, player II choose an arbitrary element in B. The rest of the strategy is the same as for linear orders.

This means that A and B are elementarily equivalent up to quantifier-rank [log_2 min(n,m)] + 1. In particular, need at least log_2 k + 1 quantifiers to express "A is a k-cycle".

(I may have gotten the quantifier-rank wrong by +- 1, but should still be basically log2 k )

$\endgroup$
1
  • $\begingroup$ Can the expression "A is a k-cycle" be made explicit with log_2 k quantifiers? I'd like to see it. $\endgroup$ Oct 16, 2010 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.