MA314-6-SP-CO:
Graph Theory
2022/23
Mathematics, Statistics and Actuarial Science (School of)
Colchester Campus
Spring
Undergraduate: Level 6
Current
Monday 16 January 2023
Friday 24 March 2023
15
29 April 2022
Requisites for this module
MA108 and MA114
(none)
(none)
(none)
(none)
This module introduces graph theory and some key definitions, proofs and proof techniques associated with graph theory.
1. To introduce students to basic definitions of graph theory.
2. To develop students’ critical understanding of some main results in graph theory.
3. To develop understanding of how to apply such results in particular problems.
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 some 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.
Syllabus:
Basics
Basic definitions: degrees, walks, trails, trees: minmum 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.
Matchings
Definition. Hall's theorem on matching in bipartite graphs: results equivalent to Hall's theorem. Brief (non-examinable) discussion of Tutte's theorem.
Connectivity
Menger's theorem, related results.
Hamilton cycles
Dirac's theorem, Ore's theorem. Chvatal-Erdos theorem. Hamiltonicity or otherwise of simple graphs such as the Petersen graph.
Colouring
Chromatic number. Greedy colouring algorithm, statement of Brooks' theorem. Edge chromatic number: Vizing's theorem. Choosabiilty: Galvin's theorem (without proof). Brief informal discussion of the four-colour problem (non-examinable).
Extremal Graph Theory
Turan's theorem (with proof). Erdos-Stone theorem (without proof). Examples.
Ramsey theory
Basic definitions. Erdos-Szekeres upper bound: probabilistic lower bound on diagonal Ramsey numbers. Some calculations for small parameters.
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.
Random graphs
G(n,p). Thresholds. First and second moment methods. Simple examples .
Teaching in the department will be delivered using a range of face to face lectures, classes and lab sessions as appropriate for each module. Modules may also include online only sessions where it is advantageous, for example for pedagogical reasons, to do so.
This module does not appear to have a published bibliography for this year.
Assessment items, weightings and deadlines
| Coursework / exam |
Description |
Deadline |
Coursework weighting |
| Exam |
Main exam: In-Person, Closed Book, 120 minutes during Summer (Main Period)
|
| Exam |
Reassessment Main exam: In-Person, Closed Book, 120 minutes during September (Reassessment Period)
|
Exam format definitions
- Remote, open book: Your exam will take place remotely via an online learning platform. You may refer to any physical or electronic materials during the exam.
- In-person, open book: Your exam will take place on campus under invigilation. You may refer to any physical materials such as paper study notes or a textbook during the exam. Electronic devices may not be used in the exam.
- In-person, open book (restricted): The exam will take place on campus under invigilation. You may refer only to specific physical materials such as a named textbook during the exam. Permitted materials will be specified by your department. Electronic devices may not be used in the exam.
- In-person, closed book: The exam will take place on campus under invigilation. You may not refer to any physical materials or electronic devices during the exam. There may be times when a paper dictionary,
for example, may be permitted in an otherwise closed book exam. Any exceptions will be specified by your department.
Your department will provide further guidance before your exams.
Overall assessment
Reassessment
Module supervisor and teaching staff
Dr Alexei Vernitski, email: asvern@essex.ac.uk.
Dr Alexei Vernitski
asvern@essex.ac.uk
Yes
Yes
No
Prof Stephen Langdon
Brunel University London
Professor
Dr Rachel Quinlan
National University of Ireland, Galway
Senior Lecturer in Mathematics
Available via Moodle
Of 33 hours, 23 (69.7%) hours available to students:
10 hours not recorded due to service coverage or fault;
0 hours not recorded due to opt-out by lecturer(s), module, or event type.
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.