A graph is a mathematical object with vertices, represented by dots, and edges, represented by lines. Each edge joins two vertices. For example, the graph shown on the right has 10 vertices and 15 edges. This graph is famous and has a name - the Petersen graph.
Graphs are very useful for modelling the relationships which exist between objects in a network or system. Many researchers in different areas use graphs, including physicists, computational biologists and computer scientists.
We now describe some of the graph theory research activities and interests of members of the School of Mathematics and Statistics at UNSW, past and present.
Hunting the Snark
George Szekeres (1911 - 2005) came to UNSW as Foundation Professor in Pure Mathematics in 1964. Although he retired in 1975, George continued to work at UNSW well into his nineties. George made outstanding contributions to mathematics in many different areas including algebra, combinatorics and number theory, mathematical analysis, relativity and cosmology. We will describe just one of his discoveries in the area of graph theory.
In 1973 George discovered a famous graph, which is now called the Szekeres snark. A snark is a graph with the following properties:
- the graph is cubic: that is, every vertex has three edges meeting it,
- the graph is bridgeless: that is, you cannot disconnect the graph into two pieces by deleting one edge,
- there is no proper edge colouring of the graph with three colours.
Here a proper edge colouring of a graph is formed by assigning colours to the edges of a graph so that all the edges which meet at a given vertex are coloured with distinct colours.
Snarks are important for several reasons. P.G. Tait proved in 1880 that the famous Four Colour Theorem (or Four Colour Conjecture, as it was then) is equivalent to the statement that "no snark is planar". A graph is called planar if it can be drawn in the plane with no edges crossing.
The oldest snark is the Petersen graph, shown above, which was discovered in 1891. For a long time nobody knew whether there were any other snarks at all. But then in 1946 Danilo Blanuša discovered two more snarks, both with 18 vertices. A few more snarks emerged over the years, including the Szekeres snark which George Szekeres discovered in 1973. The Szekeres snark, shown on the left, has 50 vertices and 75 edges.
Finally, Rufus Isaacs produced two infinite families of snarks in 1975. The name "snark" was given to these graphs by Martin Gardner in 1975, after the poem by Lewis Carroll called "The Hunting of the Snark". In this poem, the snark is a fabled beast who is very elusive, which reminded Gardner of these graphs which had been so difficult to find.
In the 1973 paper by George Szekeres where he described the Szekeres snark, he also made a conjecture, called the Cycle Double Cover Conjecture. This is one of the most famous conjectures in graph theory, and was also independently posed by Paul Seymour in 1979. In 1975, François Jaeger proved that if the Cycle Double Cover Conjecture is false, then a minimal counterexample must be a snark! However, none of the known snarks are counterexamples, as they all have a cycle double cover.
Since the Cycle Double Cover Conjecture is still open and motivating research today, we can say that the Hunting of the (minimal counterexample) Snark continues.
Random graphs
At the other end of the graph theory spectrum we find random graphs, a current area of research within the School of Mathematics and Statistics. Snarks are very special graphs with most known examples exhibiting a lot of symmetry, whereas random graphs rarely display any symmetry at all. In a random graph, the edges are constructed using some random or probabilistic procedure. In some sense, a random graph is a "typical" graph. Researchers are interested in the asymptotic properties of the random graph, meaning properties which hold as the number of vertices tends to infinity. For example, researchers may be interested in the probability that the random graph has a Hamilton cycle; that is, a cycle which visits each vertex exactly once.
One use of random graphs is to provide "average case" analysis for researchers, such as physicists or computer scientists, who use graphs to model a system of interest. For example, if a computer scientist has an algorithm which works on graphs and wishes to know how quickly their algorithm runs on average, then they should run the algorithm on several randomly-produced graphs. There is even a relatively new random graph model which is used to model the World Wide Web.
The first random graphs were introduced by Paul Erdős in 1947. However, current research at UNSW focusses on random regular graphs, introduced in the late 1970s. A regular graph is one in which every vertex has the same number of edges meeting it. This number is called the degree of the graph. So a cubic graph is just a 3-regular graph. For a given number of vertices n and a given degree d, we want to choose a d-regular graph on n vertices, uniformly at random (that is, each with the same probability). Note that a d-regular graph on n vertices has nd/2 edges, so either n or d should be even. Also, the largest possible value for d is n - 1, which occurs when every vertex is joined to every other vertex.
Unfortunately, there is no simple method for directly producing a d-regular graph uniformly at random. The configuration model of Bollobás is usually used to solve this problem. Alternatively, some researchers work with degree bounded graph processes. Start with a graph with n vertices and no edges and add a new randomly-chosen edge at each step. To maintain the degree bound, we may only add edges to vertices which currently have degree less than d.
The final graph of the process may be a d-regular graph, or the process may get stuck at a graph which is not d-regular, but where no other edges may be legally added. It has been shown that the final graph is with high probability both d-regular and connected. However, the final graph is not uniformly random. The question of how far the distribution of the final graph is from uniform is an important open problem.
Instead of adding one edge at each time step, the degree bounded star process adds several. It randomly chooses a vertex v of smallest degree, then adds the right amount of randomly chosen edges to v so that v ends up with degree d. The set of edges added forms a subgraph called a star. Again, this process may get stuck, but with high probability the final graph is both regular and connected. However, as above, the distribution of the final graph is not known.
Catherine Greenhill, School of Mathematics and Statistics, UNSW.