W kombinatoryce i informatyce istnieje wiele przykładów, w których możemy analizować problem teoretyczny na wykresach, ale w przypadku analogu hipergrraficznego problemu brakuje naszych narzędzi. Jak myślisz, dlaczego problemy często stają się znacznie trudniejsze w przypadku 3-jednolitych hiperrafów niż w przypadku 2-jednolitych wykresów? Jakie są podstawowe trudności?
Jedną kwestią jest to, że do tej pory nie mamy zadowalającego zrozumienia teorii spektralnej hipergrafii. Rzuć więcej światła na ten problem. Ale szukam również innych powodów, które sprawiają, że hipergrrafy są trudniejszymi obiektami.
Odpowiedzi:
W tym pytaniu rozumiem, że „trudność” odnosi się nie do „trudnego do obliczenia”, ale do „trudnego do nauki”.
Problemy z grafem są łatwiejsze (przynajmniej dla mnie) do studiowania, ponieważ niektóre pojęcia są równoważne. Innymi słowy, jeśli chcesz uogólnić pytania dotyczące grafów do pytań dla hipergraphów, musisz zwrócić uwagę na „właściwe” uogólnienie, aby uzyskać pożądaną konsekwencję.
Rozważmy na przykład drzewo. W przypadku wykresów wykres jest drzewem, jeśli jest połączone i nie zawiera cyklu. Jest to równoważne z połączeniem i posiadaniem krawędzi n-1 (gdzie n jest liczbą wierzchołków), a także równoważne z brakiem cyklu i posiadaniem krawędzi n-1. Jednak w przypadku hipergraphów 3-jednolitych, powiedzmy, że hipergraph 3-jednolitych jest drzewem, jeśli jest połączone i nie zawiera cyklu. Ale to nie jest równoznaczne z byciem połączonym i posiadaniem n-1 hipergezy, ani nie zawieraniem żadnego cyklu i posiadaniem n-1 hipergege.
Słyszałem, że główną trudnością w udowodnieniu, że lemat o regularności dla jednolitych hipergraphów było wymyślenie właściwych definicji regularności i powiązanych pojęć.
Jeśli chcesz rozważyć „spektralną teorię hipergraphu”, możesz spróbować przyjrzeć się tensorom lub homologii, jeśli widzisz hipergraph k-uniform jako (k-1) wymiarowy kompleks uproszczony, z którego naturalnie powstaje algebra liniowa. Nie wiem, które jest „właściwe” uogólnienie dla twojego celu, lub możliwe, że żadne z nich nie jest właściwe.
źródło
Myślę, że jest to w dużej mierze spowodowane „mistyczną mocą twonessy” Lawlera (obserwacja, że wiele sparametryzowanych problemów występuje w P dla param = 2 i NP-zupełny dla param≥3). Wykres to rzecz, która łączy 2 krotki wierzchołków, a hypergraph to rzecz, która łączy k-krotność wierzchołków dla k≥3.
Tak więc np. 2-SAT występuje w P i jest zasadniczo problemem grafowym, podczas gdy 3-SAT stanowi problem na 3-jednolitych hipergraphach i jest NP-kompletny.
źródło
Innym powodem jest to, że mamy znacznie więcej wiedzy na temat relacji binarnych niż jakiekolwiek inne relacje n-ary dla n większych niż 2.
Oczywiście bierzemy pod uwagę relacje binarne między obiektami, takie jak przyleganie, niepuste przecięcie, równoważność itp. Możemy więc zdefiniować wykresy w kategoriach relacji binarnych, a nawet zdefiniować wykres oparty na pewnej relacji binarnej na innym wykresie. (Na przykład wykresy liniowe, kliki, rozkład drzew ...)
Ale jeśli chodzi o inne relacje n-ary, nie rozumiemy zbyt wiele. Na przykład znalezienie interesującej relacji trójskładnikowej zajmuje trochę czasu; (Okej, częściowo z powodu mojej niewiedzy) właściwości są słabsze, a narzędzia znacznie mniejsze w badaniu relacji trójskładnikowych. (Jak definiujemy symetryczne lub przechodnie relacje trójskładnikowe? Oba są jednymi z najważniejszych związków, jakie można studiować.)
Ale wciąż nie wiem, dlaczego tak się dzieje między relacjami binarnymi i trójskładnikowymi. Być może, jak powiedział turkistany, to pytanie jest trudne i może być związane ze zrozumieniem problemu P / NP.
źródło
Najpierw chciałem odpowiedzieć na złe pytanie: „który przykład problemów jest znacznie trudniejszy w hipergrrafach niż w grafach”. Byłem pod szczególnym wrażeniem różnicy w radzeniu sobie z problemem maksymalnego dopasowania na wykresach, tak samo z hipergraphami (zestawem par rozłącznych krawędzi), które bardzo łatwo mogą modelować kolorowanie, maks. Zestaw niezależny, maks. Klika ...
Potem zauważyłem, że to nie było twoje pytanie: „jakie są podstawowe trudności między nimi dwoma?”.
Cóż, na to odpowiedziałbym, że do tej pory nie widziałem wielu wspólnych punktów między wykresami a hipergraphami. Z wyjątkiem samej nazwy. I fakt, że wiele osób próbuje „rozszerzyć” wyniki od pierwszego do drugiego.
Miałem okazję przewracać strony „Hypergraphów” Berge i „Systemów” Bollobasa: zawierają one wiele smacznych wyników, a te, które uważałem za najbardziej interesujące, miały niewiele do powiedzenia na temat wykresów. Na przykład twierdzenie Baranyai (jest dobry dowód w książce Jukny).
Nie znam ich zbyt wiele, ale myślę teraz o problemie z hipergraphem i wszystko, co mogę o tym powiedzieć, to to, że nie czuję nigdzie żadnego wykresu. Być może uważamy je za „trudne”, ponieważ staramy się je badać przy użyciu niewłaściwych narzędzi. Nie spodziewam się, że problemy z grafem, nad którymi pracuję, znikną natychmiast po zastosowaniu teorii liczb (chociaż czasem się zdarza).
Aha i coś jeszcze. Być może trudniej je studiować, ponieważ są kombinatorycznie dużo ... więcej?!
„wypróbuj je wszystkie i przekonaj się, kiedy to działa” jest czasem dobrym pomysłem na wykresy, ale w przypadku hipergraphów szybko upada liczba. :-)
źródło