A course in topological combinatorics (Q2431276)

Topological combinatorics is concerned with the applications of the many powerful techniques of algebraic topology to problems in combinatorics. One of its landmarks is [\textit{L. Lovász}, J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)], which gave an elegant proof of Kneser conjecture [\textit{Martin Kneser}, Aufgabe 360, Jahresbericht der Deutschen Mathematiker-Vereinigung 58, No. 2, 27 (1955)] by exploiting [\textit{K. Borsuk}, Fundam. Math. 20, 177--190 (1933; Zbl 0006.42403; JFM 59.0560.01)]. The present book aims to give a clear and vivid presentation of some of the most beautiful and accessible results from the area. The text, based upon some courses by the author at Freie Universität Berlin, is designed for an advanced undergraduate student. The book consists of 9 chapters, the first four of which being intended for main topics while the remaining five being concerned with appendices. The first chapter deals with envy-free fair and consensus divisions, which lead to two distinct topological tools, namely, Brouwer's fixed point theorem and the theorem of Borsuk and Ulam, which turn out to have combinatorial analogues called the lemma of Spencer and that of Tucker. The second chapter is concerned with Kneser conjecture settled by Lovász, as mentioned above. ``Lovász associated a simplical complex to a graph in such a way that the topology of the complex provides some information about the chromatic number of the graph, therefore transforming a discrete problem into a topological one.'' The third chapter is based upon [\textit{M. Aigner}, Combinatorial search. Wiley-Teubner Series in Computer Science. Stuttgart (FRG): B. G. Teubner; Chichester (UK): Wiley (1988; Zbl 0663.68076)]; [\textit{B. Bollobás}, Extremal graph theory. Reprint of the 1978 original. Mineola, NY: Dover Publications (2004; Zbl 1099.05044); Extremal graph theory. London--New York--San Francisco: Academic Press (1978; Zbl 0419.05031)]; [\textit{Daria Schymura}, Über die Fragekomplexität von Mengen-und Grapheneigenschaften, Master's thesis, Freie Universität Berlin (2006)] and [\textit{J. Kahn, M. Saks} and \textit{D. Sturtevant}, Combinatorica 4, 297--306 (1984; Zbl 0577.05061)]. The fourth chapter answers the question whether a given graph \(G\) is planar, namely, Kuratowski's theorem, by using methods of algebraic topology. Proceeding more generally, the author considers whether a given simplicial complex admits a geometric realization in some fixed dimension \(n\). The author investigates, besides questions of embeddability and nonembeddability, whether all maps of a given graph or a complex into some Euclidean space have some predetermined intersection property and whether maps with such a property exist. The remaining five chapters are devoted to Appendix A (basic concepts from graph theory), Appendix B (crash course in topology), Appendix C (partially ordered sets, order complexes, and their topology), Appendix D (groups and group actions) and Appendix E (some results and applications from Smith theory) based upon [\textit{G. E. Bredon}, Introduction to compact transformation groups. New York--London: Academic Press (1972; Zbl 0246.57017)] and [\textit{R. Oliver}, Comment. Math. Helv. 50, 155--177 (1975; Zbl 0304.57020)].