Homogeneous sets in combinatorial structures with local constraints

• Applicant: Professorin Maria Axenovich, Ph.D.
• Subject Area: Mathematics
• Term: since 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 455779225

One of the key tasks in extremal combinatorics is to understand the behaviour of homogeneous sets, such as cliques in graphs and chains in partially ordered sets (posets).   Erdös and Hajnal observed that forbidding a fixed induced subgraph forces a graph to have a "large" homogenous set, much larger than one could for example observe in a random graph. This initiated  a research program to quantify how the size of a largest homogeneous set depends on local constraints.

 This proposal addresses two specific aspects of this research program:
1. Finding large homogeneous sets in edge-multicolored  graphs with a fixed forbidden color pattern, and 
2. Finding large homogeneous sets in partially ordered sets with a subposet constraint. 

The novel aspects of this proposal is that instead of a graph setting (corresponding to complete graphs edge-colored with two colors), a multicolor setting with a large number of colors is being considered.  While this  setting was not systematically investigated,  it promises not only to provide a much more general statement, but also to shed light into the classical two-color question. 
In addition, it is proposed here to investigate a dual question of  finding forbidden patterns, guaranteeing specific asymptotic behaviour of largest homogeneous sets.  To the best of our knowledge, Erdös-Hajnal’s setting was not addressed for partially ordered sets.  Special subproblems here correspond to Ramsey-type questions for Boolean lattices. This area is poorly understood with only a few relatively weak bounds known. Answering the proposed questions for posets will address the behaviour of large homogenous sets and allow to understand the structure of posets with forbidden subposets; thus in a sense extending Turán-Ramsey theory for posets.

The proposed research is intended to eliminate gaps in the knowledge in these two closely connected areas.  In doing so, it is proposed to combine tools in structural combinatorics giving specific descriptions of discrete objects avoiding fixed substructures  with many powerful tools of extremal graph theory and combinatorics.

• DFG Programme: Research Grants