# Graph theory: coming to a reality near you

April 14, 2016

Imagine you have before you a coloring book. The picture you are working on is divided into a hundred sections. When colored in with a full repertoire of shades and hues, the picture is brought to life. However, you find yourself stuck with the basic American diner set of four crayons.

It may seem trivial, but this scenario is one that map makers contend with constantly. Their solution? An interesting subfield of pure mathematics known as graph theory.

On April 7 the Quigley auditorium at Allegheny College was full of students and faculty who attended this semester’s installment of the math department’s undergraduate lecture series. This lecture, given by Ann Trenk, professor of mathematics at Wellesley College, covered the field of graph theory.

Students ought to understand the importance of all the behind-the-scenes work that informs their fields. Although an abstract mathematical proof might seem pointless because it has no immediate applications, it may birth five other proofs with applications all over academia. Take the computer. The process of creating computers involved myriad mathematical proofs. One may not seem relevant, but all together they created something that has revolutionized the world in a way that no other technology has ever done before. Math is life. You cannot escape it.

This extrapolatory approach is the idea of pure mathematics, the field which subsumes graph theory. Pure mathematics involves the study of math that does not inform or reside within the real world, but is purely dependent on the hypothetical rules of mathematics itself. This does not, however, mean that graph theory is completely abstract and restricted to academia.

Let us return to our map-making metaphor. Graph theory allows us to create a graph (representing our map) with as many areas as we want and it will only use four colors. This can also be applied to something such as GSM cell phone networks (currently used by T-Mobile and AT&T). GSM phone networks can only use four different frequency ranges. When creating a network for a large region, the cell carrier will have to divide its cell towers up into the four different frequency ranges, and the fastest way to do this is with graph theory.

Scheduling works in a similar way. Constructing a schedule with 3 professors and 2 rooms is not a particularly difficult task. But what about 600 professors and 400 rooms? Graph theory (and computer algorithms) allow us to quickly create a schedule.

The graphs that one typically imagines—histograms, bars graphs and pie charts—actually have little to do with graph theory. Nor do parametric graphs, like the graph of an equation like a parabola. Graphs in graph theory are simply a collection of vertices and the edges that may, or may not, connect them.

Trenk opened her lecture with a few explanations of different concepts of graph theory. The most relevant concept to the topic of her lecture was that of interval graphs. An interval graph is essentially a series of intervals, for example the times of courses, laid out in the form of a graph. If two “classes” are at the same “time” then there is an edge between the two corresponding vertices on the graph.

Trenk then uses a mystery as an example of a forensic application of abstract math. Suppose a book is stolen from a library by a professor. Now the police interviews each of the six suspects and each suspect gives a statement of who they claim to have seen at the library. Using graph theory, one can prove which one of the suspects lied.

“(The math department) is not necessarily aiming these lectures to the math major seniors, they are for everybody,” said James Hollerman, professor of math at Allegheny. “It is always important extend yourself and your knowledge base.”

The whole lecture, barring about a three-minute section in the middle, required no previous math experience to understand. During this middle section Trenk explained and proved a few short theorems to explain interval graphs in more detail.

Graph theory, and pure math in general, is an intriguing world for students and lay persons alike to explore.

If you want a picture to show with your comment, go get a gravatar.