Charles Explorer logo

Combinatorics and Graph Theory 1

Class at Faculty of Mathematics and Physics |


Double Counting: Sperner Theorem, The maximum number of edges in a graph without C4 and without K3.

Number of spanning trees (determinant proof) and electrical networks.

Generating functions (understood as Taylor series), applications: Catalan, Fibonacci numbers, solving recurrences, asymptotics of the solution.

Finite projective planes.

Error-correcting codes, basic properties. Hammnig code, Hadamard code. Existence of asymptotically good codes (Gilbert-Varshamov). Hamming's lower bound.

Maximum matching in graphs, Hall's theorem and its applications (Birkhoff-von Neumann theorem), Tutte theorem. k-connectivity, Menger's theorem. Ear lemma, structure of 2-connected graphs.

Ramsey theorem, Ramsey theorem for p-tuples, Ramsey infinite theorem.

König's theorem on the infinite branch.

Course web page (Irena Penev, Winter 2020/2021):


Inclusion-exclusion principle and its applications.

Generating functions.

Finite projective planes, latin squares.

Hall theorem and its applications.

Flows in digraphs. k-connectivity of graphs.

Ramsey theory.