#	Pagina
attuale pagina	/open-h2020/projects/202542/results.html

Report

Teaser, summary, work performed and final results

Periodic Reporting for period 3 - RanDM (Randomness and pseudorandomness in discrete mathematics)

Teaser

Summary

The project addresses questions related to randomness and pseudorandomness in discrete mathematics, with a particular eye to applying these concepts to solve longstanding open problems. The probabilistic method plays an important role in combinatorics, often remaining the only method for producing objects with certain required properties. On the other hand, pseudorandom objects, that is, objects which are explicit but random-like, have played an ever-increasing role in recent advances, not least the PI\'s work on diagonal Ramsey numbers and Keevash\'s solution to the classical design problem. It is expected that by developing our understanding of random and pseudorandom objects, we will be able to make still further progress on problems in the areas of Ramsey theory, extremal graph theory, additive combinatorics and combinatorial geometry.

Work performed

To date, the project has led to substantial progress on questions in Ramsey theory, extremal graph theory, additive combinatorics, pseudorandomness and the study of high-dimensional expanders. The main results are summarised below:

- A question of Lovasz and Hatami asks for a characterisation of those graphs which can be used to define norms. Together with the PDRA Joonkyung Lee, the PI uncovered a connection between this question and the theory of finite reflection groups, allowing them to find a wide family of norming graphs. These results also have applications to the study of quasirandomness in hypergraphs and to a famous conjecture of Sidorenko and Erdos-Simonovits. The paper \'Finite reflection groups and graph norms\' has now appeared in Advances in Mathematics.

- As a further application of the results on norming graphs, Conlon and Lee made further significant progress on Sidorenko\'s conjecture, which says that quasirandom graphs minimise the number of copies of any fixed bipartite graph H, where the minimum is taken over all graphs with a given order and density. The main result of this paper states that for any fixed H, there is an appropriate blow-up of H such that the conjecture holds for this blow-up. The resulting paper, \'Sidorenko\'s conjecture for blow-ups\', has been submitted for publication.

- Inspired by the connection between C_6-free graphs and triangle-free pseudorandom graphs, the PDRA Lee and the PI explored the extremal number of the subdivision H_t of the complete graph K_t. Their main result, improving a result of Furedi and answering a problem of Erdos, says that any graph with n vertices and more than C n^{3/2 - c} edges contains a copy of H_t. This paper \'On the extremal number of subdivisions\' also raised a large number of interesting open questions that have attracted strong attention.Â

- Also on extremal numbers is \'Rational exponents in extremal graph theory\', written by Boris Bukh and the PI. Here, they build on Bukh\'s random algebraic method to prove a variant of an old conjecture of Erdos and Simonovits, namely, that for any rational number 1 < r < 2, there exists a family of graphs H_r such that the largest graph on n vertices containing no graph from H_r has between c n^r and C n^r edges. This paper has appeared in the Journal of the European Mathematical Society.

- These papers were followed by another paper with PDRA Lee and Oliver Janzer, \'More on the extremal number of subdivisions\'. Here we pursued several themes, all related to the so-called degeneracy problem in extremal graph theory - it is often easy to find homomorphic copies of a graph H, but finding a non-degenerate copy can pose severe difficulties. Our work finds means of circumventing this difficulty, with several applications to problems in the literature.

- In recent years, much energy has gone into the study of high-dimensional, or hypergraph, expanders, with much of the work centring around the study of Ramanujan complexes, remarkable algebraically-defined objects. In \'Hypergraph expanders from Cayley graphs\', the PI gives a considerably simpler construction of 3-uniform hypergraphs sharing many of the features of Ramanujan complexes. This paper was later extended to all uniformities by the PI, together with Jonathan Tidor and Yufei Zhao, using additional ideas from coding theory.

- Answering a question of Erdos, Graham, Montgomery, Rothschild, Spencer, and Straus, the PI and Jacob Fox showed that there is a red/blue-colouring of the points of n-dimensional space containing no pair of red points at distance 1 and no 2^{cn} blue points all in a line. This is best possible up to the value of the constant c. The resulting paper, \'Lines in Euclidean Ramsey theory\', is due to appear in Discrete and Computational Geometry.

- In \'The Ramsey number of books\', the PI solves old problems of Thomason and of Erdos, Faudree, Rousseau and Schelp about the Ramsey number of books, showing that a simple lower bound coming from th

Final results

Arguably the most significant progress in the project has been the work of PDRA Annika Heckel showing the non-concentration of the chromatic number of random graphs. However, there have also been substantial gains in our understanding of extremal numbers for bipartite graphs, significant progress towards classifying graph norms, itself leading to surprising results on the celebrated Sidorenko\'s conjecture, and solutions to a number of longstanding problems in Ramsey theory, some originally stated by Erdos and his collaborators.