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.

News

current If you are a hard-working student enrolled at a Czech university (or about to enroll) interested in collaboration (possibly leading to a thesis), check here.

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.