Naturalne, niestabilne właściwości wykresu

Podczas testowania właściwości wykresu algorytm wysyła zapytanie do wykresu docelowego o obecność lub brak krawędzi i musi ustalić, czy cel ma określoną właściwość, czy też jest -far od posiadania tej właściwości. (Algorytm może zostać poproszony o powodzenie z błędem 1-stronnym lub 2-stronnym.) Wykres ma -far od posiadania właściwości, jeśli nie można dodać / odjąć krawędzi \ epsilon \ binom {n} {2}, aby utworzyć ma właściwość.$\epsilon$$\epsilon$$\epsilon \binom{n}{2}$

Mówi się, że właściwość jest testowalna, jeśli można ją przetestować w sposób określony powyżej w subliniowej liczbie zapytań lub jeszcze lepiej w szeregu zapytań niezależnych od $n$ (ale nie $\epsilon$ ). Pojęcie tego, jakie są właściwości, można również sformalizować, ale powinno być jasne.

Istnieje wiele wyników charakteryzujących właściwości, które można testować, z wieloma przykładami naturalnych właściwości testowalnych. Nie jestem jednak świadomy wielu naturalnych właściwości, o których wiadomo, że nie są testowalne (powiedzmy w stałej liczbie zapytań) - jednym z nich jest testowanie izomorfizmu na danym wykresie.

Moje pytanie brzmi zatem: jakie naturalne właściwości grafu nie są testowalne?

W modelu macierzy przylegania istnieje dolna granica w złożoności zapytania sprawdzania, czy wykres wierzchołków składa się z dwóch izomorficznych kopii niektórych wykresów odwróconych (patrz Wprowadzenie do testowania właściwości wykresu - Goldreich do ankiety).$\Omega(n)$$n$$n/2$

Ponadto istnieje wiele dolnych granic, które zależą od dla testerów z jednostronnym błędem, np .: testowanie -Clique, -Cut i -Bisection (patrz Testowanie właściwości i jego związek z uczeniem się i przybliżaniem - Goldreich , Goldwasser, Ron )$n$$\rho$$\rho$$\rho$

Ponadto w modelu grafu z ograniczonym stopniem testowanie 3-kolorowalności wymaga zapytań , podczas gdy testowanie 2-kolorowalności (tj. Dwustronność) wymaga (patrz Testowanie właściwości w grafach stopni ograniczonych - Goldreich, Ron ).$\Omega(n)$$\Omega(\sqrt n)$