Jakie właściwości grafów płaskich uogólniają się na wyższe wymiary / hipergrrafy?

Płaska wykres przedstawia wykres, który może być osadzony w płaszczyźnie, bez konieczności przekraczania krawędzie.

Niech będzie - jednolitym hipergraphem, tj. Hipergraphem takim, że wszystkie jego hipergezy mają rozmiar k.$G=(X,E)$$k$

Wykonano już pewne prace związane z osadzaniem hiperrafatów w płaszczyźnie (w kontekście klastrowania lub innej aplikacji), ale często danych po prostu nie można osadzić w płaszczyźnie. Rozwiązaniem może być albo wymuszenie go, z pewną stratą, albo osadzenie go w wyższym wymiarze, jak sugeruję tutaj:

Naturalne rozszerzenie płaskości (przynajmniej IMO) to „ -proste osadzanie” (czy jest znana inna nazwa?) : embedding , takie, że istnieją powierzchnie, które łączą wszystkie wierzchołki każdego hiperge, i nie przecinają się one z wyjątkiem punktów końcowych.G M : X → R$k$$G$$\mathcal{M}:X\to \mathbb{R}^k$

(Pomyśl o analogu w 2D, gdzie każda powierzchnia jest krawędzią, którą możesz narysować w dowolny sposób).

Oto przykład prawidłowego 3-prostego osadzenia hipergrrafu 3-jednolitego. (Każdy wierzchołek jest pokolorowany przez zawarte w nim hipergezy, a każda twarz reprezentuje hipersge).

Innym przykładem 3-prostego wykresu jest pełny 3-jednolity hipergraph na 5 wierzchołkach . Aby to zobaczyć, po prostu weź 4 punkty w które nie leżą na płaszczyźnie 2D, utwórz trójkątną piramidę (ich wypukły kadłub) i umieść piąty punkt na środku piramidy, łącząc go z pozostałe wierzchołki.R$G=(V,V\times V\times V)$$\mathbb{R}^3$

Podobnie wydaje się, że pełny 3-uniform-hypergraph na 6 wierzchołkach nie ma 3-prostych osadzeń.

Istnieje kilka bardzo przydatnych właściwości grafów płaskich, które umożliwiają ulepszone algorytmy trudnych problemów, gdy wykres jest płaski. Niestety dane często nie są płaskie, choć czasem mają małą wymiarowość. Myślę, że zrozumienie, które właściwości uogólniają wykresy płaskie, pomoże nam dowiedzieć się, które algorytmy można dostosować do wyższego wymiaru za pomocą tego samego narzędzia.

Przykład właściwości, która może być przydatna, pochodzi z twierdzenia Fáry'ego, który sugeruje, że każdy płaski wykres można osadzić w taki sposób, że wszystkie jego krawędzie są segmentami linii prostych.

Czy twierdzenie Fáry'ego ma wyższy wymiar? , tj. jeśli wykres ma osadzenie -proste, to czy ma osadzenie, w którym wszystkie hiper-krawędzie są hiperpłaszczyznami?$k$

Czy są jakieś inne właściwości, które można uogólnić? na przykład, czy Formułę Eulera dla grafów płaskich można w jakiś sposób uogólnić na wyższy wymiar? (chociaż w tej chwili nie jestem pewien, co by to miało znaczyć).

Jako pierwsza uwaga, wydaje się, że skupiasz się na hipergraphach, ale myślę, że większość literatury na temat osadzania hipergraphów woli pracować z prostymi kompleksami. Dobrym odniesieniem do tych pytań jest ten artykuł Matouseka, Tancera i Wagnera.

Czy twierdzenie Fáry'ego ma wyższy wymiar?

Odpowiedź brzmi nie.

Istnieją 3 różne pojęcia osadzania: z prostymi, kawałkowo-liniowymi i ciągłymi (hiper) krawędziami. W samolocie wszystkie się pokrywają, ale ogólnie nie. Jeśli chodzi o osadzanie w linii prostej, pierwszym przeciwnym przykładem jest Brehm

Brehm, U. (1983). Niepolarny trójkątny pasek Möbiusa. Proc. Amer. Matematyka Soc., 89 (3), 519–522. doi: 10.2307 / 2045508

i kilka przykładów poszło za przykładem wyników z teorii matroidów.

O różnicy między PL a osadzeniem topologicznym wynika to z ogólnych kontrprzykładów wynikających z Hauptvermutung : W wymiarach 5 i więcej istnieją sfery topologiczne, które nie przyjmują żadnej struktury liniowo-częściowej

Czy są jakieś inne właściwości, które można uogólnić? na przykład, czy Formułę Eulera dla grafów płaskich można w jakiś sposób uogólnić na wyższy wymiar?

Możesz rzucić okiem na charakterystykę Eulera (przejście do definicji topologicznej), która łączy przemienną sumę liczby wymiarowych uproszczeń z przemienną sumą liczb betti twojego kompleksu.$k$

Podobnie wydaje się, że pełny 3-hypergraph na 6 wierzchołkach nie ma osadzania 3-prostych.

Rzeczywiście wynika to z niedrożności van Kampen-Flores. Zostało to wyjaśnione niezwykle szczegółowo i wyraźnie w książce Matouseka Korzystanie z twierdzenia Borsuka Ulama.

Oh Chcesz być bardzo, bardzo ostrożny. Wykresy kontaktowe wypukłych polytopów w 3D mogą zrealizować dowolny wykres. Zaskakująco, klika może być zrealizowana przez n polytopów, które są n obróconymi i przetłumaczonymi kopiami tego samego politopu (umysł zadziera). Zobacz ten artykuł:

http://www.cs.uiuc.edu/~jeffe/pubs/crum.html

To już oznacza, że ​​możesz zakodować dość nieprzyjemne wykresy jako wykresy przecięcia trójkątów w 3D. Zobacz część 4 tego dokumentu:

http://sarielhp.org/p/09/set_cover_hard/

BTW, jestem zainteresowany podobną wersją twojego problemu, próbując zrozumieć, jak zachowuje się wykres przecięcia geometrycznego ...

Twierdzenie Schnydera stwierdza, że ​​wykres jest płaski, a jego zasięg występowania ma co najwyżej wymiar 3. Został on rozszerzony przez Mendeza na dowolne kompleksy proste (patrz „Geometryczna realizacja kompleksów prostych”, rysowanie wykresów 1999: 323-332). O dziwo jest o wiele starszy artykuł o bardzo podobnym tytule „Geometryczna realizacja półprostego kompleksu”, ale podejrzewam, że jest na inny temat.

Bardzo ważna właściwość: dualność szerokości drzewa.

np. spójrz na: szerokość drzew hiper-grafów i dualność powierzchni Frederica Mazoita,

Streszczenie jest następujące:

W Graph Minors III Robertson i Seymour piszą: „Wygląda na to, że szerokość drzewa płaskiego wykresu i szerokość drzewa jego geometrycznego podwójnego są w przybliżeniu równe, w rzeczywistości przekonaliśmy się, że różnią się co najwyżej o jeden”. Nigdy tego nie dali. W tym artykule dowodzimy uogólnienia tego stwierdzenia do osadzania hipergraphów na ogólnych powierzchniach i dowodzimy, że nasza granica jest ścisła.

http://www.labri.fr/perso/mazoit/uploads/Surface_duality_journal.pdf