# Graphentheorie

### Wintersemester 2021/22 Stefan Felsner

1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 . 32 ,

Lecture 1, Th. 21.10.2021

```    3 trigger problems
Introduction
Fundamental definitions
iso- and other morphisms
types of subgraphs
examples of graphs
Solution of problem I

```
Lecture 2, Fr. 22.10.2021
Youtube recording part 1 (62 min)
Youtube recording part 2 (26 min)
```       Cycle free graphs
Solution of problem II
Geometric graphs without disjoint edges
Topological graphs, Thrackles
Solution of problem III
Rigid grids: paralell classes of edges - connectivity of auxiliary graph
```
Lecture 3, Th 28.10.20121
```      Degree sequences
Charakterization of Havel and Hakimi
The flip-graph of 2-switches
Thm. of Erdös-Gallai
Paths and cycles
```
Lecture 4, Fr 29.10.2021
```         Distances
Connectivity
vertex- and edge-connectivity
Κ(G) vs Κ'(G)
The Theorem of Menger
proof of the u-v variant
```
Lecture 5, Th 04.11.2021
```          The classical Menger's Theorem
8 variants of Menger's Theorem
Ford-Fulkerson and König-Egervary
Trees and Forests
Characterizations of trees
Spanning trees
3 algorithmic proofs for their existence
```
Lecture 6, Fr 05.11.2021
```        BridgeIt
The game
A winning strategy based on spanning trees
Cayley' Theorem on the number of trees
Proof 1. Pitman; twofold counting of chains of rooted forests
Proof 2. Clarke; refined counting and recursion
```
Lecture 7, Th 11.11.2021
Youtube recording - audio dies 13 minutes before end
```           Proof 3. Prüfer; a bijection between trees and Prüfer codes
Proof 4. Joyal; A bijection involving the cycle-forests of maps [n] --> [n]
F2 vector spaces of graphs
F2 orthogonality
vertex and edge space
cut and cycle space
fundamental bases of cut and cycle space
```
Lecture 8, Fr 12.11.2021
```           Lights-Off; an application of F2 vector spaces
Matrix-Tree Theorem
Sketch of the proof via the Cauchy-Binet determinant formula
Proof of the Matrix-Tree Theorem for digraphs
arborescences
reduction to digraphs with outdeg(v) = 1 for all v
```
Lecture 9, Th 18.11.2021
```     Eulerian paths and cycles
Memory Wheels
The deBruijn Graph Bn(m)
BEST Theorem
Counting eulerian cycles in directed graphs
```
Lecture 10, Fr 19.11.2021
```        The number of eulerian cycles in deBruijn Graphs
Eigenvalue version of the matrix tree theorem
Path of length n in Bn(m)
The eigenvalues of the Laplacian of Bn(m)
Hamilton cycles
The icosian game
Dirac's theorem
```
Lecture 11, Th 25.11.2021
```       Theorem of Erdös-Chvatal
The hamiltonian closre
Hamiltonian cycles in squares and cubes of trees
Extremal graph theory
Four fundamental parameters
Mantel's theorem
```
Lecture 12, Fr 26.11.2021
```      Turán's Theorem
Proof 1: optimization - shifting weights
Proof 2: short induction
Proof 3: the 3 vertex property
- characterizing maximizing examples
Triangles in dense graphs
Extremal functions ex(n,H)
Theorems of Erdös-Stone and Erdös-Simonovits
```
Lecture 13, Th 02.12.2021
```     ex(n,C4) = O(n3/2)
An inequality for the independence number α
The Wei inequality
Two weakenings and Turán again
1. proof: random permutations
2. proof: analyzing Algo MAX
3. proof: analyzing Algo MIN
```
Lecture 14, Fr 03.12.2021
```   Ramsey Theory
Monotone subsequences (Erdös Szekeres)
Breaklines in domino tilings of the 6x6 board
Theorems of Schur / van der Waerden / Ramsey
(Ein Beitrag zu den Sätzen von Schur, Ramsey und Fermat: video)
Graph-Ramsey
Existence of R(k,k) via induced colorings
Existence of R(k,k) by induction, binomial coefficients
Probabilistic lower bound
```
Lecture 15, Th 09.12.2021
```     Which Ramsey numbers are known?
The general set Ramsey numbers: Rk(t;n1,..,nt)
Applications of Ramsey numbers: The Happy Ending Problem (convex subsets)
Esther Klein Lemma
Theorem of Erdös Szekeres
N(n) < R4(5,n)
N(n) < R3(n,n)
Planar Graphs
Drawings, crossings, the Jordan curve theorem
```
Lecture 16, Fr 10.12.2021
```         K5 and K3,3 are non-planar
Dual Graphs
Proofs of Euler's formula
dual trees
induktion
angle sums
```
Lecture 17, Th 17.12.2021
```        Implications of Euler's formula
The "Art Gallery Problem"
Crossing numbers
topological and straight
bounds
The Crossing Lemma
```
Lecture 18, Fr 17.12.2021
```           Unit distances - an application of the crossing lemma
Moon's probabilistic proof for drawings of K3n with few crossings
Theorems of Kuratowski and Wagner
Proof of Kuratowski
3 connectivity lemma
subdivision lemma
```
Lecture 19, Th 06.01.2022
```      Whitney's Theorem (unique embedding)
Hanani-Tutte Theorem (independent odd crossings)
Transforming drawings
The z-vector of a drawing
The vector space of drawings
The vector spaces of K5 and K3,3
```
Lecture 20, Fr 07.01.2022
```      Kissing coins representations of planar triangulations (Koebe's Theorem)
The iteration and its convergence
Laying out the triangles
Separator theorems
```
Lecture 21, Th 13.01.2022
```         Centerpoints of point sets
The cups and belts of a circle representation
Expected size of a separator
An application of small separators: max weighted matching
Two lemmas about weight increasing alternating paths
The running time
```
Lecture 22, Fr 14.01.2022
```     Planar drawings on linear size grids
Schnyder woods on triangulations
Definition and existence
Trees and regions
Barycentric coordinates
Chromatic numbers
Alternative definitions
Two lower bounds
```
Lecture 23, Th 20.01.2022
```        Graphs with no triangle and large χ - further constructions
Mycielski-Construction
Split-graphs
The expected  χ of random graphs
Upper bounds
Greedy colorings
Bounding  χ by Δ and by degeneracy
Bounding  χ by pathlength in orientations (Gallai-Roy)
```
Lecture 24, Fr 21.01.2022
```      Geometric intersection graphs
χ-boundedness
interval graphs and square graphs
rectangle intersection graphs (Asplund-Grünbaum)
Intersection graphs of pseudodisks
```
Lecture 25, Th 27.01.2022
```      Line graphs and edge colorings
Examples
Matchings : Theorem of Kőnig-Egerváry
Chromatic index of bipartite graphs (Kőnig)
Perfect graphs
```
Lecture 26, Fr 28.01.2022
```          Vizing's Theorem
Theorem of Tait
Connection to Hamiltonicity
Counterexample of Tutte
List colorings
Lower and Upper Bounds
Example: Bipartite graphs
Survey of results on planar graphs
```
Lecture 27, Th 03.02.2022
```          Planar graphs
Upper bound of 5 (Thomassen)
Lower bound of 5 (Mirzakhani)
Kernels
Some remarks on stable matchings
Galvin's Theorem: List-edge colorings of bipartite graphs
```
Lecture 28, Fr 04.02.2022
```          Stable matchings: Gale-Shapley Theorem
Galvin's Theorem: wrap-up
Fractional chromatic number
(A book: Fractional Graph Theory by Scheinerman and Ullman)
b-colorings
Fractional chromatic number χf
odd cycles
lower bounds
b-cliques and fractional clique number ωf
```
Lecture 29, Th 10.02.2022
```        Chromatic and clique numbers via 0-1 programs
LP-relaxation and duality
χf = ωf
Bounding the integrality gap: χ <= (1+ln α)χf
Colorings and homomorphisms
Kneser graphs
Fractional chromatic number of Kneser graphs
```
Lecture 30, Fr 11.02.2022
```        A connection (equivalence) with the Erdös-Ko-Rado Theorem
Chromatic number of Kneser graphs (a topological argument)
Perfect graphs
The bipartite collection: 4 fundamental classes of perfect graphs
```
Lecture 31, Th 17.02.2022
```        The Berge conjectures
Chordal graphs
clique separators - simplicial vertices -
tree representation - perfect elimination ordering
perfectness
The perfect graph theorem
ω-perfectness - α-perfectness - product perfectness
minimally imperfect graphs
```
Lecture 32, Fr 18.02.2022
```  Tree width