Connecting the dots

For those who hear the phrase “graph theory” and think of the basic pie charts and bar graphs introduced in elementary school, there’s a new world to be explored.

“In graph theory, the most simple way to think of a graph is as a set of points joined by segments,” said Felix Lazebnik, professor of mathematical sciences at the University of Delaware and an internationally known expert in graph theory. “Graph theory has become the common language for discrete mathematics … especially with the advent of computer science.”

Lazebnik is one of three researchers working in graph theory whose work was  celebrated at a conference at UD in early August. Tthe Algebraic and Extremal Graph Theory Conference was attended by more than 80 mathematicians from around the world and featured 14 invited speakers from the U.S., Canada, the Netherlands, Spain, China, Israel and England.

In addition to Lazebnik, the conference honored the work of Willem Haemers of Tilburg University in the Netherlands and Andrew Woldar of Villanova University. All three delivered talks at the event.

Graphs—the dot-and-line kind that are highly useful in such diverse fields as computer science, linguistics, chemistry and sociology—can be seen as similar to a network, where the problem lies in connecting the dots by drawing lines in particular ways.

Lazebnik described a very simple example in interpersonal relations: A group of seven people can be represented by drawing seven points, or dots, on a flat piece of paper. Lines can then be drawn between any pairs of individuals who know each other. When the drawing is finished, it can serve as a visual answer to various questions, such as which person has the most acquaintances or how many individuals know only one other person in the group.

Much larger and more complex graphs can be created as models for everything from how various areas of the brain are connected to how diseases spread through populations. In another example, the methods used by search engines to rank web pages come from recent techniques in graph theory.

“Graph theory studies all these possible applications,” Lazebnik said. “When you have a question, you can translate it into the language of graphs.”

That translation requires relying on theory, said Eric Moorhouse, professor of mathematics at the University of Wyoming, who often draws simple graphs to use in his teaching. But in real situations, particularly in computer science, “Most of the graphs we are concerned with are much too complicated to be meaningfully represented by drawings or physical models,” he said. 

Lazebnik “is one of the most important researchers in graph theory,” whose work in 1995 on constructing a particular kind of graph “is still the best in the world,” said Sebastian Cioabă, associate professor of mathematical sciences at UD and one of the conference organizers.

Lazebnik, who was born and grew up in Kiev, Ukraine, in what was then the Soviet Union, earned his master’s degree in mathematics at Kiev State University. He taught high school for four years at a boarding school at the university, where students from throughout Ukraine were able to study more advanced math and physics than were offered at other high schools.

Even today, Lazebnik said, that high school teaching experience, in which he worked with the same youngsters for three years and so got to know them well and help them develop their skills over time, remains one of his most meaningful and enjoyable jobs. He is still in touch with many of his former students, some of whom have gone on to their own careers in mathematics.

“On the other hand, I would never have been able to study mathematics further and do active research if I continued that work,” he said, so when the opportunity to leave the Soviet Union arose, he and his family came to the United States.

Arriving in Philadelphia with little knowledge of the American system of higher education, he wrote letters to several mathematicians, who offered him “remarkable advice and support,” he said. The first thing he learned was that, in order to teach at a university, he would need a doctoral degree.

Lazebnik applied to the University of Pennsylvania, without even knowing the school’s reputation and Ivy League status, and was accepted. He worked part-time as a lecturer and teaching assistant—and, during a yearlong leave of absence from Penn, as a full-time actuarial assistant at an insurance company—and earned his doctorate in 1987. He joined the UD faculty that same year.

He is the author of numerous papers in academic journals and serves on the editorial board of the Electronic Journal of Combinatorics. He has supervised many undergraduate and graduate students, and is currently working with three doctoral students.

The conference seeks to “expand, deepen and broaden the research” in new areas of graph theory, according to the National Science Foundation, one of the sponsors. Other sponsors are UD’s Department of Mathematical Sciences, Villanova University, Muhlenberg College, the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers University, the International Linear Algebra Society and the Institute for Mathematics and Its Applications.

Article by Ann Manser; illustrations by Jeff Chase and courtesy of Eric Moorhouse