The project addresses a set of problems which are at the forefront of contemporary combinatorics. The main objectives include the following: an extension of Szemerédi type theorems for solutions of linear systems to the sparse setting, which is the arithmetic side of recent developments leading to random versions of Ramsey and density results in combinatorics; the extension to minor closed classes of graphs of the celebrated results on enumeration and parameter analysis of planar graphs, which involve the asymptotic probability distribution of significant parameters and may lead, among other results, to the first known subquadratic algorithm for 4-coloring random planar graphs; the study of a random model for tranversal matroids, which would be a novel contribution to random models for complex combinatorial structures; a longstanding conjecture of Stanley on the feasibility of h-vectors in matroids in terms of pure simplicial complexes, for which only few simple cases have been verified; the use of polynomial methods in the study of the so-called MDS conjecture, proved by one of the members of the team in the prime case, and the improvement of constants involved in Kakeya sets and of Bourgain sets in finite geometries, as well as their extensions to higher dimensions; the extension to the geometric setting of classical results in additive combinatorics, which is connected to the existence of a class of MDS codes in the space of bilinear symmetric forms with respect to a particular metric; the asymptotic analysis of pattern densities in permutations, a novel project strongly connected to extremal graph theory and the theory of graph limits. The treatment of these problems involves a development and interleaving of algebraic, geometric and probabilistic methods in combinatorics. Building a solid ground for this set of techniques is one of the side objectives of the proposal.
Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016
Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprograma Estatal de Generación de Conocimiento
Excelencia: Proyectos I+D
Gobierno De España. Ministerio De Economía Y Competitividad, Mineco
Atserias, A.; Kreutzer, S.; Noy, M. International Colloquium on Automata, Languages, and Programming p. 1-14 DOI: 10.4230/LIPIcs.ICALP.2018.116 Presentation's date: 2018-06-09 Presentation of work at congresses