Professor Jozsef Balogh, a J. Andrew and Susan Langan Scholar, has been awarded a Focused Research Grant by the National Science Foundation (NSF), jointly with Florian Pfender (University of Colorado Denver) and Bernard Lidicky (Iowa State University). This grant supports collaborative groups employing innovative methods to solve specific, major research challenges in the mathematical sciences. Balogh, Lidicky, and Pfender are long time collaborators in the field of combinatorics and, for this project, will work to solve three prominent types of problems in extremal combinatorics: those of Erdős, Turán and Zarankiewicz. Their work will have far-reaching impact in the field of mathematics, with many applications in logic and computer science.
The project's abstract is as follows:
In extremal combinatorics one aims to find and characterize optimal members of a given class of mathematical objects. Those extremal objects often have unique properties and structures, giving insights in many mathematical fields. Over the last twenty years, several new techniques, many using the assistance of computers, have been extraordinarily successful in studying extremal objects. One of the recent powerful methods is based on the theory of flag algebras. This method enables researchers to translate extremal combinatorics questions into instances of semidefinite programs, which can then be explored with the help of a computer and academic as well as commercial software. This translation has led to recent breakthroughs on longstanding open questions. The method is versatile and can be applied in various settings such as graphs, hypergraphs, permutations, oriented graphs, point sets, embedded graphs, and phylogenetic trees. The aim of this focused research group is to resolve three prominent types of open questions by Erdős, Turán, and Zarankiewicz using these techniques.
The three types of questions to be studied share the general flavor of generalized Turán problems, and solving them would have far reaching consequences. The first type are extremal hypergraph questions, the second type concerns finding maximum cuts in graphs with certain properties, and the third type are questions related to the crossing number of graphs. For all three, the use of flag algebras has recently led to significant progress but not to full solutions. This project will combine the expertise of the investigators with a concentrated effort and further method development to resolve these open questions. It is planned to find connections to more traditional methods such as the stability method and linear algebraic methods. A substantial number of students and early-career researchers will be trained and supported at the three institutions, and several focused workshops are planned.