Infinite graph theory II

Summer Semester 2022

Schedule

• Lecture: Tuesday, 8:30 am–10:00 am, Geomatikum H4
• Exercises: Thursday, 12:00 am–1:30 pm, Geomatikum 435
  Thursday, 2:30 pm–4:00 pm, Sedanstr. 19, 205

Requirements

Collecting 100 points from homeworks and passing the oral exam at the end of the course. Each exemee gets two topics from this list (the exam can be done in German as well).

Literature

The material of the course can be found partially in the book Graph Theory (5th edition) by Reinhard Diestel.

Thematics

Structural infinite generalisation of Menger's theorem by Aharoni and Berger: reduction to the finite case if a finite separation exists, existence of a maximal wave, linking safely a new vertex, the proof when the digraph is countable (book 232-237).
Elements of topological infinite graph theory: topological ends, |G|, Jumping Arc Lemma, basic properties (book 245-251). Inverse limit of compact Hausdorff spaces, |G| as the inverse limit of cell complexes of finite multigraphs (book 258-261). The failure of Tutte's spanning tree packing theorem in infinite graphs (see here). Packing topological spanning trees (book 252-253). The cycle space (book 268-271).
Gale-Shapley theorem for infinite multigraphs, the derivation of the infinite version of Pym's theom from it. The Hercules-Hydra game (see the basic facts about ordinal arithmetic here ).
Some fundamental concepts in combinatoral set theory (ordinal numbers, cardinals, clubs, stationary sets, cofinality), the fundamental theorem of cardinal arithmetic, Elementary submodels : basic facts (Claims 2.7-3.8), Delta-system lemma (Theorem 4.1), Theorem 4.6, Fodor's lemma (Theorem 4.8). Partitioning a (directed) graph into (directed) cycles (Theorem 5.1). Subgraphs of uncountably chromatic graphs (see here p. 20-22). Ramsey's' theorem, Erdős-Dushnik-Miller theorem (Theorem 4.4), Todorcevic's anti-Ramsey result