COCOA: Contemporary Combinatorics and its Applications

The 3-year project COCOA: Contemporary Combinatorics and its Applications is funded by the Agencia Estatal de Investigación (Ministerio de Ciencia, Innovación y Universidades) with reference PID2023-147202NB-I00 and through the call "Proyectos de Generación de Conocimiento 2023." for the period Sept-2024 to Aug-2027.

The Principal investigators of the project are Simeon Ball and Guillem Perarnau. Most of the members of GAPCOMB participate in the Resarch or the Work team of the project, including the following faculty of the group Richard Lang, Anna de Mier, Marc Noy, Clement Réquile, Juanjo Rué, Oriol Serra and Lluís Vena.

Description of the project:

Combinatorics is a broad discipline in the forefront of modern mathematics extending its influence across many other scientific fields. This proposal explores a wide variety of its applications, both of purely mathematical nature and delving into the realm of complex systems such as the world-wide web, sociology, telecommunication, and quantum computation. Approaches to combinatorial problems are inherently diverse, encompassing algebraic, analytic, geometric and probabilistic tools. The combined expertise of the team in these methods is the identity mark of our research group and will allow us to address open problems and new trends in the area. Given its broad spectrum, the project will be led by two principal investigators with complementary expertises.

The research content of the project is split into 7 interrelated tasks, each containing a number of specific objectives.

Task 1 fits inside the active field of arithmetic combinatorics. The main focus will be on understanding the structure and number of sumsets in different arithmetic settings, such as Euclidian spaces or groups which do not contain solutions of particular linear equations.
Graphs are used to model interconnected complex systems arising in areas such as biology, sociology or economics.

Task 2 aims at obtaining new understanding of algebraic graph invariants. We will pay particular attention to Tutte polynomial, graph homomorphisms and the chromatic symmetric function associated to a graph, and determine their distinguishing properties.
Random graph models are particularly useful for real-world networks. However, randomness limits their applicability to study fluctuations in networks.

Task 3 will study fundamental questions such as how robust are networks to failures, how additional connections can enhance their features or how noise can distort them. There are many applications of perturbed neworks, for instance they provide excellent small- world networks models. Objectives within this task will have direct consequences on the topics of Task 2.

Combinatorial tools, most notably finite projective spaces, have led to recent progress in quantum computation. To effectively store and make fault tolerant operations on a quantum system it is imperative to use quantum error-correcting codes, closely related to classical error-correcting codes. Certain geometric objects can be used to describe both classical linear-additive codes and quantum stabiliser codes, which is the central theme of Task 4.

Ramsey theory describes the phenomenon that large graphs always have small ordered parts. Task 5 aims to build on new breakthroughs in determining Ramsey numbers, by the integration of probabilistic techniques (with the same spirit as Task 3) and finite geometry (as developed in Task 4).

Task 6 aims to build on our enumerative knowledge of graph classes and its probabilistic counterpart. We will use new techniques combining generating functions and tools derived from complex analysis in the context of social choice theory, where the enumerative techniques have not been exploited yet.
Finally, we focus on the study of large networks using graph limits.

In Task 7 we aim to find limits at a micro- and macroscopic level for classes of graphs, including random ones, and study the relation between the different limit notions and their applicability to large networks. Probabilistic techniques will be key in the development of the objectives, as in Tasks 3 and 5