Postgraduate: Level 7
Sunday 17 January 2021
Friday 26 March 2021
16 July 2020
Requisites for this module
This module introduces graph theory and some key definitions, proofs and proof techniques associated with graph theory. It is distinguished from the undergraduate version of the module by greater emphasis on the concept of proof.
1. To introduce students to basic definitions and results of graph theory.
2. To develop students’ advanced understanding of some main proofs in graph theory.
3. To develop understanding of how to apply such results in particular problems at an advanced level.
1. Give basic graph theoretic definitions.
2. Prove basic results in the theory of graphs.
3. Show critical understanding of some results about matchings (Hall’s theorem and equivalent results).
4. Have critical understanding of some basic results about Hamilton cycles.
5. Have experience of problems connected with chromatic number, and know basic theory and how to apply it.
6. Have critical understanding of extremal graph theory, Ramsey theory and the theory of random graphs.
7. Advanced understanding of proofs of key theorems in the theory of graphs.
The PGT syllabus, below, will be distinguished from the UG one by greater emphasis on proofs.
Basic definitions: degrees, walks, trails, trees: minimum spanning tree. Bipartite graphs. Cycles, Hamiltonian cycles, connectedness, connectivity. inequalities between various measures of connectivity. Minors, subdivisions. Planar graphs (not too much topological detail). Independent sets and cliques, complements.
Definition. Hall's theorem on matching in bipartite graphs: results equivalent to Hall's theorem. Brief (non-examinable) discussion of Tutte's theorem.
Menger's theorem, related results.
Dirac's theorem, Ore's theorem. Chvatal-Erdos theorem. Hamiltonicity or otherwise of simple graphs such as the Petersen graph.
Chromatic number. Greedy colouring algorithm, statement of Brooks' theorem. Edge chromatic number: Vizing's theorem. Choosability: Galvin's theorem (without proof). Brief informal discussion of the four-colour problem (non-examinable). Proofs of some appropriate results.
Extremal Graph Theory
Turan's theorem (with proof). Erdos-Stone theorem (without proof). Examples including proofs of simple results. .
Basic definitions. Erdos-Szekeres upper bound: probabilistic lower bound on diagonal Ramsey numbers. Some calculations for small parameters and proofs of basic results.
Linear Algebra Methods
Adjacency matrix and spectrum. Some links with graph structure. Strongly regular graphs and their eigenvalues. Multiplicities of their eigenvalues and examples of using this.
G(n,p). Thresholds. First and second moment methods. Simple examples.
Teaching will be delivered in a way that blends face-to-face classes, for those students that can be present on campus, with a range of online lectures, teaching, learning and collaborative support.
Specific to the PGT students there will be additional lectures emphasising proof.
Students having issues with the module are encouraged to talk to the module supervisor during office hours/open-door policy.
Module supervisor and teaching staff
Dr David Penman, email: email@example.com.
Dr David Penman & Dr Jesus Martinez-Garcia
Dr David Penman (firstname.lastname@example.org), Dr Jesus Martinez-Garcia (email@example.com)
Dr Tania Clare Dunning
The University of Kent
Reader in Applied Mathematics
Available via Moodle
Of 35 hours, 33 (94.3%) hours available to students:
2 hours not recorded due to service coverage or fault;
0 hours not recorded due to opt-out by lecturer(s).
* Please note: due to differing publication schedules, items marked with an asterisk (*) base their information upon the previous academic year.
Disclaimer: The University makes every effort to ensure that this information on its Module Directory is accurate and up-to-date. Exceptionally it can
be necessary to make changes, for example to programmes, modules, facilities or fees. Examples of such reasons might include a change of law or regulatory requirements,
industrial action, lack of demand, departure of key personnel, change in government policy, or withdrawal/reduction of funding. Changes to modules may for example consist
of variations to the content and method of delivery or assessment of modules and other services, to discontinue modules and other services and to merge or combine modules.
The University will endeavour to keep such changes to a minimum, and will also keep students informed appropriately by updating our programme specifications and module directory.
The full Procedures, Rules and Regulations of the University governing how it operates are set out in the Charter, Statutes and Ordinances and in the University Regulations, Policy and Procedures.