Przypuszczenie Albertsona

Nierozwiązany problem z matematyki :

Czy pełne grafy mają najmniejszą możliwą liczbę przecięć wśród grafów o tej samej liczbie chromatycznej ?

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

Kompletny wykres narysowany trzema przecięciami, najmniejsza liczba przecięć dowolnego wykresu wymagającego sześciu kolorów ${\ displaystyle K_ {6}}$

W matematyce kombinatorycznej hipoteza Albertsona jest nieudowodnionym związkiem między liczbą przecięcia a liczbą chromatyczną wykresu . Został nazwany na cześć Michaela O. Albertsona, profesora Smith College , który w 2007 roku stwierdził to jako przypuszczenie; jest to jedno z jego wielu przypuszczeń dotyczących kolorowania grafów . Przypuszczenie stwierdza, że ​​​​spośród wszystkich wykresów wymagających $kolorów$$.$ wykres tym , który ma najmniejszą liczbę przejść Równoważnie, jeśli wykres można narysować z mniejszą liczbą przecięć niż $to$ z przypuszczeniem można go pokolorować mniejszą $kolorów$ .

Przypuszczalny wzór na minimalną liczbę przejść

Łatwo jest pokazać, że grafy z ograniczoną liczbą przecięć mają ograniczoną liczbę chromatyczną: można przypisać różne kolory punktom końcowym wszystkich przecinających się krawędzi, a następnie pokolorować pozostały graf planarny 4 . Hipoteza Albertsona zastępuje tę jakościową zależność między liczbą skrzyżowań a ubarwieniem bardziej precyzyjną zależnością ilościową. W szczególności inne przypuszczenie Richarda K. Guya ( 1972 ) stwierdza, że ​​​​liczba przecięcia pełnego wykresu wynosi ${\ displaystyle K_ {n}}$

${\ Displaystyle {\ textrm {cr}} (K_ {n}) = {\ Frac {1} {4}}} {\ biggl \ lfloor} {\ Frac {n} {2}} {\ biggr \ rfloor} \ left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {n-2}{2}}\right\rfloor \left\lfloor {\frac {n-3 }{2}}\prawo\rpodłoga .}$

Wiadomo, jak rysować pełne grafy z taką liczbą przecięć, umieszczając wierzchołki w dwóch koncentrycznych okręgach; nie wiadomo, czy istnieje lepszy rysunek z mniejszą liczbą skrzyżowań. Dlatego wzmocnionym sformułowaniem hipotezy Albertsona jest to, że każdy $-chromatyczny$ ma liczbę przecięć co najmniej tak dużą, jak prawa strona tego wzoru. To wzmocnione przypuszczenie byłoby prawdziwe wtedy i tylko wtedy, gdy zarówno przypuszczenie Guya, jak i przypuszczenie Albertsona są prawdziwe.

Granice asymptotyczne

Słabsza forma przypuszczenia, udowodniona przez M. Schaefera, stwierdza, że ​​​​każdy $wykres$$przecinającą$ ( użyciu dużego notacja omega ) lub równoważnie, że każdy wykres z przecinającą się liczbą ma liczbę chromatyczną ${\ Displaystyle O (k ^ {1/4}$$)$ ) Albertson, Cranston & Fox (2009) opublikowali prosty dowód tych granic, łącząc fakt, że każdy minimalny $wykres$ ma minimalny stopień co najmniej (ponieważ inaczej ${\ displaystyle n-1}$ chciwe kolorowanie $zgodnie$ mniej kolorów) wraz z przecinającej ${\ Displaystyle | E |/| V | \ geq 4}$ z z ma numer przejścia ${\ Displaystyle \ Omega (| E | ^ {3} / | V | ^ { 2})}$ . Korzystając z tego samego rozumowania, pokazują $,$ że kontrprzykład do hipotezy Albertsona dla liczby chromatycznej $jeśli$ istnieje) musi mieć mniej .

Przypadki specjalne

Hipoteza Albertsona jest bezsensownie prawdziwa dla ${\ Displaystyle n \ równoważnik 4}$ . W takich przypadkach ${n}}$ liczbę przecięć zero, więc przypuszczenie stwierdza tylko, że wykresy -chromatyczne mają liczbę przecięć większą lub równą zeru, co jest prawdą w przypadku ${\ displaystyle n}$ wszystkie wykresy. Przypadek hipotezy Albertsona jest równoważny twierdzeniu o $czterech$ kolorach , planarny można pokolorować czterema lub mniej kolorami, dla jedynych wykresów wymagających mniejszej liczby przecięć niż jedno przecięcie ${\ displaystyle K_ {5}}$ to wykresy planarne, a przypuszczenie sugeruje, że wszystkie powinny być co najwyżej 4-chromatyczne. Dzięki wysiłkom kilku grup autorów przypuszczenie to jest obecnie znane dla wszystkich. ${\ Displaystyle n \ leq 18}$ . $koloru,$ każdej liczby $Luiz$ Richter przedstawili rodzinę pełnego wykres ${\ Displaystyle K_ {c + 1}},$ ale mieć numer przejścia co najmniej ten z ${\ Displaystyle K_ {c + 1}}$ .

Powiązane przypuszczenia

Istnieje również związek z hipotezą Hadwigera , ważnym otwartym problemem w kombinatoryce dotyczącym związku między liczbą chromatyczną a istnieniem dużych klik jako drugorzędnych na grafie. Wariant hipotezy Hadwigera, stwierdzony przez $;$ , jest taki, że każdy $-chromatyczny$ zawiera podpodział gdyby to była prawda, pojawiłaby się hipoteza Albertsona, ponieważ liczba przecięć całego grafu jest co najmniej tak duża, jak liczba przecięć któregokolwiek z jego podpodziałów. Jednak obecnie znane są kontrprzykłady hipotezy Hajósa, więc to połączenie nie zapewnia możliwości udowodnienia hipotezy Albertsona.

Notatki

•   Ackerman, Eyal (2019), „O grafach topologicznych z maksymalnie czterema przecięciami na krawędź”, Computational Geometry , 85 : 101574, 31, arXiv : 1509,01932 , doi : 10,1016/j.comgeo.2019.101574 , MR 4010251
• Albertson, Michael O.; Cranston, Daniel W.; Fox, Jacob (2009), „Zabarwienie, skrzyżowania i kliki” (PDF) , Electronic Journal of Combinatorics , 16 : R45, arXiv : 1006,3783 , Bibcode : 2010arXiv1006.3783A .
• Barát, János; Tóth, Géza (2010), „W kierunku hipotezy Albertsona” , Electronic Journal of Combinatorics , 17 (1): R73, arXiv : 0909.0413 , Bibcode : 2009arXiv0909.0413B .
• Catlin, PA (1979), „Przypuszczenie Hajósa dotyczące kolorowania wykresów: wariacje i kontrprzykłady”, Journal of Combinatorial Theory , Seria B , 26 (2): 268–274, doi : 10.1016/0095-8956 (79) 90062-5 .
• Erdős, Paweł ; Fajtlowicz, Siemion (1981), „O przypuszczeniach Hajósa”, Combinatorica , 1 (2): 141–143, doi : 10.1007 / BF02579269 .
• Guy, Richard K. (1972), „Przecinanie liczb grafów”, w: Alavi, Y .; Lizać, DR; White, AT (red.), Graph Theory and Applications: Proceedings of the Conference at Western Michigan University, Kalamazoo, Michigan, 10–13 maja 1972 , Nowy Jork: Springer-Verlag, s. 111–124 . Cytowane przez Albertsona, Cranstona i Foxa (2009) .
• Oporowski B.; Zhao, D. (2009), „Kolorowanie wykresów ze skrzyżowaniami”, Discrete Mathematics , 309 (9): 2948–2951, arXiv : math/0501427 , doi : 10.1016/j.disc.2008.07.040 .
• Luiz, Atílio; Richter, Bruce (2014), „Uwagi na temat przypuszczenia Baráta i Tótha” , Electronic Journal of Combinatorics , 21 (1): P1.57 .