Hipoteza Erdősa-Fabera-Lovásza

Przykład hipotezy Erdősa – Fabera – Lovásza : graf utworzony z czterech klik po cztery wierzchołki w każdym, z których dowolne dwa przecinają się w jednym wierzchołku, może być czterokolorowy.

W teorii grafów hipoteza Erdősa -Fabera-Lovásza jest problemem dotyczącym kolorowania grafów , nazwanym na cześć Paula Erdősa , Vance'a Fabera i László Lovásza , którzy sformułowali ją w 1972 roku. Mówi ona:

Jeśli k pełnych grafów , z których każdy ma dokładnie k wierzchołków, ma tę właściwość, że każda para pełnych grafów ma co najwyżej jeden wspólny wierzchołek, to sumę grafów można odpowiednio pokolorować k kolorami .

Dowód hipotezy dla wszystkich wystarczająco dużych wartości k został ogłoszony w 2021 roku przez Dong Yeap Kang, Tom Kelly, Daniela Kühn , Abhishek Methuku i Deryk Osthus .

Równoważne preparaty

Haddad i Tardif (2004) przedstawili problem, opowiadając o przydzielaniu miejsc w komisjach: załóżmy, że na wydziale uniwersyteckim istnieje k komisji, z których każda składa się z k członków wydziału, i że wszystkie komisje spotykają się w tym samym pokoju, co ma K krzesła. Załóżmy również, że co najwyżej jedna osoba należy do przecięcia dowolnych dwóch komitetów. Czy możliwe jest przydzielenie członków komisji do przewodniczących w taki sposób, aby każdy członek zasiadał na tym samym krześle we wszystkich różnych komisjach, do których należy? W tym modelu problemu członkowie wydziału odpowiadają wierzchołkom grafów, komitety odpowiadają kompletnym grafom, a krzesła odpowiadają kolorom wierzchołków.

Hipergraf liniowy (znany również jako częściowa przestrzeń liniowa ) to hipergraf , którego właściwość polega na tym, że każde dwa hipergrafy mają co najwyżej jeden wspólny wierzchołek. Mówimy, że hipergraf jest jednorodny, jeśli wszystkie jego hipergrafy mają taką samą liczbę wierzchołków. N klik o rozmiarze n w hipotezie Erdősa-Fabera-Lovásza można interpretować jako hiperkrawędzie n -jednorodnego hipergrafu liniowego, który ma te same wierzchołki co graf bazowy. W tym języku hipoteza Erdősa-Fabera-Lovásza stwierdza, że ​​​​dany dowolny n -jednolity hipergraf liniowy z n hiperkrawędziami można n -pokolorować wierzchołki tak, że każda hiperkrawędź ma jeden wierzchołek każdego koloru.

Prosty hipergraf to hipergraf, w którym co najwyżej jedna hiperkrawędź łączy dowolną parę wierzchołków i nie ma hiperkrawędzi o rozmiarze co najwyżej jednego. W sformułowaniu kolorowania grafów hipotezy Erdősa – Fabera – Lovásza można bezpiecznie usunąć wierzchołki należące do jednej kliki, ponieważ ich kolorowanie nie nastręcza trudności; po wykonaniu tej czynności hipergraf, który ma wierzchołek dla każdej kliki i hiperkrawędź dla każdego wierzchołka grafu, tworzy prosty hipergraf. Podwójny hipergraf kolorowania wierzchołków to kolorowanie krawędzi . Zatem hipoteza Erdősa – Fabera – Lovásza jest równoważna stwierdzeniu, że każdy prosty hipergraf z n wierzchołkami ma indeks chromatyczny (liczbę zabarwienia krawędzi) co najwyżej n .

Wykres hipotezy Erdősa – Fabera – Lovásza można przedstawić jako wykres przecięcia zbiorów: każdemu wierzchołkowi wykresu odpowiada zbiór klik zawierających ten wierzchołek i łączy dowolne dwa wierzchołki krawędzią, ilekroć ich odpowiadające zestawy mają niepuste skrzyżowanie. Korzystając z tego opisu wykresu, przypuszczenie można powtórzyć w następujący sposób: jeśli jakaś rodzina zbiorów ma n elementów, a dowolne dwa zbiory przecinają się co najwyżej w jednym elemencie, to wykres przecięcia zbiorów może być n -kolorowy.

Liczba przecięć grafu G to minimalna liczba elementów w rodzinie zbiorów, których grafem przecięcia jest G , lub równoważnie minimalna liczba wierzchołków w hipergrafie, którego grafem liniowym jest G . Klein i Margraf (2003) podobnie definiują liczbę przecięć liniowych grafu jako minimalną liczbę wierzchołków hipergrafu liniowego, którego graf liniowy to G . Jak zauważają, hipoteza Erdősa-Fabera-Lovásza jest równoważna stwierdzeniu, że liczba chromatyczna dowolnego grafu jest co najwyżej równa jego liniowemu numerowi przecięcia.

Haddad i Tardif (2004) przedstawiają inne, ale równoważne sformułowanie, jeśli chodzi o teorię klonów .

Historia, częściowe wyniki i ostateczny dowód

Paul Erdős , Vance Faber i László Lovász sformułowali nieszkodliwie wyglądającą hipotezę na przyjęciu w Boulder Colorado we wrześniu 1972 roku. Jej trudność zdawano sobie sprawę bardzo powoli. Paul Erdős pierwotnie zaoferował 50 USD za udowodnienie hipotezy twierdząco, a później podniósł nagrodę do 500 USD. W rzeczywistości Paul Erdős uważał to za jeden ze swoich trzech najbardziej ulubionych problemów kombinatorycznych.

Chiang i Lawler (1988) udowodnili, że liczba chromatyczna grafów w przypuszczeniu wynosi co najwyżej 3 k / 2 - 2 , a Kahn (1992) poprawił to do k + o ( k ) .

W 2021 roku, prawie 50 lat po postawieniu pierwotnej hipotezy, została ona rozwiązana dla wszystkich wystarczająco dużych n .

Powiązane problemy

Interesujące jest również rozważenie liczby chromatycznej grafów utworzonych jako suma k klik o k wierzchołkach w każdym, bez ograniczania tego, jak duże mogą być przecięcia par klik. W tym przypadku liczba chromatyczna ich sumy wynosi co najwyżej 1+ k √ k − 1 , a niektóre utworzone w ten sposób grafy wymagają takiej liczby kolorów.

, że wersja przypuszczenia, która używa ułamkowej liczby chromatycznej zamiast liczby chromatycznej, jest prawdziwa. Oznacza to, że jeśli graf G jest utworzony jako suma k k -kliek przecinających się parami co najwyżej w jednym wierzchołku, to G może być k -kolorowy.

W ramach kolorowania krawędzi prostych hipergrafów Hindman (1981) definiuje liczbę L z prostego hipergrafu jako liczbę wierzchołków hipergrafu, które należą do hipergrafu złożonego z trzech lub więcej wierzchołków. Pokazuje, że dla dowolnej ustalonej wartości L wystarczy skończone obliczenie, aby zweryfikować, czy hipoteza jest prawdziwa dla wszystkich prostych hipergrafów o tej wartości L . Opierając się na tym pomyśle, pokazuje, że przypuszczenie jest rzeczywiście prawdziwe dla wszystkich prostych hipergrafów z L ≤ 10 . W formułowaniu kolorujących grafów utworzonych przez związki klik, wynik Hindmana pokazuje, że przypuszczenie jest prawdziwe, gdy co najwyżej dziesięć klik zawiera wierzchołek należący do trzech lub więcej klik. W szczególności jest to prawdziwe dla n ≤ 10 .

Zobacz też

Notatki

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Erdős–Faber–Lovász_conjecture&oldid=1136215525 ”