Sensitivitas Properti Grafik

Dalam [1], Turan menunjukkan bahwa sensitivitas (disebut "kompleksitas kritis" di kertas) properti grafik benar-benar lebih besar dari manamadalah jumlah simpul dalam grafik. Dia melanjutkan dengan dugaan bahwa setiap properti grafik non-sepele memiliki sensitivitas≥m-1. Dia menyebutkan bahwa ini telah diverifikasi untukm≤5. Apakah ada kemajuan yang dibuat pada dugaan ini?$\lfloor {1\over 4} m \rfloor$$m$$\geq m-1$$m \leq 5$

Latar Belakang

Biarkan menjadi string biner dalam { 0 , 1 } n . Tentukan x i untuk 1 ≤ i ≤ n menjadi string yang diperoleh dari x dengan membalik bit i t h . Untuk fungsi boolean f : { 0 , 1 } n \ to { 0 , 1 } , tentukan sensitivitas f pada x sebagai s ( f ; $x$$\{0,1\}^n$$x^i$$1 \leq i \leq n$$x$$i^{th}$$f: \{0,1\}^n$$\{0,1\}$$f$$x$. Akhirnya, menentukansensitivitasdari f sebagai s ( f ) : = max$s(f;x) := |\{i : f(x) \neq f(x^i) \}|$$f$ .$s(f) := \mbox{max}_x\; s(f;x)$

Properti grafik adalah koleksi grafik sehingga jika G ∈ P dan G ' adalah isomorfik ke G kemudian G ' ∈ P . Kami bisa memikirkan properti grafik P sebagai penyatuan sifat P m di mana P m adalah bagian dari P yang terdiri dari grafik dengan m simpul. Selanjutnya, kita bisa membayangkan properti grafik P m sebagai fungsi boolean pada { 0 , 1 } n di mana n $\mathcal P$$G \in \mathcal P$$G'$$G$$G' \in \mathcal P$$\mathcal P$$\mathcal P_m$$\mathcal P_m$$\mathcal P$$m$$\mathcal P_m$$\{0,1\}^n$ . Kita dapat menyandikan grafik padasimpulmdalam vektor biner dengan panjangn; setiap entri dalam vektor sesuai dengan sepasang simpul dan entri adalah1jika tepi itu ada dalam grafik. Dengan demikian, sensitivitas properti grafik adalah sensitivitasnyafungsiquaboolean.$n = {m \choose 2}$$m$$n$$1$

1. Turan, G., Kompleksitas kritis properti grafik, Information Processing Letters 18 (1984), 151-153.

Survei yang ditunjuk Suresh untuk memunculkan makalah oleh Wegener [1] yang sebagian mengkonfirmasi dugaan tersebut. Ini berlaku untuk semua properti grafik monoton dan ketidaksamaannya sangat ketat (pertimbangkan properti "Tidak memiliki simpul terisolasi"). Hasil yang lebih baru akan dihargai juga.

1. Wegener, L. Kompleksitas kritis semua fungsi (monoton) Boolean dan properti grafik monoton. Informasi dan Kontrol , 67: 212-222, 1985.