Applied Mathematics’ Kaul Leads Conference at Illinois Tech on Extremal Combinatorics

Date

More than 140 mathematicians from all over the world participated in EXCILL III: Extremal Combinatorics at Illinois, a conference on the latest in extremal combinatorics held on Illinois Tech’s Mies (Main) Campus from August 8-10.

A highlight of the conference was the presentation by Peter Keevash, professor of mathematics at Oxford University, of his proof of existence of designs, answering a major unsolved problem from 1853.

Hemanshu Kaul, associate professor of applied mathematics, organized the conference with colleagues from University of Illinois at Urbana-Champaign, University of Illinois at Chicago, Miami University, and College of William and Mary. Local arrangements were managed with the help of Michael Pelsmajer, associate professor of applied mathematics, and other members of IIT’s applied mathematics community, including Gladys Collins, Jeffrey Murdock, Benjamin Reiniger, William Schwartz, Despina Stasi, Dane Wilburne, and Kan Zhang.

“The speakers were like a Who’s Who of the research field from North America, South America, Europe, and Asia,” said Kaul. “It would be a big deal for a conference to have just had three to four speakers of that caliber, let alone 20-plus.” Distinguished participants included members of national academies of science, winners of mathematical prizes, a MacArthur Fellow, and more, including Noga Alon of Tel Aviv University, Maria Chudnovsky of Princeton University, Lazslo Babai of the University of Chicago, Jacob Fox of Stanford University, and Zoltan Furedi of the University of Illinois at Urbana-Champaign and Hungarian Academy of Sciences.

The EXCILL III conference was supported through grants awarded by the National Science Foundation and National Security Agency on which Kaul is principal investigator; by the College of Science dean’s office; and by the Department of Applied Mathematics.

Extremal combinatorics studies fundamental mathematical questions inspired by how small or large certain mathematical structures—such as graphs (networks), geometric configurations, or natural numbers—can be. A graph (or network) is simply an ensemble of pairwise relations (like friendship, interaction, link, reaction, etc.) between objects (like humans, animals, webpages, molecules, etc.) which is widely used for modeling in modern applied mathematics, computer science, statistical physics, etc.

An example of such an extremal problem is the classic Turan-type problem, which in non-mathematical terms asks in graph (or network) what are the minimum number of pairwise relations that guarantee the existence of a large clique. Another example is the graph coloring problem which asks for minimum number of colors needed to “color” a graph so that there are no conflicts between objects of the same color. The most famous example of this is the four-color problem, which asked whether regions of any map can be colored using at most four colors such that like-colored regions are not adjacent to each other. This question was finally answered in the affirmative in the 1970s, after more than 120 years of work by mathematicians. Coloring of graphs has diverse applications in such areas as scheduling problems, time tabling, pattern matching, and allocation problems.