Module Details

MA314-7-SP-CO: Graph Theory

Year: 2016/17
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

Staff
Supervisor: Dr Gerald Williams, email gwill@essex.ac.uk
Teaching Staff: Dr Gerald Williams, email gwill@essex.ac.uk
Contact details: Mrs Shauna Meyers - 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
Autumn Spring Summer

Module Description

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.

Syllabus

Basics
Basic definitions: degrees, walks, trails, trees: minimum spanning tree. Bipartite graphs. Cycles, Hamiltonian cycles, connectedness, connectivity. Planar graphs (not too much topological detail).

Matchings
Definition. Hall's theorem on matching in bipartite graphs: results equivalent to Hall's theorem. Some discussion of Tutte's theorem and algorithmic aspects.

Connectivity
Menger's theorem, related results. Inequalities between
measures of connectivity.

Hamilton cycles
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.

Ramsey theory

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.

Random Graphs
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.

Assessment

20 per cent Coursework Mark, 80 per cent Exam Mark

Coursework

The coursework comprises a test worth 12.5%, a project worth 7.5% and 5 formative homeworks

Other details

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.

Other information

Available to Socrates/IP students spending all relevant terms at Essex.

Bibliography

  • 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

Further information