Extremal Problems Concerning Forbidden Subgraphs

点击翻译按钮获取中文摘要

The PI will study forbidden subgraph problems, namely the Turan andsaturation functions, as well as positional games. It is hoped that abetter understanding of some of the key topics, such as the Turan density,exactness results, stability, jumps, and non-principality phenomena willbe achieved. The PI will work on enlarging the list of forbiddenhypergraphs for which the complete solution has been obtained. Also, themore general setting of the above problems, wherein the restriction ofcontaining no forbidden subgraph is replaced by an arbitrary propertyexpressible in first order logic, will be considered. Another direction ofresearch is to study positional games, such as Breaker-Maker, coloring,and symmetry games. In particular, the PI will continue the previousinvestigation of the first order descriptive complexity of combinatorialstructures, in which the Ehrenfeucht game is an indispensable tool.The proposed topics of extremal combinatorics comprise many important anddifficult problems, some of which have withstood decades of attempts. Thisarea is rich in connections to other fields, such as the probabilisticmethod, linear algebra, codes, design theory, and finite fieldconstructions. Also, the investigator's work on positional games and firstorder properties, which play an important role in combinatorics, computerscience, and logic, may potentially lead to improvements in redundancy andrepresentation algorithms for combinatorial data.