Extremal graphs, hereditary and random structures

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

The PI and the co-PI study how l o c a l properties affect the g l o b a l parameters of various combinatorial structures. This is a very general framework of the so-called Turan number problems. The PI and the co-PI emphasize five different aspects: Turan numbers of triple systems, cardinalities of hereditary families, geometrical/algebraic representations of graphs where Turan numbers naturally emerge, they study more general coding theory problems, and investigate random combinatorial structures, especially the phase transition of various models of bootstrap percolation. Combinatorics, in other words Discrete Mathematics, studies finite, but large structures, many of them arising from computer science. Combinatorics is the theoretical basis of coding theory, computer graphics, computer science, cryptography and communication theory. Combinatorists are looking for economical, fast and reliable ways to store and search data structures. A wide variety of combinatorial problems deal with l o c a l properties, or use local probabilities in order to determine (or estimate) global parameters to describe the bigger picture. This effect of local properties on global parameters is the subject of this proposal.