Results
The first year of CoSP was blasting with exciting activities, all the planned activities and research started in an exciting way and solid foundations of top level research were laid. Training by research and in transferable skills was very successful and we also had diverse communication activities.
The second year, the year of the pandemic, the conditions drastically changed. In fact, the traditional academic ‘business’ stopped. Exactly during this period, the project proves to be substantial. The research contacts continue on-line and thanks to the connections established the first year, the research outputs are very good. Arguably the biggest success are the training activities at the Rutgers University done remotely. Collaboration on CoSP has continued via online collaboration and training during COVID-pandemy. Thanks to flexible and creative approach of experienced and early-stage researchers, deliverables and milestones which could be reached via online methods were achieved.
First year of CoSP implementation showed its added value for researchers in the field of discrete mathematics and theoretical computer science. Both early stage researchers and experienced researchers, men as well as women benefited from the international collaboration with experts of different domains. Training was provided mainly as ‘training by research’ and in the transferable skills, in order to increase the career prospects of the involved researchers. The early stage researchers were provided multidisciplinary training through mobility, networking and contacts with their peers from different countries and continents. They benefited from direct collaboration with experienced researchers. Researchers spent on secondments 34,91 months from beneficiary institutions and 3,15 months from partner institutions during the first year. It is only 11,94 months less than planned (9,09 months less by beneficiaries and 2,85 months less by partner institutions).
Second year of CoSP implementation (2020) was reversely influenced by worldwide COVID pandemy and travel restrictions connected to that. Since mid-February 2020, secondment preparations were cancelled and no secondments started from February until the end of 2020. This has caused underspending of 32,73 months in 2020. Researchers from beneficiary institutions spent 22,26 months on secondments. There was no incoming secondment to beneficiaries. It is 26,734 months of secondments less than planned by beneficiaries and 6 months less by partner institutions.
In case of secondments, which started before the COVID pandemy outbreak, we took measures in order to protect health of researchers (esp. teleworking) and secondments were prolonged until the situation calmed down and researchers could return safely home. Research collaboration and training in project was altered to online collaboration and training, so that the project implementation continued in a limited way given current circumstances.
Summarising, during the first two years the research has been conducted in all three areas of the project:
(a) Matching theory for graphs and hypergraphs,
(b) Algorithms and complexity,
(c) Graph homomorphisms.
Work Package 1 – Mysteries of the intersection of two matroids
Work in the first work package was done mainly by Martin Loebl (two secondments at Princeton University), Ron Aharoni and Ron Holzman (secondments at Princeton University).
During his secondments, Martin Loebl was working with Maria Chudnovsky (Princeton University), Paul Seymour (Princeton University) and Ron Aharoni (Technion). Martin Loebl further discussed math with Sophie Spirkl, former doctoral student of Paul Seymour, and with Cemil Dibek, a current doctoral student of Maria Chudnovsky. Cemil later visited Charles University in June 2019 on a CoSP secondment. Martin Loebl also discussed math with Jeff Kahn and Michael Saks (Rutgers University) and with Yuval Peled (Courant Institute).
In 2020, Martin Loebl discussed extensively the topological methods with the participants of the CoSP seminar on topological methods (remotely) which resulted in a surprising application of these methods in the joint paper “Arc-routing for winter road maintenance” with Jirka Fink and Petra Pelikanova (in preparation).
Ron Aharoni talked to Noga Alon, Maria Chudnovsky and Paul Seymour. Ron Aharoni also talked to Mike Saks, Sophie Spirkl and Jeff Kahn in Rutgers and with Ron Holzman, see below.
During his secondment ending in October 2020, Ron Holzman continued a collaboration with Ron Aharoni and Joseph Briggs from the Technion, and Zilin Jiang from MIT, which resulted in the paper "Rainbow odd cycles".
Ron Holzman also started a collaboration with Boris Bukh and Ting-Wei Chao from Carnegie Mellon University, which resulted in the paper "On convex holes in d-dimensional point sets".
He also started a collaboration with Noga Alon from Princeton University on the size of k-uniform families with intersecting symmetric differences and related questions. This is ongoing exciting research. As well as a collaboration with Shay Moran from Google AI Princeton on epsilon approximation for product distributions and related questions.
Task T1.1 – Study Conjecture 1 of Aharoni and Berger and Rota’s bases conjecture
We worked mainly on the following problems:
A question on the ratio between the domination number of a graph and the independence domination number (the maximum, over all independent sets, of the minimal number of vertices dominating it). It is known that in chordal graphs the two are equal, and in line graphs the ratio is at most 2. We discussed other classes of graphs, and proved, e.g., that the ratio is at most 2 in the complements of chordal graphs. We conjecture that the ratio is bounded in C_4-free graphs.
A well-known theorem of Haxell is that if a graph with maximum degree d is partitioned into sets of size k that is at least 2d, then there is a transversal of these sets that is independent in the graph. We conjecture that it is enough to assume that the average degree in each set is at most k/2. We tried this problem, so far with no progress.
(Aharoni, Loebl and Saks) Mutually orthogonal clutters, and mutually orthogonal polytopes. There are exciting conjectures, and we made some progress on some of them.
Task T1.2 – Study Conjecture 2 of Aharoni and Berger
Martin Loebl conjectured that there are only exponentially many different d-connected graphs with minimum degree d and bounded maximum degree (as a function of the number of vertices) avoiding a given d-connected topological minor H with maximum degree at most d. Martin Loebl with Paul Seymour and Maria Chudnovsky managed to completely solved this question in the paper M. Chudnovsky, M. Loebl, P. Seymour Small Families Under Subdivision (2019).
The motivation in this investigation has been a long-standing extensively studied conjecture of B. Durhuis: is the number of different triangulations of the 3-ball only simply exponential in the number of tetrahedra? The motivation of this conjecture is from the theoretical
physics, namely whether certain quantum field theory makes sense. The work of Chudnovsky, Loebl, Seymour established an important step towards a possible combinatorial resolution of the conjecture.
Martin Loebl finished, after helpful discussions with colleagues in Princeton and Rutgers, the paper “The Precise Complexity of Finding Rainbow Even Matchings”.
Work package 2 – Algorithms and Complexity
Work in the second package was done by Michal Koucký during his two secondments at Rutgers and Robert Šámal at Simon-Fraser University.
Michal Koucky studied the fundamental algorithmic problem of sorting together with Michael Saks.
Another collaboration resulted in the paper Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, and Michael Saks. Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time.
Another but related collaboration with Sask is on a close connection between circuit complexity of sorting and a well-known conjecture on network coding.
During his stay at Simon Fraser University Robert Samal worked mainly with Bojan Mohar, Matt DeVos, David Wood and Tomáš Masařík. The main project of WP 2 he worked on is the Pentagon problem.
Researchers from CNRS had to reschedule or cancel their secondments, which were planned for the first year (for detailed explanation see WP 6 Management). The collaboration on CoSP in CNRS took place remotely without secondments; however, several results were reached.
Task T2.1 – Study the edit distance and related problems
Michal Koucký studied the fundamental algorithmic problem of sorting together with Michael Saks. On one hand the goal is to prove circuit lower bounds for it, on the other hand the goal is to design new algorithms for settings where an optimal algorithm is still not known, such as sorting large integers. The circuit complexity of sorting was recently connected to the cryptographic problem of designing oblivious RAM. A lower bound on the complexity of oblivious RAM would imply a lower bound on circuit size for sorting. Koucky with co-authors recently obtained a lower bound for restricted oblivious RAM and the goal is to address now the "easier" problem of sorting circuit size. Koucky with Saks made some partial progress in understanding the problems, and they further continue working on the problems.
Task T2.2 – Study composition and simulation theorems in communication complexity and prove circuit lower bounds
While seconded at the Rutgers University, Michal Koucky worked together with Mike Saks on a close connection between circuit complexity of sorting and a well-known conjecture on network coding. This is not a coincidence as sorting requires circuits (resp. the graphs of their connections) to have super-concentrator like properties. There are known techniques for proving lower bounds on the size of graphs implementing super-concentrators and the research effort is to exploit the structure of these graphs for proving the circuit lower bounds in the case of circuits of logarithmic depth that consist of fan-in two gates.
There seems to be a roadblock for proving these lower bounds which resembles a similar issue when trying to prove lower bounds for data structures. This is an issue with recovering efficiently information about a part of an input from an encoding of the whole input. Similar issue but not the same also comes in the problem of locally decodable codes. I tis an ongoing cutting edge research direction to connect all the three areas.
Task T2.3 – Algorithmic approaches to coloring of random regular, large girth and Erdős-Rényi graphs
In this task we aim to search for an ensemble of random graphs that will lead to the smallest possible colorability threshold. The technique to achieve this is via large deviations calculation. We have not yet found a way to perform this calculation in the graph colouring problem but Lenka Zdeborová with collaborators realised that it is considerably simpler in the problem on perceptron, where it has very relevant applications to active learning in artificial neural networks. This is work in progress.
A related work is to consider the statistical inference problem of recovering an unknown perfect matching, hidden in a weighted random graph, by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted matching. Our results are published in the paper “Recovery thresholds in the sparse planted matching problem“.
This research has independent interest in particular in machine learning, and for the purpose of the present project serves as a simpler case to develop the large deviation technique on random graphical models. We will continue working on other applications of this large deviation technique.
Robert Samal with Bojan Mohar and Tomáš Masařík studied properties of random embeddings. This is a topic with enticing connections to statistical physics, structural graph theory and with possible algorithmic applications. A breakthrough in finding the asymptotically tight estimate of the expected number of faces of a complete graph, of random cubic graphs, and also random dense graphs is achieved.
Task T2.4 – Study of the Pentagon problem
Robert Šámal discussed with Lenka Zdeborová the status of statistical physics approach to the Pentagon problem. He then compared this with what was achieved by people working in graph theory (Luis Goddyn and his former PhD student Mohammad Ghebleh). The preliminary outcome is that statistical approach leads to faster heuristics but so far without sufficient theoretical understanding. Graph theorists have a nice theory related to this problem (circular coloring), but many parts are still missing.
During his secondmend, Robert Šámal worked on the problem with Bojan Mohar, Matt DeVos, Luis Goddyn and David Wood, discussing possible approaches and their limitations.
Task T2.6 – Inference problems in Graphical Models
Algorithmic properties of high dimensional inference problems are surrounded by many open questions. Lenka Zdeborová with collaborators managed to solve an important among those problems, leading to an article “Marvels and Pitfalls of the Langevin Algorithm in Noisy High-Dimensional Inference” that appeared in a prestigious journal Physical Review X. Gradient-descent-based algorithms and their stochastic versions have widespread applications in machine learning and statistical inference. An analytic study of the performances of one of them is performed, namely the Langevin algorithm, in the context of noisy high-dimensional inference. We employ the Langevin algorithm to sample the posterior probability measure for the spiked matrix-tensor model. The typical behaviour of this algorithm is described by a system of integro-differential equations that we call the Langevin state evolution, whose solution is compared with the one of the state evolution of approximate message passing (AMP). Our results show that, remarkably, the algorithmic threshold of the Langevin algorithm is sub-optimal with respect to the one given by AMP. We conjecture this phenomenon to be due to the residual glassiness present in that region of parameters. Finally, we show how a landscape-annealing protocol, that uses the Langevin algorithm but violate the Bayes-optimality condition, can approach the performance of AMP.
Work package 3–Graph homomorphisms
Work in the third work package was done by Robert Šámal and by Jan Bok during their secondments at Simon Fraser University and by Jan Hubička and Matěj Konečný during their secondments at Rutgers University.
Robert Šámal was working mostly with Bojan Mohar and Matt DeVos (both SFU) on several problems related to graph homomorphisms.
Jan Bok was working with Pavol Hell (SFU) and Nikola Jedličková (CU) on algorithms for graph homomorphisms (connections with Work package 2) and on the structure of homomorphisms for interval graphs.
Jan Hubička and Matěj Konečný collaborated with Gregory Cherlin on the study of homogeneous structures.
Task T3.1 – Study of counting questions for graph homomorphisms
Robert Šámal with Bojan Mohar, Matt DeVos and Rikke Marie Langhede (PhD student of Carsten Thomassen) worked on a counting problem for group connectivity (a dual version of graph coloring/homomorphism). We merge approach by Jaeger et al. with that of Seymour and find a certain dual of Thomasen's result (exponentially many list 5-colorings of planar graphs). We are currently preparing the paper for publication, we will finish it in early 2020.
Robert Šámal also finished his older paper with Matt DeVos on 3-Flows with Large Support, the paper is currently accepted to JCTB.
Task T3.2 – Study of structure of homomorphisms
Robert Samal with Bojan Mohar and David Wood worked on the problem of a simple graph containing all countable planar graphs. They found that such graph must necessarily contain an infinite complete graph as a minor. On the other hand, an explicit construction was found of a graph that contains all countable planar graphs and has good structural properties (sparsity, tree width, ...). This is an on-going research.
Robert Samal with Matt DeVos were discussing possible approaches to Bouchet conjecture (bidirected graphs have a nowhere-zero 6-flow). After several failed attempts, they found what they believe to be the right approach and are progressing to obtain a proof (so far only in a special case: cubic graphs of high cyclic connectivity).
Jan Bok, together with Pavol Hell and Nikola Jedličková obtained a partial dichotomy for the list homomorphism problem for signed graphs. They continued on the same topic also during the Bok’s secondment in 2020.
Proving the full dichotomy is work in progress. List versions of homomorphism problems have been much studied for non-signed graphs and digraphs. Dichotomies and concrete classifications of complexity for the list homomorphism problem are known for reflexive graphs, irreflexive graphs, arbitrary graphs, and arbitrary digraphs and dichotomy is known for even more general relational structures.
The second project of the same research group was focused on extending partial orderings of adjusted interval digraphs. Adjusted interval digraphs have been studied as the right digraph analogue of interval graphs. For interval graphs, there are polynomial algorithms to extend a partial representation by given intervals into a full interval representation.
During the first secondment, Bok with co-authors introduced a similar problem – extending partial orderings. A polynomial algorithm for extending a partial ordering of adjusted interval digraph was provided.
The problem is deeply connected with the complexity of graph homomorphisms, since adjusted interval digraphs have the property that the list homomorphism problem for reflexive digraphs is polynomial for them. A result such as this can shed more light on understanding the structure of adjusted interval digraphs which can then lead to designing more efficient algorithms for graph homomorphism problems and, possibly, to solving the conjectured dichotomy of list homomorphism problem on reflexive digraphs.
They further focused on providing dichotomy to all trees in general (the so-called mixed trees). They provided a partial catalogue of NP-complete instances and proved about several mixed trees that they are polynomial by employing a polynomial algorithm, building upon the existing result on reflexive trees. It now remains to prove that the remaining cases are indeed polynomial, which is the current work in progress.
Task T3.3 – Study of Ramsey properties of classes with forbidden homomorphisms
Jan Hubička and Matěj Konečný collaborated with Gregory Cherlin on the study of homogeneous structures, in particular attempting to classify (primitive) 3-constrained metrically homogeneous graphs using results on homogenizations of families given by forbidden homomorphisms of Hubička and Nešetřil. As a result, they produced a very early draft which firstly isolates a combinatorial lemma giving sufficient conditions (in terms of a family of forbidden homomorphisms) for an amalgamation class to be determined by triangle constraints and the so-called Henson constraints, and secondly applied this lemma to obtain the existing catalogue of primitive 3-constrained metrically homogeneous graphs of finite diameter. This proves the completeness of the catalogue in the case of finitely-constrained classes (first such proof) and moreover explains the inequalities between the 5 relevant parameters. This result is probably the strongest evidence for the completeness of Cherlin's catalogue of metrically homogeneous graphs.
Cherlin, Hubička and Konečný also tried using the aforementioned lemma to prove the Lachlan-Woodrow catalogue of countably infinite homogeneous graphs. This didn't seem to be possible, however, they were able to isolate some examples where various possible strengthenings of the lemma fail (i.e. symmetric analogues of the semigeneric tournament or the generic local order), thereby giving clear boundaries for the method which one can then study closer.
Finally, several other topics were also briefly discussed, such as possible classifications of homogeneous hypertournaments (Cherlin has a list of finite ones), their “switching reducts”, and parametrized families of linear orders, EPPA for tournaments and various complexity questions concerning classifying amalgamation classes given by forbidden homomorphisms (WP2+WP3).
Work package 4 –Training
We train our students today in order to have stellar researchers tomorrow. In total, several dozens students took part in our training programmes, ranging from a week to two months of duration.
Task T4.1 – Training by research during the training secondments in RU-DIMACS and in CU
2019 Our research experience for undergraduates (REU) program had two parts in 2019. In two months spent at RU-Dimacs students worked on a research project of their choice. As a side note, our project passes the Bechdel–Wallace test, one of the research groups was formed entirely by girls. The students worked on the following research areas.
Compression – Pavel Dvořák, Lukáš Ondráček, Jakub Pekárek
A research group under mentoring of Periklis Papakonstantinou. The group studied space compression of Turing machines and depth compression of circuits and get some partial results about one-tape Turing machines and multi-tape Turing machines, where there is only one read-write tape and others are read-only tape.
Biased random walks – Petr Chmel, Jan Petr, and Mikhail Beliayeu
A group mentored by Dr. Bhargav Narayanan, Assistant Professor of Mathematics at the Rutgers University. The group of mentees studied a particular case of biased random walks – the so-called geodesic-biased random walk. They disproved the existence of a polynomial bound on the geodesic-biased random walk's expected hitting time for graphs with unbounded degree and a constant number of excitations as well as graphs with bounded maximum degree and number of excitations roughly proportional to the square root of the number of vertices in the graph by constructing examples of graphs with superpolynomial expected hitting times.
Their results form the basis of the article "Slowdown for the geodesic-biased random walk", which is now published in the electronic open-access journal Electronic Communications in Probability.
A game problem in extremal combinatorics –Andrej Dedik, Jan Soukup.
Tutored by Dr. Sophie Spirkl. The work in question was about a graph game which was used a supplemental method in improving the bound of Erdos-Hajnal conjecture researched by the tutor herself. The students improved the existential proof giving a foundation for an upper bound into much more specific bound for given graphs such as trees, paths, circles and bipartite graphs.
Rainbow structures – Petra Pelikanova and Aneta Stastna
Mentor Sophie Spirkl. The work was focused on rainbow structures and Aharoni's conjecture. (Thus connecting also to Work package 1 of the project.) Petra and Aneta presented parts of their research at Workshop Cycles and Colourings 2019, Slovakia. They gave talks about existence of short rainbow cycles in special classes of graphs.
ITI published a booklet of REU 2019.
The second part of the REU 2019 program consisted of two week stay in Prague. Due to the shorter duration, students didn't start a new research project. Instead, they visited lectures on many topics in discrete mathematics and theoretical computer science. They took part in the CoSP Workshop and School on topology and in Midsummer Combinatorial Workshop.
2020 We started preparation of REU 2020 secondments. Twelve early stage researchers were supposed to go for a secondment at the RU for 2 months and 6 US early stage researchers were planning to come to the Czech Republic for one month secondment. However, all secondments had to be cancelled in the beginning of March 2020 due to the outbreak of COVID pandemy. The REU 2020 training was done online without secondments implemented. This has been very successful due to efforts of students and researchers of the CoSP network. The students worked on four projects as follows (for more details including the students presentations see the web page of CoSP). This activity was also presented during the midterm meeting.
1. Antipodal monochromatic paths in hypercubes
Students: Tomáš Hons, Marian Poljak, Tung Anh Vu (Charles University)
Mentor: Ron Holzman Technion, on secondment of CoSP in Princeton
2. High School Partitions,
Students: Josef Minarik, Michael Skotnica (Charles University)
Mentor: Shay Moran (Princeton)
3. On the Optimal Starting State for a Deterministic Scan in the Three-Color Potts Model
Students: Filip Cermak,, Jakub Xaver Gubas, Lenka Nina Kop-fova, Radek Olsakak (Charles University)
Mentor: Bhargav Narayanan (Rutgers)
4. ∆-coloring in the graph streaming model
Students: Pankaj Kumar Parth Mittal (Charles University)
Mentor: Sepehr Assadi (Rutgers University)