CRM - Fields - PIMS Prize Lecture: "Some 21st Century Results in Graph Theory"

Abstract

Finding ways of getting from place to place has occupied humanity since the dawn of civilization. The Romans built roads, Moses parted the waters, Dorothy clicked her heels (cf. the Wizard of Oz). Mathematicians settle for studying graphs. A graph is a set of vertices and a set of edges, each of which links a pair of vertices. Thus, graphs may abstractly represent the highways (edges) linking a set of cities (vertices), the bridges linking the islands of an archipelago, or the flights linking airports. However, the use of graphs as models extends far beyond transport networks. The edges can represent bonds between molecules, hyperlinks between webpages, or acquaintanceship in a social network. Indeed, the connections in any network, whether physical or conceptual, can be modeled in this way. Hilbert in his famous 1900 talk, The Problems of Mathematics, noted: "History teaches the continuity of the development of science. We know that every age has its own problems, which the following age either solves or casts aside as profitless and replaces by new ones." This is as true in graph theory as in any other area of mathematics. The development of graph theory has been profoundly marked by the advent of the information age. This has led to explosive growth in the size of the networks that can be studied and to the development of techniques that allow us to study huge networks. The talk will briefly survey the changes that have occurred and then focus on a number of quite diverse techniques for handling huge networks, all of which allow us to deduce global properties of a network via an analysis of its local structure. Examples will include the application of the probabilistic method to graph colouring and of structural decomposition to the theory of graph minors. The talk is aimed at a general audience and no knowledge of graph theory is assumed.