CONTREWA: Combinatorics: new trends and real-world applications

The 3-year project CONTREWA: Combinatorics: new trends and real-world applications is funded by the Agencia Estatal de Investigación (Ministerio de Ciencia, Innovación y Universidades) with reference PID2020-113082GB-I00 and through the call "Proyectos I+D+i 2020" for the period Sept-2021 to Aug-2024.

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 Anna de Mier, Anna Lladó, Marc Noy, Juanjo Rué, Oriol Serra, Lluís Vena.

Description of the project:

Combinatorics is a broad subject with tentacles reaching into many other branches of mathematics. This proposal covers various applications of combinatorics, not only to problems of a purely mathematical nature but also real-world problems arising from complex systems, such as in the study of the world-wide web, epidemiology and quantum computation. Combinatorics is by nature diverse, including probabilistic, geometric, algebraic and analytic methods. The common ground of this proposal relies in the blending of these methods and techniques to address relevant problems and applications which are inserted in the mainstream developments of contemporary research in the combinatorial community worldwide. The combined expertise of the team in these techniques is the identity mark of the research group.

Objective 1 fits inside the active field of arithmetic combinatorics and relates to the additive structure of sets in groups and discrete isoperimetric problems. This subject has its origins in a classical problem dating back to Goldbachs conjecture; that any even number is the sum of two primes. Here, we are interested in Freiman's conjecture which relates the sumset size and its additive volume.

Interconnected systems appear commonly in different real-word situations and are most easily described using graphs. These networks have heterogeneity properties which motivates the study of models that can generate scale-free networks, or even more, networks with arbitrary prescribed degree distribution. This subject, which mathematically is still relatively in its infancy, will be the focus of Objective 2.

The classical graph theoretic problem of colouring has a host of real-world applications not only to the obvious application of the colouring of maps, but to many graph theoretic problems arising in areas such as biology, sociology and economics. In 1995 Stanley introduced the symmetric function generalisation of the chromatic polynomial which has risen a number of interesting questions. One of the central open problems in the area is whether the chromatic symmetric function distinguishes trees. This will be the focus of Objective 3.

The tools of combinatorics, most notably finite projective spaces, have recently come to the foreground in the burgeoning subject of quantum computation. To effectively store and make fault tolerant operations on a quantum system it is imperative to use a quantum error- correcting code. These codes have many similarities with classical error-correcting codes, used in classical communication channels which are subject to noise. Certain geometric objects can be used to describe both classical linear and additive codes and quantum stabiliser codes. This combinatorial application is the central theme of Objective 4.

Objective 5 is two-folded. First, to advance in the enumeration of combinatorially restricted graphs classes, such as planar or bounded tree-width graphs. Enumeration techniques are a powerful approach to derive typical properties of such graph classes. Second, to explore the connections between logic, enumerative combinatorics and random graphs. Most fundamental properties of graphs are expressible in simple logic languages. We aim to understand the shape of the set of limiting probabilities, which is intimately related to phase transitions on random structures.

Grant PID2020-113082GB-I00 funded by MICIU/AEI/10.13039/501100011033.