Para quaisquer dois gráficos não isomórficos

Eu quero ser muito específico. Alguém sabe de uma reprovação ou de uma prova da seguinte proposição:

$\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, isso deve ser verdade se todos os gráficos não isomórficos puderem ser distinguidos usando as instruções " $Clog(n)^k$ local", e eu imagino que isso seja falso. É claro que qualquer gráfico pode ser distinguido usando a profundidade do quantificador polinomial, pois você pode simplesmente especificar o isomorfismo do módulo de gráfico:

$\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: Então parece que a intuição de localidade que tive é falsa. Uma fórmula da profundidade do quantificador $k$ tem a localidade de Gaifman delimitada por $O(3^k)$ , o que significa que uma fórmula de profundidade do log é basicamente global. Por esse motivo, tenho um pressentimento de que a proposição se tornará verdadeira, o que seria muito mais difícil de provar na minha opinião.

Agradeço ao meu colega Maxim Zhukovskii por sugerir esta resposta.

Acontece que a resposta é negativa e o contra-exemplo é bastante simples. Basta pegar e por e e para . (Aqui é uma classe e é um conjunto de vértices isolados). Considerando o jogo de Ehrenfeucht, pode-se mostrar que no primeiro caso a profundidade mínima possível é e no segundo caso é . H = K m + 1 ⊔ ¯ K m - 1 n = 2 m L = 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$

Foi mostrado no artigo "A definibilidade de primeira ordem dos gráficos: limites superiores para a profundidade do quantificador", de Oleg Pikhurko, Helmut Veith e Oleg Verbitsky, que esse limite é quase rígido e quaisquer dois gráficos vertex são distinguíveis por uma fórmula de profundidade .n + $n$$\frac{n+3}{2}$