Time: Thursday 12.15-14.00
Room: B
Lecture notes: here
Final exam: Monday 12 February 2024, 14:00-17:00,
room 601
We covered some graph theory appearances in "nature" and some definitions, ending with the definition of induced subgraphs.
We covered some more definitions, characterised bipartite
graphs in terms of their cycle lengths and proved Hall's
Marriage Theorem.
You should now be able to do Problems 1-10 from Problem
List 1.
We introduced some corollaries to Hall's Marriage Theorem. We
have also defined k-connected graphs, stated Menger's
Theorem and proved the main ingredient in its proof (Lemma
1.10).
Assuming you believe Menger's Theorem is true, you should now be
able to do Problems 1-11 and 13 from Problem List 1.
We proved vertex and edge versions of Menger's Theorem, and
gave a very brief introduction to extremal problems (defining Kr,
Km,n, and r-partite graphs).
You should now be able to finish Problem List 1 and
attempt Problems 1-3 from Problem List 2.
We introduced Turán graphs and proved Turán's Theorem, as well
as started bounding the number of edges a C4-free
graph
can have (we will complete the argument on the next lecture).
You should now be able to attempt Problems 1-6 from Problem
List 2.
We gave an asymptotic upper bound for the number of edges a Kt,t-free
graph can have (Theorem 2.5), introduced chromatic numbers, and
stated the Erdős-Stone Theorem, finishing with Corollary 2.8.
You should now be able to attempt Problems 1-8 and 10-12 from Problem
List 2.
We sketched a proof of Erdős-Stone Theorem and stated another
corollary to it. We also introduced Hamiltonian graphs and
proved Dirac's Theorem.
You should now be able to attempt Problems 1-16 from Problem
List 2.
We introduced and characterised Eulerian graphs. We also
introduced Ramsey numbers and stated Ramsey's Theorem on their
existence.
You should now be able to finish Problem List 2.
We proved Ramsey's Theorem, and discussed its variations.
You should now be able to attempt all problems from Problem
List 3.
We introduced random graph techniques, and used them to give
lower asymptotic bounds of Ramsey and Zarankiewicz numbers. We
also gave some lower bounds on chromatic numbers.
You should now be able to attempt Problems 1-2 from Problem
List 4.
We proved that there are graphs which have (simultaneously)
arbitrarily large girth and arbitrarily large chromatic number.
We briefly introduced threshold functions.
You should now be able to attempt Problems 1-5 from Problem
List 4.
We found threshold functions for a graph to contain an edge or
a triangle, and gave an idea on why one can have a very precise
estimate on the clique number of almost every random graph.
You should now be able to finish Problem List 4.
We have introduced planar graphs and proved some results for
them, including Euler's Formula and the Five Colour Theorem.
We discussed drawings of graphs on closed surfaces and introduced the chromatic polynomial.
You should now be able to attempt Problems 1-5 from Problem
List 5.
We discussed edge chromatic numbers and proved Vizing's Theorem.
We also had a brief introduction into algebraic methods and using them to list all Moore graphs.
You should now be able to attempt Problems 1-7 from Problem
List 5.
Time: Wednesday 14.15-16.00
Room: 602
Problem lists: 1 2
3
4
5
[Difficulty indicators:
− easy / short,
worth 2 points;
° medium, worth 3 points;
+ hard / long,
worth 4 points;
++ very hard /
very long, worth 5 points.]
Problem lists (without hints and difficulty indicators):
1 2 3 4 5