Extremal Problems Concerning Forbidden Subgraphs

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

The PI will study forbidden subgraph problems, namely the Turan and saturation functions, as well as positional games. It is hoped that a better understanding of some of the key topics, such as the Turan density, exactness results, stability, jumps, and non-principality phenomena will be achieved. The PI will work on enlarging the list of forbidden hypergraphs for which the complete solution has been obtained. Also, the more general setting of the above problems, wherein the restriction of containing no forbidden subgraph is replaced by an arbitrary property expressible in first order logic, will be considered. Another direction of research is to study positional games, such as Breaker-Maker, coloring, and symmetry games. In particular, the PI will continue the previous investigation of the first order descriptive complexity of combinatorial structures, in which the Ehrenfeucht game is an indispensable tool. The proposed topics of extremal combinatorics comprise many important and difficult problems, some of which have withstood decades of attempts. This area is rich in connections to other fields, such as the probabilistic method, linear algebra, codes, design theory, and finite field constructions. Also, the investigator's work on positional games and first order properties, which play an important role in combinatorics, computer science, and logic, may potentially lead to improvements in redundancy and representation algorithms for combinatorial data.