<p>Thanks to my colleague Maxim Zhukovskii for suggesting this answer.</p>

<p>It turns out that the answer is negative, and the counterexample is rather simple. Just take $G=K_m\sqcup \overline{K_m}$ and $H=K_{m+1}\sqcup \overline{K_{m-1}}$ for $n=2m$ and $G=K_m\sqcup \overline{K_{m+1}}$ and $H=K_{m+1}\sqcup \overline{K_m}$ for $n=2m+1$. (Here $K_s$ is an $s$-clique and $\overline{K_s}$ is a set of $s$ isolated vertices). By considering the Ehrenfeucht game one can show that in the first case the minimal possible depth is $m$ and in the second case it is $m+1$.</p>

<p>It was shown in the paper <a href="http://www.sciencedirect.com/science/article/pii/S0166218X06000989" rel="noreferrer">"The first order definability of graphs: Upper bounds for quantifier depth"</a> by Oleg Pikhurko, Helmut Veith and Oleg Verbitsky that this bound is almost tight and any two $n$-vertex graphs are distinguishable by a formula of depth $\frac{n+3}{2}$.</p>

CC BY-SA 3.0
2017-11-05T14:35:15.490Z
2017-11-05T17:54:12.107Z
2017-11-05T17:54:12.107Z
Daniil Musatov
<p>I want to be very specific. Does anyone know of a disproof or a proof of the following proposition:</p>

<p>$\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N},$ </p>

<p>$\forall G, H \in STRUC[\Sigma_{graph}] (min(|G|, |H|) = n, G \not\simeq H),$</p>

<p>$\exists \varphi \in \mathcal{L}(\Sigma_{graph}),$ </p>

<p>$|\varphi| \leq p(n) \wedge qd(\varphi) \leq Clog(n)^k \wedge G \vDash \varphi \wedge H \nvDash \varphi.$</p>

<p>Intuitively, this should be true if all non-isomorphic graphs can be distinguished using "$Clog(n)^k$ local" statements, and I'd imagine that this is false. Of course any graph can be distinguished using polynomial quantifier depth, as you can simply specify your graph modulo isomorphism:</p>

<p>$\varphi = \exists x_1 \exists x_2 \exists x_3 ... \exists x_n (\forall x (\bigvee_{i \in V_G} x = x_i) \wedge (\bigwedge_{(i, j) \in E_G} E(x_i, x_j))) \wedge (\bigwedge_{(i, j) \notin E_G} \neg E(x_i, x_j))) \wedge (\bigwedge_{(i, j) \in V_G^2 \mid i \neq j}x_i \neq x_j).$</p>

<p><strong>Edit:</strong> So it seems that the locality intuition I had is false. A formula of quantifier depth $k$ has Gaifman locality bounded by $O(3^k)$, which means that a log depth formula is basically global. For this reason, I have a hunch the proposition will turn out to be true, which would be <strong>much</strong> harder to prove in my opinion.</p>

CC BY-SA 3.0
2017-10-25T22:14:57.497Z
What about the path and two disconnected paths each of length $\frac{n}{2}$
Samuel Schlesinger
CC BY-SA 3.0
2017-10-26T11:13:37.993Z
The path only has two nodes of degree $1$, two paths have four. I.e., they can be distinguished by a constant-size formula. You may have better luck with one circle vs. two circles, but I think they can be distinguished by a formula of quantifier rank $O(\log n)$.
Emil Jeřábek
CC BY-SA 3.0
2017-10-27T08:12:31.333Z
Tall trees might work for a refutation, if they differ close to the leaves.
András Salamon
CC BY-SA 3.0
2017-10-27T08:14:18.947Z
@EmilJeřábek is that true without equality?
Samuel Schlesinger
CC BY-SA 3.0
2017-10-27T11:28:32.010Z
I don’t know, maybe not. But AFAICS, bounded reachability can still be defined by log-depth formulas, which can be used to distinguish the two models. In any case, without equality, there are pairs of nonisomorphic graph that cannot be distinguished by any formula whatsoever.
Emil Jeřábek
CC BY-SA 3.0
2017-10-31T21:58:40.933Z
Two paths of length $n, n + 1$ respectively can't be distinguished by formulas of quantifier depth $log(n)$, but this of course doesn't rule out the general polylogarithmic case. That should be the idea though, picking two things which are only distinguishable by an essentially global property.
Samuel Schlesinger
CC BY-SA 3.0
2017-10-31T22:05:10.477Z
One could imagine that G and H could be equivalent in all of their local properties but aut[G] does not equal aut[H], or maybe even aut[G] = 1 or something.
Samuel Schlesinger
CC BY-SA 3.0
2017-11-01T04:13:15.490Z
@EmilJeřábek Do you have a citation for the claim about languages without equality? I would love to read that and google is failing me.
Stella Biderman
CC BY-SA 3.0
2017-11-01T05:22:19.647Z
@StellaBiderman I think you can prove it by taking any graph $G$ and expanding it into a graph $G_k$ with $k$ times as many elements in its universe where before we had $(x_0, y_0) \in E_G$ now we have $(x_i, y_i)
 \in E_{G_k}$ for any $i \in [k]$. Haven't went through it formally but it seems pretty clear that $G_k \vDash \varphi \Longleftrightarrow G \vDash \varphi$, as we can't really distinguish between any of the $k$ copies of $x_0$.
Samuel Schlesinger
CC BY-SA 3.0
2017-11-01T08:34:51.843Z
@StellaBiderman The truth of formulas without equality is preserved by surjective reflecting (i.e., preserving relations in both ways) homomorphisms. In the case of graphs, for example, any two graphs with no edges satisfy the same sentences. More generally, one can take any graph, and blow up any vertex into an independent set.
Emil Jeřábek
<graph-theory><graph-isomorphism><formulas><first-order-logic>
For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?
Samuel Schlesinger
# For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?

(Asked by: username_0 on 2017-10-25)

I want to be very specific. Does anyone know of a disproof or a proof of the following proposition:

$\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N},$

$\forall G, H \in STRUC[\Sigma\_{graph}] (min(|G|, |H|) = n, G \not\simeq H),$

$\exists \varphi \in \mathcal{L}(\Sigma\_{graph}),$

$|\varphi| \leq p(n) \wedge qd(\varphi) \leq Clog(n)^k \wedge G \vDash \varphi \wedge H \nvDash \varphi.$

Intuitively, this should be true if all non-isomorphic graphs can be distinguished using "$Clog(n)^k$ local" statements, and I'd imagine that this is false. Of course any graph can be distinguished using polynomial quantifier depth, as you can simply specify your graph modulo isomorphism:

$\varphi = \exists x\_1 \exists x\_2 \exists x\_3 ... \exists x\_n (\forall x (\bigvee\_{i \in V\_G} x = x\_i) \wedge (\bigwedge\_{(i, j) \in E\_G} E(x\_i, x\_j))) \wedge (\bigwedge\_{(i, j) \notin E\_G} \neg E(x\_i, x\_j))) \wedge (\bigwedge\_{(i, j) \in V\_G^2 \mid i \neq j}x\_i \neq x\_j).$

**Edit:** So it seems that the locality intuition I had is false. A formula of quantifier depth $k$ has Gaifman locality bounded by $O(3^k)$, which means that a log depth formula is basically global. For this reason, I have a hunch the proposition will turn out to be true, which would be **much** harder to prove in my opinion.

**Tags:** graph-theory, graph-isomorphism, formulas, first-order-logic
> **Comments:**
> **username_0**: What about the path and two disconnected paths each of length $\frac{n}{2}$  
> **username_1**: The path only has two nodes of degree $1$, two paths have four. I.e., they can be distinguished by a constant-size formula. You may have better luck with one circle vs. two circles, but I think they can be distinguished by a formula of quantifier rank $O(\log n)$.  
> **username_2**: Tall trees might work for a refutation, if they differ close to the leaves.  
> **username_0**: @EmilJeřábek is that true without equality?  
> **username_1**: I don’t know, maybe not. But AFAICS, bounded reachability can still be defined by log-depth formulas, which can be used to distinguish the two models. In any case, without equality, there are pairs of nonisomorphic graph that cannot be distinguished by any formula whatsoever.  
> **username_0**: Two paths of length $n, n + 1$ respectively can't be distinguished by formulas of quantifier depth $log(n)$, but this of course doesn't rule out the general polylogarithmic case. That should be the idea though, picking two things which are only distinguishable by an essentially global property.  
> **username_0**: One could imagine that G and H could be equivalent in all of their local properties but aut[G] does not equal aut[H], or maybe even aut[G] = 1 or something.  
> **username_3**: @EmilJeřábek Do you have a citation for the claim about languages without equality? I would love to read that and google is failing me.  
> **username_0**: @StellaBiderman I think you can prove it by taking any graph $G$ and expanding it into a graph $G_k$ with $k$ times as many elements in its universe where before we had $(x_0, y_0) \in E_G$ now we have $(x_i, y_i)  \in E_{G_k}$ for any $i \in [k]$. Haven't went through it formally but it seems pretty clear that $G_k \vDash \varphi \Longleftrightarrow G \vDash \varphi$, as we can't really distinguish between any of the $k$ copies of $x_0$.  
> **username_1**: @StellaBiderman The truth of formulas without equality is preserved by surjective reflecting (i.e., preserving relations in both ways) homomorphisms. In the case of graphs, for example, any two graphs with no edges satisfy the same sentences. More generally, one can take any graph, and blow up any vertex into an independent set.  

---

## 1 answers

### Answer by username_4 on 2017-11-05. Score: 9 | Accepted answer

Thanks to my colleague Maxim Zhukovskii for suggesting this answer.

It turns out that the answer is negative, and the counterexample is rather simple. Just take $G=K\_m\sqcup \overline{K\_m}$ and $H=K\_{m+1}\sqcup \overline{K\_{m-1}}$ for $n=2m$ and $G=K\_m\sqcup \overline{K\_{m+1}}$ and $H=K\_{m+1}\sqcup \overline{K\_m}$ for $n=2m+1$. (Here $K\_s$ is an $s$-clique and $\overline{K\_s}$ is a set of $s$ isolated vertices). By considering the Ehrenfeucht game one can show that in the first case the minimal possible depth is $m$ and in the second case it is $m+1$.

It was shown in the paper ["The first order definability of graphs: Upper bounds for quantifier depth"](http://www.sciencedirect.com/science/article/pii/S0166218X06000989) by Oleg Pikhurko, Helmut Veith and Oleg Verbitsky that this bound is almost tight and any two $n$-vertex graphs are distinguishable by a formula of depth $\frac{n+3}{2}$.


---

