The LMS-EPSRC Durham Research Symposia began in 1974, and form an established series of international research meetings, with nearly 100 symposia to date. They provide an excellent opportunity to explore an area of research in depth, to learn of new developments, and to instigate links between different branches. The format is designed to allow substantial time for interaction and research. The meetings are held in July and August, usually lasting for 10 days, with up to 70 participants, roughly half of whom will come from the UK. Lectures and seminars take place in the Department of Mathematical Sciences, Durham University.

Graph theory is a highly active mathematical discipline playing a central role in a variety of research fields with numerous applications far beyond mathematics. In this conference we aim to bring together researchers in pure mathematics and theoretical computer science whose scientific interests range from algorithmic and combinatorial topics to geometric, group theoretic and spectral aspects in graph theory.

The three topics will be central to the symposium. They are not independent but have many cross-links.

Algorithmic Graph Theory and Complexity. Many computational problems in graph theory arise from practical questions. These include network flow problems (max-flow min-cut), vertex- and edge-connectivity (network reliability), matchings (assignment problems), Eulerian tours and Chinese Postman Problem, Hamiltonian cycles and Travelling Salesman Problem, vertex- and edge-colouring (scheduling, time-tabling), stable sets, dominating sets.

Combinatorial Graph Theory. One of the many tools in combinatorial graph theory is the Tutte polynomial, counting many important properties such as colourings, acyclic or totally cyclic orientations, spanning trees and forests, and more. This topic links also up with computational complexity from the previous section. Another thriving area is extremal graph theory. There are also many links with other areas such as coding theory and design theory. Statistical optimality of designs is closely related to graph properties determined by the Laplacian spectrum, mentioned in the next section.

Graphs, Geometry and Spectra. There are close links betweem graph theory and differential geometry. A differentiable manifold can be discretized by a weighted graph, and the graph Laplacian approximates the Laplacian of the manifold. Results from differential geometry have been applied to graphs. In addition, one of the most celebrated applications of graph spectra is to Google's page-rank algorithm. In optimal design theory in statistics, good designs are found by maximizing functions of the Laplacian eigenvalues of the concurrence graph. Expander graphs are of great theoretical and practical importance, with applications in combinatorial number theory, finite group theory, complexity theory and elsewhere.

Useful information about travelling to Durham can be found on the Department of Mathematical Sciences and Durham University webpages.

Accommodation for participants will be in a Durham College. Guest rooms offer en-suite and internet facilities. Attendance is by invitation only and fees for self-supporting participants are payable by cash, credit card, sterling cheques or sterling travellers cheques at registration.