Most people first meet graphs as a childhood activity; a page of numbered dots, a pencil, and a hidden picture that appears once the lines are drawn. For Isaac Reiter, a fifth-year doctoral student in mathematics at Lehigh, that simple idea has become the foundation of a dissertation.

Reiter's research focuses on a specific family of graphs called interval graphs. The idea starts with the number line. An interval is simply a continuous stretch of it, such as everything between one and three. Give each interval a name, represent it with a dot, and connect two dots whenever their intervals intersect. The result is a compact picture of which intervals interact and which do not.

With three intervals, the picture is easy to read. With 100, it becomes a quick way to take in a large amount of information at a glance.

Reiter works with a more detailed, nuanced version of this idea. Intervals can relate to each other in two ways. They can partially overlap, or one can sit entirely inside another. A standard interval graph cannot tell those two situations apart. So Reiter's graphs color the edges, with one color marking overlap and another marking containment, which adds a layer of information to the picture.

Going from intervals to a colored graph is straightforward. Reiter's research asks what happens when you go the other direction.

He offers an analogy. Imagine handing an interval graph to a preschooler with a box of red and blue crayons. The child colors the edges at random and hands the page back. Can you now find a set of intervals that matches the coloring? In other words, can you start with the finished picture and reconstruct the intervals behind it?

Sometimes the answer is yes, and sometimes it is no. Reiter is pursuing two strategies to understand why.

The first is to build an algorithm that attempts the reconstruction. When the algorithm stalls on a particular graph, that failure is informative, because it reveals what can go wrong. The second strategy is to study those failures and identify the structures inside a graph that cause them. If those problem structures can be named, a mathematician could look at a colored graph and know right away whether a matching set of intervals exists, without running the algorithm at all.

"I know ahead of time before I even put it in the algorithm that I can't do it for this one,” Reiter says. “So the idea is we use the algorithm and reverse engineer it so that way I can just look at them and confirm we can't do it," he explains.

Reiter's path to the project began before graduate school. He earned his undergraduate degree at Kutztown University, where he discovered his love for graph theory. At Lehigh he set out to find a dissertation advisor, completing independent studies and exploring different topics. He approached Professor Garth Isaak, professor of mathematics, who works in combinatorics, and Isaak sent him a collection of slides and articles on problems on which he had worked. He invited Reiter to see if anything caught his interest.

One slide did. It posed a problem that looked like it might be interesting, and Reiter began experimenting with it. A month or two later, he had his first significant result. "At that point I was like, 'Okay, this could definitely be my dissertation topic,'" he recalls.

The full problem, covering every possible interval graph and every possible coloring, is too large to tackle all at once. Reiter and his advisor are starting with specific kinds of interval graphs. When every dot of a graph is connected to every other dot, we say the graph is complete. Complete graphs are the building blocks of interval graphs, and Reiter has been focusing on interval graphs that contain either one or two of them. He says that they have made good progress on those cases, and the current work is writing up the results and checking them carefully. The longer-term goal is to extend the findings to all other interval graphs.

Research is only part of Reiter's story. He is a teaching assistant, currently in his fifth semester as the full instructor of Math 81, calculus with business applications.

"I love math research," he says. "I also really love teaching."

That enthusiasm is shaping his next step. This fall he has been applying for teaching faculty positions. In the spring, he plans to apply for industry positions as well, casting a wide net as his time at Lehigh approaches its end.

For now, his focus is on the problem in front of him: finishing the proofs, checking them again, and extending a result that began as a single slide into something much larger.