- Location: 2-502, time: Friday 14:00-15:30
Topic of this semester: Topological methods in graph theory
Lecture notes topol16.pdf
Midterm (take-home): tophw-2016-1.pdf
Final (take-home): tophw-2016-2.pdf
Weakly topics:February 19
Every 2-connected graph can be partitioned into two connected parts of given size. Every 2-connected non-bipartite 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.
Fill-in 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: non-evasiveness 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 k-connected, then K is (k-2)-connected. Derivation of graph partitioning theorem using the Main Lemma and Brouwer's Fixed Point Theorem. April 15. End of proof. The Borsuk-Ulam 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 Borsuk-Ulam Theorem: Ham-Sandwich and Necklace Theorems. Euler characteristic of simplicial complexes and convex cell complexes. May 6. The k-equal problem and using the median-of 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 k-equal-problem: Mobius functions, partition lattices, generating functions, sums of powers.