Czy dla dowolnych dwóch grafów nieizomorficznych

Chcę być bardzo konkretny. Czy ktoś wie o odrzuceniu lub dowodzie następującej propozycji:

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

Intuicyjnie powinno to być prawdą, jeśli wszystkie grafy nieizomorficzne można rozróżnić za pomocą instrukcji „ $Clog(n)^k$ local”, i wyobrażam sobie, że to nieprawda. Oczywiście każdy wykres można rozróżnić za pomocą wielomianowej głębokości kwantyfikatora, ponieważ można po prostu określić wykres izomorfizmu modulo:

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

Edycja: Wygląda więc na to, że intuicja lokalizacji była fałszywa. Wzór głębokości kwantyfikatora $k$ ma lokalizację Gaifmana ograniczoną przez $O(3^k)$ , co oznacza, że ​​formuła głębokości logarytmicznej jest zasadniczo globalna. Z tego powodu mam przeczucie, że ta propozycja okaże się prawdziwa, co moim zdaniem byłoby znacznie trudniejsze do udowodnienia.

Dziękuję mojemu koledze Maximowi Żukowskiemu za zasugerowanie tej odpowiedzi.

Okazuje się, że odpowiedź jest przecząca, a kontrprzykład jest raczej prosty. Wystarczy wziąć i dla i i dla . (Tutaj to -klatka, a to zestaw izolowanych wierzchołków). Rozważając grę Ehrenfeucht, można pokazać, że w pierwszym przypadku minimalna możliwa głębokość wynosi aw drugim przypadku jest to . 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$

W pracy „ Oleg Pikhurko, Helmut Veith i Oleg Verbitsky ” w artykule „Definiowalność grafów pierwszego rzędu: górne granice głębokości kwantyfikatora” wykazano, że granica ta jest prawie ścisła, a dowolne dwa odwrotne wykresy można odróżnić formułą głębokości .n + $n$$\frac{n+3}{2}$