Graph theory

A graph consists of a set of elements together with a binary relation defined on the set. Graphs can be represented by diagrams in which the elements are shown as points and the binary relation as lines joining pairs of points. It is this representation which gives graph theory its name and much of its appeal. However, the true importance of graphs is that, as basic mathematical structures, they arise in diverse contexts, both theoretical and applied. The concept of a graph was known already to Euler in the early eighteenth century, but it was the notorious Four-Colour Problem, posed by F. Guthrie in the mid-nineteenth century, that spurred the development of this simple concept into a flourishing theory. In this century, interactions between graph theory and linear algebra, probability theory, number theory, group theory, geometry, topology, and other branches of mathematics have led to further developments in the subject. In recent years, its fundamental links with operations research and computer science have resulted in the fast growth and greatly increased prominence of graph theory.

Graph theory has played a major role in the research activities of the Department since its inception in 1967, due primarily to the influence and example of W.T. Tutte, a leading figure in the subject for several decades. Current areas of research include algebraic graph theory (association schemes, knot polynomials, eigenvalues), algorithmic graph theory, asymptotic enumeration of graphs, extremal graph theory, matching theory, minimax theorems, and Ramsey theory.

Members: