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

12

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

pZ[x],n,k,CN,

G,HSTRUC[Σgraph](min(|G|,|H|)=n,GH),

φL(Σgraph),

|φ|p(n)qd(φ)Clog(n)kGφHφ.

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:

φ=x1x2x3...xn(x(iVGx=xi)((i,j)EGE(xi,xj)))((i,j)EG¬E(xi,xj)))((i,j)VG2ijxixj).

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(3k) , 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.

Samuel Schlesinger
la source
Qu'en est-il du chemin et de deux chemins déconnectés de longueurn2
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 . 1O(logn)
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
1
@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

Réponses:

9

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=KmKm¯H=Km+1Km1¯n=2mG=KmKm+1¯H=Km+1Km¯n=2m+1KssKs¯smm+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 .nn+32

Daniil Musatov
la source