Module Details

MA314-7-SP-CO: Graph Theory

Year: 2017/18
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
Teaching Staff: Dr Gerald Williams, email gwill@essex.ac.uk
Contact details: 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
Autumn Spring Summer

Module Description

Aims: To introduce graph theory and some key definitions, and some proof techniques associated with graph theory.

On completion of the module, students should be able to:
- give graph theoretic definitions;
- apply and prove results in the theory of graphs;
- deal with theory about matchings (Hall's theorem) and similar topics, e.g. max-flow min cut, Dilworth's theorem;
- apply and prove results about Hamilton cycles;
- solve problems connected with chromatic number, and know and prove theory;
- apply and prove results concerning strongly regular graphs;
- know rudiments of extremal graph theory, Ramsey theory and the theory of random graphs.

Syllabus

Basics Basic definitions: degrees, walks, trails, trees: minimum spanning tree. Bipartite graphs. Cycles, Hamiltonian cycles, connectedness, connectivity, planar graphs.

Matchings
Definition. Hall's theorem on matching in bipartite graphs.

Connectivity
Theorems concerning inequalities between various measures of connectivity.

Hamilton cycles
Dirac's theorem and its variants. Chvatal-Erdos theorem.

Colouring
Chromatic number, Brooks' theorem, edge chromatic number, Vizing's theorem, choosability. Brief discussion of the four-colour problem.

Extremal Graph Theory
Turan's theorem, Erdos-Stone theorem. Examples.

Ramsey theory
Basic definitions, Erdos-Szekeres upper bound.

Linear Algebra Methods
Adjacency matrix and spectrum. Some links with graph structure.

Random graphs
G(n,p). Thresholds. First moment method.

Learning and Teaching Methods

There are 5 lectures and a class 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 2 assignments that develop the theory (as opposed to being solely examples based), each worth 10%.

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

  • All reading lists are available here: http://readinglists.essex.ac.uk/ (Essex login required).

Further information