Para cualquiera de los dos gráficos no isomórficos

Quiero ser muy específico ¿Alguien sabe de una prueba o prueba de la siguiente propuesta:

$\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.$

Intuitivamente, esto debería ser cierto si todos los gráficos no isomórficos se pueden distinguir usando las declaraciones " local", y me imagino que esto es falso. Por supuesto, cualquier gráfico se puede distinguir usando la profundidad del cuantificador polinómico, ya que simplemente puede especificar el isomorfismo de su módulo de gráfico:$Clog(n)^k$

$\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).$

Editar: Entonces parece que la intuición de la localidad que tenía es falsa. Una fórmula de cuantificador de profundidad tiene la localidad de Gaifman limitada por , lo que significa que una fórmula de profundidad logarítmica es básicamente global. Por esta razón, tengo el presentimiento de que la propuesta resultará cierta, lo que sería mucho más difícil de probar en mi opinión.$k$$O(3^k)$

Gracias a mi colega Maxim Zhukovskii por sugerir esta respuesta.

Resulta que la respuesta es negativa y el contraejemplo es bastante simple. Simplemente tome y para y y para . (Aquí es una -clique y es un conjunto de vértices aislados). Al considerar el juego Ehrenfeucht, se puede demostrar que en el primer caso la profundidad mínima posible es en el segundo caso es . H = K m + 1 ⊔ ¯ K m - 1 n = 2 m G = K m ⊔ ¯ K m + 1 H = K m + 1 ⊔ ¯ K m n = 2 m + 1 K s s ¯ K s s m m + $G=K_m\sqcup \overline{K_m}$$H=K_{m+1}\sqcup \overline{K_{m-1}}$$n=2m$$G=K_m\sqcup \overline{K_{m+1}}$$H=K_{m+1}\sqcup \overline{K_m}$$n=2m+1$$K_s$$s$$\overline{K_s}$$s$$m$$m+1$

Se ha demostrado en el documento "El primero definibilidad orden de gráficos: Upper límites para la profundidad cuantificador" por Oleg Pikhurko, Helmut Veith y Oleg Verbitsky que este límite es casi apretada y cualesquiera dos -vertex gráficos son distinguibles por una fórmula de profundidad .n + $n$$\frac{n+3}{2}$