Untuk setiap dua grafik non-isomorfik

Saya ingin menjadi sangat spesifik. Adakah yang tahu tentang penolakan atau bukti dari proposisi berikut:

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

Secara intuitif, ini harus benar jika semua grafik non-isomorfik dapat dibedakan menggunakan pernyataan " $Clog(n)^k$ lokal", dan saya akan membayangkan bahwa ini salah. Tentu saja setiap grafik dapat dibedakan menggunakan kedalaman kuantum polinomial, karena Anda dapat dengan mudah menentukan isomorfisma modulo grafik Anda:

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

Sunting: Jadi sepertinya intuisi lokal yang saya miliki adalah salah. Rumus kedalaman pengukur $k$ memiliki lokalitas Gaifman yang dibatasi oleh $O(3^k)$ , yang berarti bahwa rumus kedalaman log pada dasarnya bersifat global. Untuk alasan ini, saya punya firasat proposisi akan berubah menjadi kenyataan, yang akan jauh lebih sulit untuk dibuktikan menurut pendapat saya.

graph-theory graph-isomorphism formulas first-order-logic Samuel Schlesinger
sumber

Bagaimana dengan jalan dan dua jalan terputus yang masing-masing panjangnya

\frac{n}{2}

$\frac{n}{2}$

Samuel Schlesinger

Path hanya memiliki dua node derajat , dua path memiliki empat. Yaitu, mereka dapat dibedakan dengan formula ukuran konstan. Anda mungkin lebih beruntung dengan satu lingkaran vs dua lingkaran, tetapi saya pikir mereka dapat dibedakan dengan rumus peringkat quantifier .

1

$1$

O (\log n)

$O(\log n)$

Emil Jeřábek 3.0

Pohon-pohon tinggi mungkin berfungsi untuk sanggahan, jika mereka berbeda dekat dengan daun.

András Salamon

@ EmilJeřábek apakah itu benar tanpa kesetaraan?

Samuel Schlesinger

@StellaBiderman Kebenaran formula tanpa kesetaraan diawetkan oleh surjektif yang mencerminkan (yaitu, menjaga hubungan dengan kedua cara) homomorfisme. Dalam kasus grafik, misalnya, setiap dua grafik tanpa tepi memenuhi kalimat yang sama. Secara umum, seseorang dapat mengambil grafik apa saja, dan meledakkan simpul mana pun ke dalam set independen.

Emil Jeřábek 3.0

Terima kasih kepada kolega saya Maxim Zhukovskii yang menyarankan jawaban ini.

Ternyata jawabannya negatif, dan sampel tandingannya agak sederhana. Ambil saja dan untuk dan dan untuk . (Di sini adalah -clique dan adalah sekumpulan simpul terisolasi ). Dengan mempertimbangkan permainan Ehrenfeucht kita dapat menunjukkan bahwa dalam kasus pertama kedalaman minimal yang mungkin adalah dan dalam kasus kedua adalah . $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$

Itu ditunjukkan di koran "Urutan pertama urutan grafik: Batas atas untuk kedalaman kuantifier" oleh Oleg Pikhurko, Helmut Veith dan Oleg Verbitsky bahwa batas ini hampir ketat dan setiap dua grafik -vert dapat dibedakan dengan rumus kedalaman . $n$ $\frac{n+3}{2}$

Daniil Musatov
sumber

Untuk setiap dua grafik non-isomorfik

Jawaban: