CoSP — Combinatorial Structures and Processes

Results in brief

Combinatorial Structures and Processes

CoSP addresses international collaboration in discrete mathematics and theoretical computer science. Experts from different continents and different domains will work with each other and with students in various stages of their studies. This project aims to develop various skills increasing the career prospects of the involved researchers and students both in academia and in industry. The fields of research are: (a) Matching theory for graphs and hypergraphs, (b) Algorithms and complexity, (c) Graph homomorphisms. We concentrate on graph theory - a basic field in combinatorics, that deals with connections between pairs of objects. This has innumerably many applications, from communication to kidney transplants (applications to the latter led to a recent Nobel prize) and to theoretical physics. Specific lines of research: • Understanding the mysteriously good behavior of the intersection of two matroids with respect to representation and coloring problems. • Designing a (1+ε)-approximation algorithm for edit distance running in almost linear time. • Proving a super-linear lower bound for circuits of logarithmic depth. • Algorithmic approaches to coloring of random regular, large girth and Erdős–Rényi graphs. • A long-standing conjecture called the Pentagon problem which states that all sub-cubic graphs of large girth are 5-circular colorable. • Algorithmic approaches to the planted Travelling Salesman Problem with random weights on the edges. • Algorithmic and combinatorial approaches to problems coming from statistical physics. • The classification of classes of structures defined by forbidden homomorphisms in the context of Ramsey theory, model theory and topological dynamics. A key part of our project is aimed at the exchange and training of the early stage researchers.

Data: CORDIS, © European Union

Project objective

The project brings together combinatorialists of various fields with the aim that they will enrich each other’s techniques. The tool kits they will bring include topology, probability, statistical physics and algebra. These should apply to matching problems (a central topic in combinatorics), algorithmic problems, coloring problems (which are decompositions into independent sets or matchings) and homomorphisms (a generalization of colorings).One umbrella under which many of these can be gathered is the intersection of two matroids, a notion generalizing that of matchings in bipartite graphs. Researchers are baffled by a strange phenomenon – that moving from one matroid to the intersection of two matroids sometimes costs little. The algorithmic problems are indeed harder, but the difference between min and max in the min-max theorems suffer only a conjectured penalty of 1.This connects with a second direction of the research, fine grained complexity, which deals with polynomially solvable problems, and aims to prove, under widely believed assumptions, lower bounds on the exponents in the polynomial bounds. A major question in the field is proving similar tight bounds for approximation problems.A direction connecting matchings, colorings and homomorphisms was initiated recently in statistical physics. It investigates typical algorithmic complexity, of computational problems taken under some probability distribution. While the worst case complexity questions are difficult in general and not clearly practically relevant, when we restrict to a given probability distribution of instances and when we are interested in high probability results, progress has been made, that has contributed also algorithmic insights beyond the probabilistic setting. We propose to address several outstanding open questions from the field.Finally we will work on a deep connection, studied by some of the researchers in the project, between Ramsey theory, Model theory and graph homomorphisms.

Original text from CORDIS.

Participants

UNIVERZITA KARLOVA · Praha 1CoordinatorCzechia
CENTRE NATIONAL DE LA RECHERCHE SCIENTIFIQUE CNRS · ParisFrance
Los Alamos National Security LLC · Los Alamos NmUnited States
RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY · New BrunswickUnited States
Simon Fraser University · BurnabyCanada
TECHNION - ISRAEL INSTITUTE OF TECHNOLOGY · HaifaIsrael
THE REGENTS OF THE UNIVERSITY OF CALIFORNIA · OaklandUnited States
TRUSTEES OF PRINCETON UNIVERSITY · Princeton, NjUnited States

CoSP · Combinatorial Structures and Processes

Results in brief

Combinatorial Structures and Processes

Project objective

Participants

Links