Extremal and Probabilistic Combinatorics with Applications

University Of South Carolina At Columbia, Columbia SC

Investigators

Abstract

This research project investigates basic combinatorial questions about discrete structures and explores applications of discrete mathematics in computer science, biology, and engineering. The investigators continue their work on extremal graph, set, and hypergraph theory and forbidden configurations. They investigate connections between graph theory and geometry, on the one hand studying Ricci curvature on graphs, on the other hand studying crossing numbers of graphs and related incidence problems. The project will study graph and tree indices originating in chemical graph theory and will apply combinatorial and probabilistic techniques to phylogenetics and to the theory of complex networks. Results of the project will contribute to the better understanding of key phenomena in network science, of discretization of geometric space, of phylogenetics, and of other fields. The investigators will continue the training of Ph.D. students through involvement in the research, introducing them to interdisciplinary and international research collaboration. The project will contribute to the understanding of "optimal" extreme structures and "typical" random structures in discrete mathematics. This area is referred to broadly as extremal combinatorics, and some of the main open questions in the area will be studied, including various instances of the Turan problem for graphs, hypergraphs and posets, problems in combinatorial geometry, in the vein of the Erdos unit distance problem and crossing and incidence problems, and combinatorial questions on trees such as the Maximum Agreement Subtree problem as well as topics related to chemistry. This project will build upon sophisticated methods that have been developed to attack these problems, such as the approach via crossing numbers and incidences, the Guth-Katz low degree polynomial method, and the generalization of the notion of Ricci Curvature from differential geometry to graphs, which allows, to some extent, functional analytic tools to be brought to bear.