Pour deux graphes non isomorphes , existe-t-il une formule de premier ordre de profondeur de quantificateur polysize et polylog qui en témoigne?

Je veux être très précis. Quelqu'un connaît-il un rejet ou une preuve de la proposition suivante:

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

Intuitivement, cela devrait être vrai si tous les graphiques non isomorphes peuvent être distingués à l'aide des instructions " $Clog(n)^k$ local", et j'imagine que c'est faux. Bien sûr, tout graphique peut être distingué en utilisant la profondeur du quantificateur polynomial, car vous pouvez simplement spécifier votre isomorphisme modulo graphique:

$\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: Il semble donc que l'intuition de la localité que j'ai eue est fausse. Une formule de profondeur de quantificateur $k$ a une localité de Gaifman délimitée par $O(3^k)$ , ce qui signifie qu'une formule de profondeur de log est essentiellement globale. Pour cette raison, j'ai le pressentiment que la proposition se révélera vraie, ce qui serait beaucoup plus difficile à prouver à mon avis.

graph-theory graph-isomorphism formulas first-order-logic Samuel Schlesinger
la source

Qu'en est-il du chemin et de deux chemins déconnectés de longueur

\frac{n}{2}

$\frac{n}{2}$

Samuel Schlesinger

Le chemin n'a que deux nœuds de degré , deux chemins en ont quatre. C'est-à-dire qu'ils peuvent être distingués par une formule de taille constante. Vous pouvez avoir plus de chance avec un cercle contre deux cercles, mais je pense qu'ils peuvent être distingués par une formule de quantificateur de rang .

1

$1$

O (\log n)

$O(\log n)$

Emil Jeřábek

Les grands arbres pourraient servir de réfutation s'ils diffèrent près des feuilles.

András Salamon

@ EmilJeřábek est-ce vrai sans égalité?

Samuel Schlesinger

@StellaBiderman La vérité des formules sans égalité est préservée par les homomorphismes surjectifs reflétant (c'est-à-dire préservant les relations dans les deux sens). Dans le cas des graphiques, par exemple, deux graphiques sans bords satisfont aux mêmes phrases. Plus généralement, on peut prendre n'importe quel graphe et faire exploser n'importe quel sommet en un ensemble indépendant.

Emil Jeřábek

Merci à mon collègue Maxim Zhukovskii d'avoir proposé cette réponse.

Il s'avère que la réponse est négative et que le contre-exemple est plutôt simple. Prenez simplement et pour et et pour . (Ici est une -clique et est un ensemble de sommets isolés). En considérant le jeu Ehrenfeucht, on peut montrer que dans le premier cas la profondeur minimale possible est et dans le second cas elle est . $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$

Il a été montré dans l'article "La définissabilité du premier ordre des graphiques: limites supérieures pour la profondeur du quantificateur" par Oleg Pikhurko, Helmut Veith et Oleg Verbitsky que cette limite est presque serrée et que deux graphiques vertex quelconques peuvent être distingués par une formule de profondeur . $n$ $\frac{n+3}{2}$

Daniil Musatov
la source

Pour deux graphes non isomorphes , existe-t-il une formule de premier ordre de profondeur de quantificateur polysize et polylog qui en témoigne?

Réponses: