Существуют ли для любых двух неизоморфных графов

Я хочу быть очень конкретным. Кто-нибудь знает опровержение или доказательство следующего предложения:

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

Интуитивно понятно, что это должно быть правдой, если все неизоморфные графы можно различить с помощью операторов « local», и я думаю, что это неверно. Конечно, любой граф можно отличить, используя глубину полиномиального квантификатора, так как вы можете просто указать свой граф по модулю изоморфизма:$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).$

Изменить: Так что кажется, что интуиция местности у меня была ложная. Формула квантификатора глубины имеет локальность Гайфмана, ограниченную O ( 3 k ) , что означает, что формула логарифмической глубины в основном глобальная. По этой причине у меня есть предчувствие, что предложение окажется верным, что, на мой взгляд , будет гораздо сложнее доказать.$k$$O(3^k)$

Спасибо моему коллеге Максиму Жуковскому за предложенный ответ.

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

$n$$\frac{n+3}{2}$