Czułość właściwości wykresu

W [1] Turan pokazuje, że czułość (zwana w dokumencie „złożonością krytyczną”) właściwości wykresu jest ściśle większa niż $\lfloor {1\over 4} m \rfloor$gdzie$m$jest liczbą wierzchołków na wykresie. Dalej zakłada, że ​​każda nietrywialna właściwość graficzna ma czułość$\geq m-1$. Wspomina, że ​​zostało to zweryfikowane dla. Czy poczyniono jakieś postępy w tej hipotezie?$m \leq 5$

tło

Niech będzie ciągiem binarnym w . Zdefiniuj dla jako ciąg uzyskany z przez odwrócenie bitu . Dla funkcji boolowskiej \ to zdefiniuj czułość at jako s ( f ; x ) : = | { i : f ( x ) ≠ f ( x i ) } |{ 0 , 1 } n x i 1 ≤ i ≤ n x i t h f : { 0 , 1 } n { 0 , 1 } f x$x$$\{0,1\}^n$$x^i$$1 \leq i \leq n$$x$$i^{th}$$f: \{0,1\}^n$$\{0,1\}$$f$$x$$s(f;x) := |\{i : f(x) \neq f(x^i) \}|$. Wreszcie, określenia wrażliwości na w postaci S ( f ) : = max$f$ .$s(f) := \mbox{max}_x\; s(f;x)$

Właściwość wykres jest zbiorem Diagramy takie, że jeśli G ∈ P i G " jest izomorficzny G wtedy G ' ∈ P . Możemy myśleć o własności wykresu P jako o połączeniu własności P m, gdzie P m jest podzbiorem P składającym się z wykresów o m wierzchołkach. Ponadto, można wyobrazić sobie właściwości wykres P m jako funkcji logicznej w { 0 , 1 } n , gdzie 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$ . Możemy zakodować wykres namwierzchołkach w binarnym wektorze o długościn; każdy wpis odpowiada w wektor do pary wierzchołków i wejście jest1IFF krawędź ma w wykresie. Zatem czułość właściwości wykresu to jej czułośćquaboolean.$n = {m \choose 2}$$m$$n$$1$

1. Turan, G., Krytyczna złożoność właściwości grafów, Information Processing Letters 18 (1984), 151-153.

Badanie, na które wskazał Suresh, przywołuje artykuł Wegenera [1], który częściowo potwierdza przypuszczenie. Dotyczy wszystkich właściwości wykresu monotonicznego, a nierówność jest niewielka (rozważ właściwość „Nie ma izolowanych wierzchołków”). Docenione zostaną również wszelkie nowsze wyniki.

1. Wegener, L. Krytyczna złożoność wszystkich (monotonicznych) funkcji boolowskich i właściwości grafu monotonicznego. Information and Control , 67: 212-222, 1985.