# Extremal combinatorics and asymptotic enumeration

Lead Research Organisation:
University of Warwick

Department Name: Mathematics

### Abstract

Combinatorics is a branch of mathematics studying finite structures. The generality of these questions suggests wide applicability of combinatorics in other areas of pure mathematics (most notably in algebra, number theory, probability, and topology), as well as in real-world applications (discrete optimization, computer science).One of the oldest and most central parts of combinatorics are graph theory and enumerative combinatorics. Graph theory models networks (such as road connections, or internet users), and enumerative combinatorics concerns studying counting questions of various kinds.Extremal graph theory is a broad part of graph theory which investigates interplay between various graph parameters. One of the main tools in Extremal graph theory is the so-called Szemeredi Regularity Lemma. This tool (developed in the 70's) has become one of the corner-stones of modern mathematics. Recently, using the insights gained from the Regularity Lemma, Lovasz and Szegedy initiated study of graph limits.The proposed research project addresses major open questions in extremal graph theory and aims contribute to general theories the Regularity Lemma, graph limits, and by developing novel tools which will be used in enumerative combinatorics.

### Planned Impact

The proposed research project is of theoretical nature. The primary beneficiary will be the European and especially the British community in Discrete Mathematics. It has been pointed out in recent International Review of UK Research in Mathematics (a review undertaken on behalf of the EPSRC and CMS, 2004), that even though there is a significant growth in research on discrete mathematics and its applications to computer science, this area is still under-represented in the UK, both in Mathematics and Computer Science Departments . The research in this proposal can contribute to this undertaking. On the other hand, it should be emphasized that combinatorics, and graph theory in particular are widely applicable in real-world problems, and techniques developed to address theoretical problems have found applications in industry. Let us name applications in design of or operations with networks of various kind (which employ a variety of graph-theoretic results), or applications in coding theory (where the so-called expander graphs are used - objects very close to my main research interests), a field which for example designs optimal ways how to store information on CDs. The knowledge gained during my studies in Computer Science will help me link my results to Theoretical Computer Science, in particular to property testing and analysis of randomized algorithms. Activities at the Centre for Discrete Mathematics and Its Applications at the University of Warwick will allow me to bring my theoretical research in industrial practice; this is one of the main of missions of the Centre. The applications of my mathematical results in Computer Science will be made available in a form accessible to the CS community. In particular, I will publish these results in renowned Computer Science conferences, for example in ACM-SIAM Symposium on Discrete Algorithms (SODA), Annual IEEE Symposium on Foundations of Computer Science (FOCS), or ACM Symposium on Theory of Computing (STOC).

## People |
## ORCID iD |

Jan Hladky (Principal Investigator) |

### Publications

Adamaszek Michal
(2015)

*DENSE FLAG TRIANGULATIONS OF 3-MANIFOLDS VIA EXTREMAL GRAPH THEORY*in TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY
Allen P
(2018)

*A Density Corrádi-Hajnal Theorem*in Canadian Journal of Mathematics
Allen Peter
(2014)

*An extension of Turan's Theorem, uniqueness and stability*in ELECTRONIC JOURNAL OF COMBINATORICS
Böttcher J
(2016)

*An approximate version of the tree packing conjecture*in Israel Journal of Mathematics
Christofides D
(2014)

*Hamilton cycles in dense vertex-transitive graphs*in Journal of Combinatorial Theory, Series B
Csikvári P
(2017)

*Chromatic roots and limits of dense graphs*in Discrete Mathematics
Hladky Jan
(2015)

*POSET LIMITS CAN BE TOTALLY ORDERED*in TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY
Hladký J
(2017)

*The Approximate Loebl--Komlós--Sós Conjecture IV: Embedding Techniques and the Proof of the Main Result*in SIAM Journal on Discrete Mathematics
Hladký J
(2017)

*The Approximate Loebl--Komlós--Sós Conjecture II: The Rough Structure of LKS Graphs*in SIAM Journal on Discrete Mathematics
Hladký J
(2017)

*The Approximate Loebl--Komlós--Sós Conjecture III: The Finer Structure of LKS Graphs*in SIAM Journal on Discrete MathematicsDescription | The main findings were of theoretical nature and fit well within the current trends in extremal graph theory and the recently developed theory of graph limits. The most important work involved the Loebl-Komlos-Sos conjecture, an open problem in extremal graph theory from the 1990's, where we achieved an asymptotic resolution (in positive), and a solution of an old question of Lovasz (for the class of dense graphs) about hamiltonicity of dense graph. |

Exploitation Route | The publications and the methods introduced in the said project have generated (and will further generate) further progress in extremal graph theory and graph limits. For example, results in our paper with Mathe, Patel and Pikhurko on limits of partial orders have been used in the context of random discrete structures by other researchers. Our novel application (with Adamaszek) of extremal graph theory in geometry has led (after the end of the project) on further project, and has generated big interest in the geometry community. |

Sectors | Electronics,Other |