Extremal and Probabilistic Combinatorics with Applications

University Of South Carolina At Columbia, Columbia SC

Investigators

Abstract

Motivated by various problems from other disciplines and also from the internal development of discrete mathematics, the demand steadily increases to understand "optimal" extreme structures and "typical" random structures in discrete mathematics.This project will investigate basic combinatorial questions about structures and will look for various applications of discrete mathematics in computer science, biology, and engineering. The principal investigators build on their previous work in combinatorics and graph theory in the areas of extremal graph, hypergraph and poset theory, graph visualization and graph drawing, random graph models and probabilistic combinatorics to attack fundamental questions in extremal set theory, extremal graph theory, and in areas closely related to them. These fundamental questions include the 70 years old Turan problem, one of the toughest problems in extremal combinatorics; the excluded subposet problems, results on which are just solidifying into a theory; and building a Turan hypergraph theory bridging the two areas above, offering new insight for both. Notwithstanding the efficacy of spectral methods in graphs theory and different analogues of it for hypergraphs, there is not yet a coherent spectral hypergraph theory. Lu and Peng made an attempt to unify different versions of Laplacians for hypergraphs. A key direction of the project is building further the spectral analysis of uniform hypergraphs based on their Laplacian. For 40 years, the Lovasz Local Lemma has been the tool to find the proverbial needle in the haystack. The principal investigators introduced a technique to use the lopsided version of the Lovasz Local Lemma for asymptotic enumeration of combinatorial objects. The project will extend the range of asymptotic enumeration problems where this method applies, by finding new classes of problems where the lopsided Lovasz Local Lemma applies. The study of crossing numbers of graphs, and of the structure of generalized Sperner families is also among the goals of the project. The applied prong of the project is expected to have an impact on other sciences. In particular, investigating models for sequence evolution and phylogeny reconstruction is relevant for the mathematical foundation of bioinformatics, investigating extremal and structural properties of tree indices has relevance for mathematical chemistry, working on crossing numbers of graphs in different models of drawing is relevant for computer science. Some probabilistic and spectral results of this project will be relevant for network science. The principal investigators continue their interdisciplinary collaborations with colleagues from engineering, biology, statistics, and computer science, and continue the training of successful graduate students.