One mathematical framework, different applications

Anna uses structural networks to study the evolutionary history of species and genes, while Patricia studies how we can determine efficient arrival and departure times of subways.

Anna examines this problem since 2024, while Patricia just completed her Master thesis about train scheduling. Their two fields may be different, but they do have something in common: Drawing lines between dots representing objects to establish correlations, revealing a structural network with lots of interesting and useful data. Anna explains:

- For instance – let’s say the dots on this paper represent Anna, Erik, Patricia, and Marc. Let’s draw a line between two persons if they know each other, for argument's sake let’s say Anna, Patricia and Erik know each other, and Anna, Patricia, and Marc know each other, but Erik and Marc don’t. We have now depicted the relationships between the dots, she says, underlining that this is a very simple example. Anna adds, this construction of dots and lines is called a combinatorial graph or simply graph. This is completely different from the graphs we see in school, where you have an x- and a y-axis. In mathematics, we call the dots vertices and the lines edges.

- So, the math in both of our fields is similar, but the applications are different, says Patricia and continues:

- In my work, the dots represent arrivals and departures of trains in stations in a subway system. The train first arrives at a station A, then stays on the station for a while until it departs for another station B, where it again arrives. We would then connect the arrival dot of station A with the departure dot of station A and the departure dot of station A with the arrival dot of station B. So, the lines we draw create train paths. We then ask the question: At which time should each train arrive and depart from their stations? The graph makes it possible to create train schedules that are efficient, guaranteeing short transfer times for passengers while using as few vehicles as possible, Patricia says. So, my work lies in the intersection of graph theory, discrete mathematics, and optimization.

Anna explains further that it also comes down to graphs in her research. Darwin’s famous “tree of life” is, when you think about it, a type of graph. The dots represent species, for instance now-living ones like a cow, a cat, and a dog. Other dots represent previous, ancestral species that current ones have evolved from. The lines represent the evolutionary relationships between them, namely who is a descendant of who.

- If we were able to look back in time, we could observe the actual ancestors of the cow and the cat. But this is, of course, impossible in practice! Instead, biologists need to figure out and test plausible evolutionary scenarios from what is available here and now, says Anna. She explains that one possibility is to look at bone structures. A cow and a horse might look somewhat similar, but their bone structure is completely different, which means their evolution and origin are different as well. However, genetic material is probably the most commonly used material nowadays.

Classically, Anna continues, it is assumed that when two species diverge, they will never come together again. In the last thirty years or so, people have realized that this might be a little bit too optimistic. The problem is, when this assumption is dropped, you need to take very tangled and complicated graphs into account. In short, the graphs get messy!

- I’ve talked about biology so far, but this work is far away from practice. Biologists still infer both trees and more complicated networks. My approach is a bit different. You give me a network and I’ll try to tell you something about it, says Anna. For example, if we have a very complicated evolutionary scenario, how can we efficiently find a simplified version that still preserves the central trends? To answer such questions, we need great ideas both from mathematicians, computer scientists, and biologists.