Przypuszczenie GNRS

Nierozwiązany problem z matematyki :

$zamkniętych$ drugorzędnych mają z ograniczonymi zniekształceniami?

(więcej nierozwiązanych problemów z matematyki)

W informatyce teoretycznej i geometrii metrycznej hipoteza GNRS łączy teorię drugorzędnych grafów , współczynnik rozciągania osadzania i współczynnik aproksymacji problemów przepływu wielu towarów . Jej nazwa pochodzi od Anupama Gupty, Ilana Newmana, Jurija Rabinowicza i Alistaira Sinclaira , którzy sformułowali ją w 2004 roku.

Sformułowanie

Jedno sformułowanie hipotezy obejmuje osadzenie najkrótszych odległości ścieżek ważonych grafów niekierowanych w $.$ odległość , rzeczywistych przestrzeniach wektorowych, między dwoma wektorami jest sumą ich różnic współrzędnych Jeśli osadzanie odwzorowuje wszystkie pary wierzchołków z odległością $re , do re ] {\ Displaystyle [cd, Cd]}$ pary wektorów z odległością z zakresu $\ Displaystyle [cd, Cd]},$ to jego współczynnik rozciągnięcia lub zniekształcenie jest stosunkiem [ do ${\ Displaystyle C / c}$ ; izometria ma współczynnik rozciągania jeden, a wszystkie inne osadzenia mają większy współczynnik rozciągania .

Grafy, które mają osadzenie z co najwyżej danym zniekształceniem, są zamknięte podrzędnymi operacjami grafu , operacjami, które usuwają wierzchołki lub krawędzie z grafu lub zawężają niektóre jego krawędzie. $,$ że ​​​​odwrotnie, każda mała domknięta rodzina grafów, inna niż rodzina wszystkich grafów, może być osadzona w przestrzeni z ograniczonym zniekształceniem. Oznacza to, że zniekształcenie grafów w rodzinie jest ograniczone stałą, która zależy od rodziny, ale nie od poszczególnych grafów. Na przykład grafy planarne są zamknięte pod nieletnimi. Dlatego z hipotezy GNRS wynikałoby, że grafy planarne mają ograniczone zniekształcenia.

Alternatywne sformułowanie obejmuje analogie twierdzenia o maksymalnym przepływie i minimalnym odcięciu dla problemów z nieukierunkowanym przepływem wielu towarów . Stosunek maksymalnego przepływu do minimalnego odcięcia w takich problemach jest znany jako przerwa między przepływem a odcięciem . Największa przerwa w przepływie, jaką może mieć problem z przepływem na danym wykresie, jest równa zniekształceniu $wykresu$ . Dlatego hipotezę GNRS można przeformułować jako stwierdzającą, że rodziny grafów z mniejszymi domknięciami mają ograniczoną szczelinę przepływu.

Powiązane wyniki

Arbitralne $grafy$$wierzchołków ($$O(\log n)}$ rzeczywistości dowolne -punktowe przestrzenie metryczne mają osadzenia ze zniekształceniami $\ displaystyle n}$$_ {1}$ . Niektóre wykresy mają logarytmiczną lukę odcięcia przepływu, w szczególności dotyczy to przepływu wielu towarów, w którym każda para wierzchołków ma równe zapotrzebowanie na wykres ekspandera o ograniczonym stopniu . Dlatego to logarytmiczne ograniczenie zniekształcenia dowolnych wykresów jest ścisłe. Wykresy planarne można osadzać z mniejszymi zniekształceniami. ${\ Displaystyle O ({\ sqrt {\ log n}})}$ .

Chociaż hipoteza GNRS pozostaje nierozwiązana, udowodniono, że dla niektórych rodzin grafów z mniejszymi zamkniętymi grafami istnieją osadzenia z ograniczonymi zniekształceniami. Należą do nich $wykresy$ -outerplanar szeregowo-równoległe i wykresy rang obwodu ograniczonego , wykresy ograniczonej szerokości ścieżki , sumy 2-kliki grafów o ograniczonym rozmiarze oraz .

$\ ell _ {2}}$ do zachowania osadzeń metrycznych w przestrzeniach, każda skończona przestrzeń ma osadzenia w $Displaystyle$ z rozciągnięciem dowolnie zbliżonym do jednego przez $Lemat$ Johnsona-Lindenstraussa i do z rozciągnięciem dokładnie jeden przez o małej rozpiętości .

Zobacz też

• Sześcian częściowy , klasa wykresów z nieważonymi zniekształceniami bez zniekształceń ${\ Displaystyle \ ell _ {1}} -$ osadzania