Globalne właściwości klas dziedzicznych?

Dziedziczna klasa struktur (np. Wykresy) to taka, która jest zamknięta pod indukowaną podbudową, lub równoważnie, jest zamknięta pod usunięciem wierzchołków.

Klasy wykresów, które wykluczają nieletnie, mają ładne właściwości, które nie zależą od konkretnej wykluczonej nieletniej. Martin Grohe wykazał, że dla klas grafów z wyłączeniem drobnych istnieje algorytm wielomianowy dla izomorfizmu, a logika stałoprzecinkowa z liczeniem przechwytuje czas wielomianowy dla tych klas grafów. (Grohe, definiowalność punktu stałego i czas wielomianowy na wykresach z małymi wykluczonymi , LICS, 2010.) Można je uznać za właściwości „globalne”.

Czy istnieją podobne „globalne” właściwości znane klasom dziedzicznym (wykresy lub bardziej ogólne struktury)?

Byłoby dobrze, gdyby każda odpowiedź koncentrowała się tylko na jednej konkretnej nieruchomości.

Dziedziczne właściwości są bardzo „solidne” w następującym znaczeniu.

Noga Alon Asaf Shapira wykazały , że dla każdego dziedzicznych właściwości , jeśli wykres G potrzebuje więcej niż ε n 2 krawędzie mogą być dodawane lub usuwane w celu spełnienia P , to jest subgraph w G , o rozmiarze co najwyżej f P ( ε ) , która nie spełnia P . Tutaj funkcja f zależy tylko od właściwości P (a nie na przykład od wielkości wykresu G ). Erdős dokonał takiego przypuszczenia tylko o właściwości k -kolorowności.${\cal P}$$G$$\epsilon n^2$${\cal P}$$G$$f_{\cal P}(\epsilon)$${\cal P}$$f$${\cal P}$$G$$k$

Rzeczywiście, Alon i Shapira dowodzą następującego silniejszego faktu: biorąc pod uwagę , dla dowolnego ϵ w ( 0 , 1 ) , istnieją N ( ϵ ) , h ( ϵ ) i δ ( ϵ ) takie, że jeśli wykres G ma co najmniej N wierzchołki i potrzebuje co najmniej ϵ n 2 krawędzi dodanych / usuniętych w celu zaspokojenia P , a następnie dla co najmniej δ ułamka indukowanych podgrafów na h wierzchołkach, indukowany podgraf narusza${\cal P}$$\epsilon$$(0,1)$$N(\epsilon)$$h(\epsilon)$$\delta(\epsilon)$$G$$N$$\epsilon n^2$${\cal P}$$\delta$$h$ . Zatem jeśli ϵ i właściwość${\cal P}$$\epsilon$ są stałe, w celu sprawdzenia, czy wykres wejściowy spełnia${\cal P}$${\cal P}$lub jest daleko od spełnienia P , wówczas wystarczy tylko zapytać o krawędzie losowo wywołanego podgrupy o stałym rozmiarze z wykresu i sprawdzić, czy spełnia on właściwość, czy nie. Taki tester zawsze akceptowałby satysfakcjonujące wykresy$\epsilon$${\cal P}$ i odrzuci wykresy ε -far od wykonania go ze stałym prawdopodobieństwa. Co więcej, każda własność, którą można jednostronnie przetestować w tym sensie, jest własnością dziedziczną! Szczegółowe informacje można znaleźć w artykule Alona i Shapiry.${\cal P}$$\epsilon$

To może nie być dokładnie to, co miałeś na myśli, ale znane są ograniczenia dotyczące liczby wykresów na wierzchołkach w dziedzicznej klasie wykresów. Na przykład nie ma dziedzicznej klasy grafów, która miałaby od 2 Ω ( n ) do 2 o ( $n$$2^{\Omega(n)}$ wykresów nanwierzchołkach.$2^{o(n\log{n})}$$n$

Odniesienia: E. Scheinerman, J. Zito, O wielkości dziedzicznych klas wykresów, Journal of Combinatorial Theory Series B

Jest to związane z odpowiedzią Travisa. W rzeczywistości można go uznać za silniejszą wersję.

Papieru przez Bollob \ 'jak i Thomason (Combinatorica 2000) wynika, że w Erd \ H {o} sR \' enyi losowe wykresy (o p pewnej ustalonej stałej), każda właściwość dziedziczne może być aproksymowane przez to, co nazwać podstawową właściwość. Podstawowy prawie oznacza wykresy, których zbiory wierzchołków są związkami klas r , których s obejmują kliki, a r - s obejmują zbiory niezależne, ale niezupełnie. To przybliżenie służy do scharakteryzowania wielkości największego zestawu P, a także $G_{n,p}$$p$$r$$s$$r-s$$\mathcal{P}$$\mathcal{P}$ liczbę -chromatic z , gdzie P jest pewną stałą własnością dziedziczną. Jeślipmoże się zmieniać, zachowanie nie jest dobrze zrozumiane.$G_{n,p}$$\mathcal{P}$$p$

Więcej informacji na temat tej i powiązanych prac znajduje się w ankiecie przeprowadzonej przez Bollob \ 'as (Proceedings of the ICM 1998), która zawiera również kuszącą hipotezę w tym zakresie, ale w przypadku hipergraphów.

Uważam, że głęboki związek między własnościami dziedzicznymi a Lemem Szeme'a Regularności jest bardzo intrygujący, ponieważ został użyty zarówno tutaj, jak i w wyniku Alona i Shapiry.

Odpowiedź Suresha na temat przypuszczenia AKR skłoniła mnie do myślenia o tym samym przypuszczeniu dotyczącym własności dziedzicznych. Myślę, że (chyba że popełniłem błąd) mogę pokazać, że wszystkie nietrywialne własności dziedziczne mają (losową i deterministyczną) złożoność drzewa decyzyjnego , co ustala przypuszczenie AKR dla takich właściwości (aż do stałych).$\Theta(n^2)$

Próbowałem przeszukać literaturę, aby zobaczyć, czy gdzieś to pokazano, ale nie mogłem znaleźć odniesienia. Więc albo nie mogłem go znaleźć, ale istnieje, albo twierdzenie jest nieciekawe, albo popełniłem błąd.

Jest to kolejny przykład globalnej właściwości wszystkich dziedzicznych właściwości grafu.

$\Omega(n^c)$$c>0$

Jest to kierunek „odwrotny”, ale dobrze znana hipoteza Aanderaa-Rosenberg-Karp stosuje się do właściwości wykresu, które są monotoniczne w górę (tj. Jeśli G spełnia tę właściwość, to również wykres na tych samych węzłach, których zestaw krawędzi zawiera E (G )).