October, 2023 Jan Hladký and Gopal Viswanathan just published their new preprint Random minimum spanning tree and dense graph limits. The problem of a minimum spanning tree (in a graph whose edges are weighted) has a rich history with a substantial Czech trace. Indeed, the first fast algorithm for this problem was developed by Otakar Borůvka in 1926 for the purpose of designing an efficient electric distribution network in Western Moravia. In 1985, Alan Frieze investigated the value of a random minimum spanning tree in a large complete graph whose edge weights are taken at random from the unit interval. In particular, Frieze proved that the total weight of a minimum spanning tree then converges to Apéry's constant. The current preprint extends Frieze's result in a maximal possible way within the framework of dense graph limits.
September, 2023 Best paper awards of the Institute of Computer Science were awarded at the annual meeting of the institute in Jizerka. Five papers in three categories (Best paper, Best paper by junior authors, Best paper with direct societal potential) were awarded, including the paper Minimum degrees for powers of paths and cycles by Eng Keat Hng (Best paper by a junior author), and Cut distance identifying graphon parameters over weak* limits by Martin Doležal, Jan Grebík, Jan Hladký, Israel Rocha, Václav Rozhoň (Best paper). Congratulations!
June, 2023 Juškevičius and Kurauskas asymptotically solved a conjecture of Leader and Radcliffe (1994) and a question of Lee Jones (1978) in finite dimensional vector spaces. These conjectures are concerned with the classical problem of establishing best possible anticoncentration bounds for sums of random vectors. The mentioned new work is the first progress towards the two problems and essentially settles both of them in R^d endowed with the l_2 norm (other norms are dealt with as well), which is the unresolved case of most interest and in some sense the hardest one. The main new tool used for the first time in this context is the Strong Perfect Graph Theorem which the authors believe to be of independent interest and useful in other related problems. See preprint.
June, 2023 Garbe, Hladký, Šileikis and Skerman recently introduced a broad class of random graph processes called flip processes and showed that the highly concentrated typical evolution of flip processes is neatly captured through the lens of dense graph limits. In a recent preprint, Eng Keat Hng fully characterizes when flip processes under seemingly different rules have the same typical evolution from the perspective of dense graph limits.
May, 2023 The field of random graphs started by two independent papers by Gilbert and by Erdos and Renyi in 1959. Both these papers studied connectivity of random graphs. Phrased in a more modern language, they established that the connectivity threshold of G(n,p) is p=ln n/n. A new preprint by Jan Hladký and Gopal Viswanathan studies an analogous problem in the setting of inhomogeneous random graphs.
October, 2022 Jan Hladký and Eng Keat Hng just published their new preprint Approximating fractionally isomorphic graphons. The concept of fractional isomorphism of finite graphs dates back to 1986 and has been used in a variety of ways including practical algorithms for graph isomorphism testing. Grebík and Rocha [Combinatorica 2022] worked out an analogous theory for graphons. The published preprint answers in positive the main question from the paper of Grebík and Rocha, namely that two fractionally isomorphic graphons can be approximated by sequences of fractionally isomorphic graphs.
August, 2022 The graph removal lemma from 1978 is one of the most applicable results in graph theory. Since then removal lemmas for many other discrete structures have been obtained. In a recent preprint, Jan Hladky together with his collaborators Frederik Garbe, Gabor Kun, and Kristyna Pekarkova obtained a removal lemma for permutations. As a key tool to obtain this result they describe the structure of permutons avoiding a given subpermutations. Permutons are central objects coming from the theory of limits of discrete structures.
We have several part-time position for undergraduate students affected by serious circumstances such as a military conflict. More information can be found here.
June, 2022 Pedro Araújo, Jan Hladký, Keat Hng and Matas Šileikis just published their new preprint Prominent examples of flip processes. This paper complements abstract foundations of the theory of flip processes laid down earlier by studying several interesting specific flip processes, which are general models of stochastic evolution on finite graphs.
February, 2022 Random graph processes are stochastic processes which model evolution of networks over time. Dozens of variants of random graph processes have been studied since the 1960s. In their recent paper, Jan Hladký and Matas Šileikis, together with Frederik Garbe (Masaryk University) and Fiona Skerman (Uppsala University) have introduced a framework of what they call flip processes. This framework is quite general and accommodates many previously studied models including the Erdős-Rényi random graph process and the triangle removal process. One of their main results is a description of a typical evolution of a flip process started from any given large graph using graph limits. This graph limit perspective allows them to study previously unnoticed phenomena.
January, 2022 In 1994 Leader and Radcliffe studied anticoncentration problems for sums of random variables using tools from Extremal Combinatorics. One of their questions was to extend their main result, which holds when the maximum probability of the summands in a fixed length interval is an inverse of an integer. They asked for the best possible such inequality for arbitrary values of concentration. This question was answered in a recent paper by Tomas Juškevičius.
September, 2021 Congratulations to Jan Hladký for receiving the Neuron prize for for Young Talented Scientists!
June, 2021 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 in a host graph, so that the copies are edge-disjoint. The area of graph packings has seen a boom in recent years, mostly due to advanced probabilistic approaches. The most striking success in the area was Keevash's construction of designs (still as a preprint).
A conjecture of Gyárfás from 1978 says that certain very general families of graphs can be packed in a complete graph. In a current 150-page long preprint, Jan Hladky, Diana Piguet, together with their collaborators Peter Allen, Dennis Clemens, Julia Böttcher, and Anusch Taraz prove a generalization of this conjecture under an additional mild bound on the maximum degrees of these trees.
November, 2020 Congratulations to Jan Hladký for obtaining the EXPRO grant Limity grafů a související obory from the Czech Science Foundation!
November, 2019 Congratulations to Matas Šileikis for obtaining the junior grant Random Discrete Structures from the Czech Science Foundation!
November, 2019 Extension counts in a graph is a generalization of vertex degrees, when instead of edges we are counting copies of some other graph, say, triangles containing a given "root" vertex or the number of paths of length five connecting two given "root" vertices. In 1989 Joel Spencer gave a sufficient condition when extension counts are asymptotically equal (for vertex degrees this is true when np grows faster than log n). In arXiv:1911.03012 Šileikis and Warnke refined Spencer's condition and showed it is necessary for a natural class of graphs (including the examples above), but concluded that the general problem remains open.
January, 2019 In their recent paper, Šileikis and Warnke study the probability that the Erdős-Rényi random graph G(n,p) has more k-stars (for fixed k) than expected. Qualitatively the result suggests that the unusually many stars apear due to one of the three reasons: (i) there are many disjoint stars; (ii) the graph G(n,p) 'looks like' G(n,r), with r > p; (iii) there are a few vertices of very large degree which create the 'excess of stars'. In particular the result determines the asymptotic order of the large deviation rate function, contributing to the emerging theory of non-linear large deviations. arXiv:1901.10637
November, 2018 Congratulation to Jan Grebik for obtaining the Josef Hlavka Prize!
September, 2018 The 'Infamous upper tail' problem (named by Janson and Rucinski) is a resilient problem in random graph theory. It asks for a sharp bound for the probability that Erdős-Rényi random graph G(n,p) has twice as many copies of a given graph H than expected. In 2011 DeMarco and Kahn conjectured the correct order (as n grows) of the logarithm of the probability in question. Their guess was confirmed in a series of papers assuming p tends to zero not too fast. Šileikis and Warnke described an infinite class of counterexamples to the DeMarco-Kahn conjecture in the very sparse setting (when copies of H are few). arXiv:1809.09595
September, 2018 There are numerous models of random rooted trees and many of them can be represented as the genealogical tree of the critical Galton-Watson process, conditioned to 'die out' after n individuals come to life. Ralaivaosaona, Šileikis and Wagner studied distribution of several parameters of such random trees (e.g, number of independent sets, or number of matchings) and showed that they are log-normal (which curiously implies they are concentrated below the expected value). arXiv:1810.00467
September, 2018 The concept of cut distance identifying graphon parameters is introduced by Martin Doležal, Jan Grebík, Jan Hladký, Israel Rocha, Václav Rozhoň. That is a follow up of the recent paper, where the cut distance topology on the space of graphons is approached via the weak* topology. The cut distance is central in the study of graphons, and cut distance identifying parameters have the hability to pinpoint a cut distance accumulation graphon in the set of weak* accumulation points. As an outcome of the theory they prove that a connected graph is step Sidorenko if and only if it is weakly norming, answering a question of Král', Martins, Pach and Wrochna [arXiv:1802.05007].
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.
Randomly generated discrete structures like graphs, permutations, trees, and hypergraphs have become ubiquitous in applied sciences as abstract models for complex objects: networks, population dynamics or physical systems. Focusing on the theoretical aspect of such models, we study random discrete structures via probabilistic concepts: laws of large numbers, asymptotic distributions, phase transitions, large deviations, and concentration inequalities. We address questions on random discrete structures by exploring techniques from various areas of mathematics, including probability, information theory, statistical physics, analysis and linear algebra.
Graphs are among 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.
Graph limits are a relatively new field inspired by developements of the former two. They offer a unified analytic framework to understand large graphs. Since the first paper about two decades ago, graph limits were instrumental in progress on some of the most famous problems in discrete mathematics, including the question of diagonal Ramsey numbers, Sidorenko's conjecture, or the replica symmetry of large deviations in random graphs.
Combinatorial and computational geometry is a subarea of the more general Discrete Mathematics and Theoretical Computer Science. Computational geometry is mainly concerned with the study of algorithmic problems that have a strong geometric component, while in Combinatorial geometry the emphasis is put on the combinatorial properties of geometric structures. While Combinatorial and computational geometry only emerged in the second half of the 20th century, it has roots in classic geometry, one of the oldest areas of Mathematics.
Currently, in our group we focus on two popular topics in Combinatorial and computational geometry: visibility in terrains and cluster Voronoi diagrams.
