The topology of solution spaces of combinatorial problems

Homomorfizm grafów to pojęcie prawie tak proste jak kolorowanie grafów, dające jednak bogatą matematyczną strukturę, która pozwala na nowe, owocne połączenia z algebrą, a nawet topologią. Dla kombinatoryków są już klasycznym zagadnieniem i choć nie tak pieczołowicie badane jak kolorowania, stanowią niemniej fundamentalne narzędzie dla głębszego ich zrozumienia. Dla informatyków zaś homomorfizmy grafów wyrażają ważną klasę problemów spełniania więzów, ilustrując wiele związanych z nimi pytań i technik.Rozprawa przedstawia nowe zastosowania topologii w teorii grafów, otrzymane przez badanie przestrzeni odpowiadających grafom oraz przestrzeni homomorfizmów między dwoma grafami. Na początek rozważana jest topologia tej drugiej w najprostszym wymiarze, to jest spójne jej składowe. Analizuję więc proces przekolorowywania czy rekonfiguracji, czyli ścieżki między homomorfizmami, gdzie kolejne homomorfizmy różnią się na jednym tylko wierzchołku. Sformułowanie naturalnego, topologicznego warunku koniecznego pozwala jednoznacznie scharakteryzować te ścieżki, wzmacniając i uogólniając znany wcześniej algorytm dla znajdowania ścieżek między 3-kolorowaniami do homomorfizmów w dowolny graf bez kwadratów (cykli długości cztery).W dalszej części badam hipotezę Hedetniemiego: pozornie proste pytanie o liczbę chromatyczną produktu grafów, które pozostaje otwarte od ponad 50 lat. Ogólniej, rozważam tzw. grafy multiplikatywne, czyli elementy pierwsze w kracie grafów (częściowo uporządkowanych relacją istnienia homomorfizmu). Związek tych zagadnień z topologią jest mniej łatwy do dostrzeżenia, ale znajduję zastosowanie dla technik podobnych jak dla rekonfiguracji. Pokazuję nowy dowód multiplikatywności dla wszystkich grafów, gdzie była ona dotychczas znana. Ponadto dowodzę, że podobnie wszystkie grafy bez kwadratów są pierwsze, daleko poszerzając tę rodzinę.Na koniec pokazuję, że hipoteza Hedetniemiego implikuje analogiczne stwierdzenie w topologii. Nowe dowody multiplikatywności unaoczniają, że bazują one na faktach o topologii jedno-wymiarowej, które do wyższych wymiarów się nie uogólniają; można więc mieć nadzieję na znalezienie topologicznych kontrprzykładów, które zaprzeczyłyby tym samym hipotezie Hedetniemiego. Z drugiej strony znaczy to, że dowód topologicznego wariantu zasadniczo powinien być prostszy, a dowód taki mógłby się stosunkowo łatwo uogólniać na przypadek grafów, tak jak ma to miejsce w obecnie znanych przypadkach. Dowodzę także, że ten topologiczny wniosek z hipotezy Hedetniemiego jest równoważny innemu, słabszemu stwierdzeniu w kombinatoryce.Te ostatnie wyniki otrzymane są dzięki konstrukcji, która stanowi pewną odwrotność (formalnie: prawe sprzężenie) do operacji brania k-tej potęgi grafu (tj. jego macierzy sąsiedztwa). Konstrukcja ta okazuje się mieć również przydatne własności topologiczne: zachowuje topologię przestrzeni odpowiadającej grafowi, a przy tym uszczegóławia jego geometrię, pozwalając na przybliżenie każdej funkcji ciągłej homomorfizmami z tak otrzymanych grafów. Powyższa implikacja hipotezy Hedetniemiego jest wtedy prostym wnioskiem, a jednocześnie otrzymuję dalekie uogólnienie twierdzenia, że rzeczona konstrukcja przyłożona do grafów pełnych zachowuje liczbę chromatyczną.Wyniki rozprawy można widzieć nie tylko jako krok w badaniach nad ważną hipotezą, ale także jako nowy rozdział na zagadkowym przecięciu kombinatoryki i topologii algebraicznej. Niemniej zamiarem autora rozprawy było również przedstawienie przystępnego wprowadzenia do niektórych połączeń między tymi dziedzinami. Ułatwia to fakt, że użyte metody polegają głównie na elementarnych definicjach z topologii, które można zrozumieć bez przesadnego wysiłku, oraz to, że następują po nich konkretne, kombinatoryczne wnioski.

Graph homomorphism is a notion almost as simple, notationally and conceptually, as graph coloring, but one that gives a rich mathematical structure, allowing for new fruitful connections with algebra and even topology. For combinatorialists, they are already a classical topic, and while not studied as thoroughly as graph coloring problems, they constitute a fundamental tool for a deeper understanding thereof. For computer scientists, graph homomorphisms express an important class of constraint satisfaction problems, exemplifying many relevant questions and techniques.This thesis presents new applications of topology to graph theory, obtained by studying spaces corresponding to graphs and spaces of homomorphisms between two graphs. First, we consider just the basic topology of the latter space, namely its connected components. That is, we study `recoloring' or `reconfiguration' paths between graph homomorphisms, defined as sequences in which consecutive homomorphism differ at only one vertex. A natural topological necessary condition is formulated, which allows to characterize the paths exactly, to strengthen a previous algorithmic result on finding paths between graph 3-colorings, and to generalize it to homomorphisms into any graph without cycles of length four.We then turn to Hedetniemi's conjecture, a deceptively simple question on the chromatic number of products of graphs, which stands open for more than 50 years. More generally, we consider multiplicative graphs, which are the `prime' elements in the lattice of graphs partially ordered by graph homomorphisms. The connection of these questions with topology is much less conspicuous, but we apply similar techniques as for reconfiguration. A new proof of the multiplicativity is shown for all graphs where it was previously known. Furthermore, all graphs without cycles of length four are similarly shown to be `prime', greatly extending this family.Finally, we show that Hedetniemi's conjecture implies an analogous statement in topology. As the new proofs of multiplicativity show, the underlying principle is based on facts in 1-dimensional topology which do not extend to higher dimensions. Therefore, one may hope to find a counterexample to the topological statement, which would thus immediately refute Hedetniemi's conjecture. On the other hand, this means that a proof in topology should be in principle easier, and could be as easy to extend to graphs as for some of the currently known cases. A partial converse is also given, in fact the topological implication of Hedetniemi's conjecture is shown to be equivalent to another, weaker combinatorial statement. These final results are obtained using a combinatorial construction that is a certain inverse (formally: the right adjoint) to taking the k-th power of a graph (or of its adjacency matrix). The construction turns out to have useful topological properties as well: it preserves the topology corresponding to a graph and refines its geometry, allowing to approximate any continuous map by homomorphisms from such refined graphs. This allows to easily prove the above implication of Hedetniemi's conjecture. It also vastly generalizes a previous result saying that the construction in question preserves the chromatic number when applied to complete graphs.Hopefully, the results will prove to be not only a significant step in a fundamental conjecture, but also a new chapter at the puzzling intersection of combinatorics and algebraic topology. However, the author also hopes this thesis to be an accessible introduction to some of the connections between these two fields. This is certainly made easier by the fact that the methods used rely mostly on elementary definitions from topology, which can be understood without much engrossment, and that concrete, purely combinatorial conclusions follow.