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 $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 $f$ . $s(f) := \mbox{max}_x\; s(f;x)$

Właściwość wykres jest zbiorem Diagramy takie, że jeśli i jest izomorficzny wtedy . Możemy myśleć o własności wykresu jako o połączeniu własności gdzie jest podzbiorem składającym się z wykresów o wierzchołkach. Ponadto, można wyobrazić sobie właściwości wykres jako funkcji logicznej w , gdzie $\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 nawierzchołkach w binarnym wektorze o długości; każdy wpis odpowiada w wektor do pary wierzchołków i wejście jestIFF 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$

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

graph-theory property-testing

— mum
źródło

Czy widziałeś ankietę 2002 Buhrmana i de Wolfa ( homepages.cwi.nl/~rdewolf/publ/qc/dectree.ps )? nie odpowiada bezpośrednio na twoje pytanie, ale zawiera więcej informacji na temat czułości funkcji w ogólności, a także właściwości wykresu monotonicznego.

— Suresh Venkat

wymaga kodowania

bitów

((\binom{m}{2}) + 1) \log m

$(\binom{m}{2}+1)\log m$

— Diego de Estrada

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.

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

— mum
źródło