Extremal Combinatorics

University Of Illinois At Chicago, Chicago IL

Investigators

Abstract

The PI and his coauthors will work on extremal problems for set systems or hypergraphs using combinatorial, algebraic, probabilistic, and topological methods. The basic problem of extremal hypergraph theory is the so called Turan problem: determine the maximum number of subsets a finite set can have without containing some fixed forbidden configuration. This question, in its full generality, is very difficult, and certain special cases are famous problems that have been open for over 50 years. Nevertheless, substantial work on closely related issues has occurred recently, and the limits of this recent progress will be explored. Although several different aspects are considered (Ramsey-Turan problems, jumps in hypergraphs, degenerate problems for simplices), the common theme is to obtain a hypergraph analogue of the Erdos-Simonovits-Stone theorem, the cornerstone of extremal graph theory. The general topic of finite set systems has connections to diverse areas of mathematics (combinatorial geometry, design theory, partially ordered sets, additive number theory), and also to academic disciplines with concrete applications in everyday life (coding theory, information theory, optimization and scheduling problems, computer science). Modern communication would be impossible without the existence of codes, or objects designed to relay information faithfully even in the face of distortion. Extremal problems for set systems play a role in constructing codes for various situations.