Extremal graph theory group

The Extremal graph theory group at the Institute of Computer Science of the Czech Academy of Sciences has existed since 2016. Currently, our research is supported by the Czech Science Foundation. We work in extremal graph theory and extremal combinatorics, random graphs, and graph limits.

Our research area

Graphs are one of the simplest mathematical structures. It is this simplicity that allows them to model a broad range of real life situations such as social networks, telecommunication networks or road networks. Some of the most natural questions in the field ask to characterize those graphs which contain a given structure. A classical example is to determine whether a given input graph contains a Hamilton cycle, i.e., a cycle visiting every node exactly once. Often those questions are hard to answer and a very fruitful research direction has been to search for simple sufficient conditions a graph needs to satisfy to guarantee the containment of a sought-after structure. This is the essence of Extremal Graph Theory.

In our group we focus on “density-type” conditions of – typically very large – graphs that force the containment of particular structures. We also study the limit (in the analytic sense) of sequences of graphs of growing sizes. Our methods rely mainly on probabilistic and analytic tools. We also investigate the closely related field of Random Graphs, where we study the characteristics of the probability space of graphs with a given distribution. An easy example is the Erdős-Rényi model, where each edge (connection between two nodes) is inserted with probability ½, i.e., by flipping a coin.

We interact quite a bit with the group Graph limits and inhomogeneous random graphs hosted by the Institute of Mathematics of the Czech Academy of Sciences.

News

June, 2018 The theory of graphons naturally comes with the so-called cut distance. The key result, which makes the theory applicable, is that graphons together with the cut distance topology form a compact space. This was first proven in the seminal paper by Lovasz and Szegedy in 2006. The relation of the cut distance topology and various norms (most notably Lp-norms) has been studied extensively in the past. In the current paper, Israel Rocha and Vaclav Rozhon together with their collaborators Martin Dolezal, Jan Grebik and Jan Hladky thoroughly investigate the relation between the cut distance and the weak-star topology. They prove that a sequence of graphons converges in the cut distance if and only if we have equality of the sets of weak* accumulation points and of weak* limit points of all sequences of graphons that are weakly isomorphic to the original sequence. They further give a short descriptive set theoretic argument that each sequence of graphons contains a subsequence with the property above, thus reproving the Lovasz-Szegedy theorem.

There will be a follow-up paper, where this theory is linked to graph(on) parameters, including graph norms. Further, Jan Hladky, Jon Noel Diana Piguet, Maria Saumell, Israel Rocha are looking at ways how to extend this approach to hypergraphs. So, stay tuned!

May, 2018 Congratulation to Václav Rozhoň for obtaining the first prize in SVOČ (University Students' Competition in research activities in Mathematics and Computer Science) in the section Mathematical Stuctures. The work he presented at the competition was done within the project Extremal graph theory and applications of the Czech Science Foundation and among other includes the following two preprints: arXiv:1804.06791 and arXiv:1802.00679.

April, 2018 Turan-type questions are among the most central in extremal graph theory. In that setting, the task is to find density conditions on the host graph that guarantee the containment of a given graph F. Famous conjectures of Erdos and Sos from 1962 and of Loebl, Komlos and Sos from 1995 (the latter one solved asymptotically in [1, 2, 3, 4]) give such conditions when F is a tree. In two recent papers [Rozhon], [KliPigRoz], Tereza Klimošova, Diana Piguet and Václav Rozhoň investigate refinements of these conjectures and related tree embedding problems.

March, 2018 Congratulation to Václav Rozhoň for obtaining the Excellence Scholarship and Opportunity Award for his master studies at ETH Zurich! We wish him all the best for his studies abroad.

November, 2017 The concept of a uniform spanning tree (UST) of a graph plays a central role in probability theory and mathematical aspects of statistical physics. The main reason for this prominence is the connection to the Schramm-Loewner evolution through loop-erased random walks. The award of the 2006 Fields medal to Wendelin Werner was largely on work on this connection. While the probability community typically investigates USTs of bounded-degree graphs such as large planar grids, Jan Hladky and Tuan Tran, who were both members of ExtrA when the project was initiated, together with Asaf Nachmias of Tel Aviv University looked at the area from the perspective of limits of dense graphs. They describe the local structure of a typical UST of any graph that is close to a given graphon. The paper will appear in Journal of Statistical Physics.

November, 2017 Many of the most important problems in extremal graph theory concern graph packings. In that setting, the task is to find copies of several given graphs into one host graph, so that the copies are edge-disjoint. There has been a flurry of research in the area of graph packing recently (including [1], [2], [3], [4], [5]), mostly driven by old Tree Packing conjectures of Ringel and Gyarfas and Lehel. In their recent manuscript, Diana Piguet, a former ExtrA member Jan Hladky, together with Peter Allen and Julia Bottcher of LSE, extend many of these results. They prove that any family of graphs of bounded degeneracy (with a moderate bound on the maximum degree) packs into a complete graph, subject to the obvious condition on not "overpacking".

July, 2017 Christos Pelekis introduces a Hausdorf dimension point of view on problems in extremal combinatorics.
Sperner's Theorem is a fundamental result about antichains in the hypercube. Version's of Sperner's theorem have been studied for other discrete posets. In their paper, Christos and his coauthors Konrad Engel (Rostock University) and Themis Mitsis (University of Crete) initiate the study of this problem in an analytic setting of the Euclidean hypercube. The difficulty here is that any antichain trivially is a null set in the sense of the Lebesgue measure. However, using the Hausdorf dimension and the Hausdorf measure allows them to "zoom in" even into such null sets. Using a similar point of view they study analytic version of the Erdos-Ko-Rado theorem. They achieve only partial progress on these problems, and as proving the natural conjectures seems to be a challenge.

May, 2017 Tuan Tran proves the Hancock-Staden-Treglown Conjecture.
Much of additive combinatorics is concerned with sum-free set, that is, sets of integers in which the equation x+y=z has no solution. There are only two maximum sum-free sets in {1,2,3,...,n}: all the odd numbers, and all numbers bigger than n/2. Even sum-free sets of smaller densities have a rather rigid structure. A complete description of this structure was known down to density 2/5 due to work of Deshouillers, Freiman, Sos and Temkin from 1999. In his paper, Tuan breaks the 2/5 barrier by describing structure of sum-free sets of density more 2/5-c, for some absolute c. This allows him to obtain a stability version of Hu's Theorem [Proc. Amer. Math. Soc. 80 (1980), 711–712] about partitioning sets of integers into two sum-free subsets, which in turn allows him to prove that the number of subsets of {1,2,3,...,n} which can be partitioned into two sum-free sets is O(2^(4n)/5). This confirms a recent conjecture of Hancock, Staden, and Treglown. This is, as far as we know, the first contribution to additive combinatorics from a researcher at a Czech institution.