MA314-7-SP-CO: Graph Theory
Department: Mathematical Sciences
Essex credit: 15
ECTS credit: 7.5
Available to Study Abroad / Exchange Students: No
Full Year Module Available to Study Abroad / Exchange Students for a Single Term: No
Outside Option: No
Dr Gerald Williams
Dr Gerald Williams, email email@example.com
Miss Shauna McNally - Graduate Administrator. email: smcnally (Non essex users should add @essex.ac.uk to create the full email address), Tel 01206 872704
|Module is taught during the following terms
Aims: To introduce graph theory and some key definitions, proofs and proof techniques associated with graph theory.
On completion of the module, students should be able to:
- Give basic graph theoretic definitions
- Prove basic results in the theory of graphs
- Deal with basic theory about: matchings (Hall's theorem, etc.) and similar topics, e.g. max-flow min cut, Dilworth
- Know some basic results about Hamilton cycles
- Have some experience of problems connected with chromatic number, and know basic theory
- Know rudiments of extremal graph theory, Ramsey theory and the theory of random graphs
- Be acquainted with use of MAPLE to investigate graph-theoretic problems.
Basic definitions: degrees, walks, trails, trees: minimum spanning tree. Bipartite graphs. Cycles, Hamiltonian cycles, connectedness, connectivity. Planar graphs (not too much topological detail).
Definition. Hall's theorem on matching in bipartite graphs: results equivalent to Hall's theorem. Some discussion of Tutte's theorem and algorithmic aspects.
Menger's theorem, related results. Inequalities between
measures of connectivity.
Dirac's theorem and its variants. Chvatal-Erdos theorem.
Colouring Chromatic number. Greedy colouring algorithm, its use to prove Brooks' theorem. Edge chromatic number: Vizing's theorem. Choosability: Galvin and Thomassen's results. Brief informal discussion of the four-colour problem.
Extremal Graph Theory
Turan's theorem (with proof). Erdos-Stone theorem (without proof). Examples.
Basic definitions. Erdos-Szekeres upper bound. Probabilistic lower bound on diagonal Ramsey numbers.
Linear Algebra Methods
Adajacency matrix and spectrum. Laplacian. Some links with graph structure. Fisher's inequality for designs.
G(n,p). Thresholds. First and second moment methods. Simple examples. Brief informal overview of the evolution of random graphs.
Learning and Teaching Methods
There are 5 lectures and 2 classes in every fortnight. There will be different coursework at postgraduate level, and separate classes for postgraduates. In the Summer Term 3 revision lectures are given.
20 per cent Coursework Mark, 80 per cent Exam Mark
The coursework comprises a test worth 12.5%, a project worth 7.5% and 5 formative homeworks
Information about coursework deadlines can be found in the "Coursework Information" section of the Current Students, Useful Information Maths web pages: Coursework and Test Information
Exam Duration and Period
2:00 during Summer Examination period.
Available to Socrates/IP students spending all relevant terms at Essex.
- Recommended Reading:
- R.J. Wilson, Introduction to Graph Theory, Longman
- Supplementary Texts:
- A. Bollobas, Modern Graph Theory, Springer-Verlag
- R. Diestel, Graph Theory, Springer-Verlag
- P. Higgins, Nets, Puzzles, and Postmen: An Exploration of Mathematical Connections, Oxford University Press, 2007