Skip to Main Content
Sign In
Visit Apply Give

News Connecting the dots

Image Picker for Section 0
Conference on graph theory includes celebration of UD mathematician's work

​Felix Lazebnik is an internationally recognized expert in the field of graph theory.

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. 

More about Felix Lazebnik and the conference

​This simple graph, known as a Heawood graph, has 14 vertices or points (represented by screws) and 21 edges or segments (represented by strings). Each screw is joined to exactly three others, and the shortest path you can find that follows a string and brings you back to the same screw where you started requires six segments of string. The Heawood graph is the smallest graph with these properties, which means it can be called “extremal.” One of the subjects of the recent conference at UD was extremal graphs.

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

News Story Supporting Images and Text
Used in the Home Page News Listing and for the News Rollup Page
A recent international conference celebrated the work of three prominent graph theorists, including Felix Lazebnik, professor of mathematical sciences at UD.

​An international conference on graph theory included a focus on the work of UD mathematician Felix Lazebnik.

Page Settings and MetaData:
(Not Shown on the Page)
Page Settings
Mathematical Sciences
MetaData for Search Engine Optimization
Connecting the dots