The investigators continue their work on graph drawing and crossing numbers, random graph models, phylogeny reconstruction, and on fundamental questions of extremal set and graph theory and discrete geometry. In particular, they will focus on Turan's hypergraph problem, on novel applications of the lopsided Lovasz Local Lemma, on Sperner type and extremal poset problems. They will use combinatorial and probabilistic techniques in phylogenetics and in the theory of complex network.
Scientific and engineering breakthroughs in many fields have spurred the development of new theory and algorithms for discrete structures. There is increasing demand 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.
Since 1973, the Lovasz Local Lemma has been the tool to find the proverbial needle in the haystack, i.e. the way to prove the existence of certain elements of negligible probability in a probability space. Lu and Szekely in this project developed a theory to use the Lovasz Local Lemma to count the needles in the haystack - at least in some categories of problems. Lu and his collaborators developed a new field between Turan theory and Katona type extremal set problems. Turan type problems for non-uniform hypergraphs connect these two major areas, and offers hope to handle major open problems, like the "diamond problem" in extremal set theory. Lu and his students started to develop Laplacian spectral analysis of hypergraphs, relevant for investigating random walks on hypergraphs. Not much of Laplacian spectral analysis of hypergraphs existed so far. Szekely and his collaborators developed a connection between M-part Sperner theory and mixed orthogonal arrays. Roughly speaking, a family of Bollobas-Lubbel-Yamamoto-Meshalkin type inequalities all hold with equalities for a k-dimensional M-part Sperner multifamily if and only if a mixed orthogonal array of constraint M and strength M-k is present. In addition, they provided constructions for mixed orthogonal arrays using only rounding, instead of the usual constructions based on finite fields or other designs. The PI's graduated two Ph.D. students, Austin Mohr and Xing Peng, who stay in academia.They work currently with 4 Ph.D. students. Szekely took his student, Heather Smith, to a one-month research visit to the Renyi Institute in Budapest from other resources. Szekely and Lu were the main organizers of a 2-week Summer School on Network Science, held in May 2013 at the University of South Carolina. 50 students, postdocs and junior faculty from different disciplines attended the lectures of about 10 invited speakers. Attendees came from as far as Poland and Switzerland, while speakers came from as far as Singapore, the Netherlands and Canada. Four invited star speakers, Fan Chung, Joel Spencer, Remco van der Hofstad and Peter Mucha gave 5-5 hour lecture series. See http://imi.cas.sc.edu/events/summer-school-network-science/
