 Location: 2502, time: Friday 14:0015:30
Topic of this semester: Topological methods in graph theory
Lecture notes topol16.pdf

Midterm (takehome): tophw20161.pdf

Final (takehome): tophw20162.pdf

Weakly topics:
February 19Every 2connected graph can be partitioned into two connected parts of given size. Every 2connected nonbipartite graph on an even number of nodes can be partitioned into two equal parts such that the bipartite graph between them is connected. The continuity argument behind these proofs, and how generalizing this to more than two parts leads to topology. Basic notions of combinatorial topology: simplicial complexes, homeomorphism, geometric realization, baricentric subdivision.
February 26.Homotopy, homotopical equivalence, retracts, contractibility. Basic lemmas, including a characterization of contractible spaces as retracts of simplices.
March 4.Fillin Lemma, contractibility of unions, neighborhood complexes of bigraphs, Nerve Theorem. Simplicial complex of chains, Crosscut theorem.
March 11. Sperner's Lemma, Brouwer's Fixed Point Theorem, equivalent formulations.
Evasive graph properties, example: connectivity. Boolean functions, weakly symmetric Boolean functions, evasiveness. April 1. Evasive Boolean functions, decision trees. Every monotone weakly symmetric Boolean function with a prime number of variables is evasive. Main lemma: nonevasiveness implies contractibility. Every monotone graph property with a prime number of nodes is evasive (sketch). Connectivity versions of lemmas about contractibility. April 8. Connectivity of the neighborhood complexes between two levels of a Boolean algebra (application of Connectivity Nerve Theorem). Partitioning a graph into connected parts of prescibed sizes. Definition of simplicial complex K on the set of spanning trees. Main Lemma (proof postponed): if G is kconnected, then K is (k2)connected. Derivation of graph partitioning theorem using the Main Lemma and Brouwer's Fixed Point Theorem. April 15. End of proof. The BorsukUlam Theorem (without proof), different versions. April 22. Neighborhood complex of a graph. The complex of complete bipartite subgraphs. Connectivity of the neighborhood complex and chromatic number. April 29. Chromatic number of Kneser graphs. Graphs with large girth and chromatic number. April 29. Other applications of the BorsukUlam Theorem: HamSandwich and Necklace Theorems. Euler characteristic of simplicial complexes and convex cell complexes. May 6. The kequal problem and using the medianof medians algorithm to get an algorithm. Linear decision trees for membership in polyhedra. The Möbius function of a poset. May 13. Lower bound for the kequalproblem: Mobius functions, partition lattices, generating functions, sums of powers.