began in 1974, and form an established series of
international research meetings, with over 90 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,
University of Durham.
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 differentiable 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.