Complex Structures: Regularities in Combinatorics and Discrete Mathematics (CORES)

The project involves four main topics, that represent the central problems of the modern combinatorics, discrete mathematics and computer science. The project concerns research in discrete mathematics and combinatorics with applications to complex network processing in theoretical computer science, and model theory. Tools include geometry, probability theory, and algebra. Algorithmic questions are emphasized. They often motivate, suggest or even dictate the addressed theoretical problems. The problems covered by this project can be grouped into four main areas:

Structure and dichotomies for large structures.
In particular, the study of nowhere dense vs somewhere dense dichotomy, unifying approach to limits. Hierarchy of structures defined by homomorphism. Low tree depth decomposition, degrees of freedom of combinatorial classes. Related questions counting and testing.
Structural Ramsey theory.
Characterization program for Ramsey classes. Quest for models of sparse graphs, Pisier problem on partitions of Sidon sets. Anti-Szemerédi problem sets (defined in a harmonic analysis context).
Extremal problems and decompositions with special properties.
Local-global phenomena for graphs and finite models, related algorithmic, probabilistic and geometric problems, Pentagon problem. Several classical problems (such as Erdös-Hajnal on sparse subgraphs) treated in the new context of logical characterizations of sparse objects and in the context of restricted dualities.
Homomorphisms, Models, Combinatorial Categories.
In particular restricted finite dualities, density and universality of classes, descriptive complexity. Classification problem for homomorphism preservation. Branching vs expanding dichotomy.

Researchers

  • Jaroslav Nešetřil (director)
  • Pavol Hell
  • Vojtěch Rödl
  • Petr Pančoška
  • Andrew Goodall
  • Patrice Ossona de Mendez
  • Robert Šámal
  • Jan Hubička