Extremal graph theory group

Current members of the group

Jan Grebík

I am a PhD student at the Charles University, my supervisor is David Chodounsky. My interests lie in descriptive set theory and its application to other parts of mathematics such as borel equivalence relations, ergodic theory, borel combinatorics, forcing, graphons etc.

Diana Piguet

Diana's research interests lie in extremal graph theory, Ramsey theory, probabilistic method, and limits of graphs. In particular together with Komlós, Hladký, Simonovits, Stein, and Szemerédi, she used a generalisation of the regularity lemma to sparse graphs to assymptotically solve a cojecture of Loebl, Komlós and Sós on trees. Together with Böttcher, Hladký and Taraz, she used the Rödl nibble method to make significant progress on a conjecture of Gyárfás about packing trees.

Israel Rocha

My research is in the area of Spectral Graph Theory. I am interested in understanding how eigenvectors portray the structure of networks, such as community formation, connectivity, partitioning, etc. Besides, I conduct research on extremal problems in Spectral Graph Theory, such as characterizing graphs that achieve extremal values of algebraic connectivity, energy, etc. Spectral techniques have been used for decades to successfully reveal the underlying properties of graphs. From graphs with a specific design to random graphs, and from finite to infinite graphs, I have been applying semidefinite optimization, probability theory, and matrix theory to expose such properties.

Maria Saumell

Until recently my main research areas have been Computational Geometry and Graph Drawing, with an emphasis on proximity graphs and Voronoi diagrams, visibility and interval graphs. Recently I have also become interested in Extremal Graph Theory and I have started to work on problems involving graph tilings. In this kind of problems, we aim to provide necessary conditions guaranteeing that some host graph G contains a fixed number of copies of another graph H.

Matas Šileikis

My main interests are random discrete structures and tail probability inequalities. I have contributed to progress on the Kim-Vu Sandwich Conjecture (and its extension to random hypergraphs) and the Upper Tail Problem for subgraph counts in the random graph G(n,p). Moreover, I have applied results of extremal hypergraph theory to obtain some optimal tail inequalities for sums of independent random variables.

Past Members

Jan Hladký
(Currently at Institute of Mathematics of CAS)

Jan obtained his PhD from the University of Warwick in 2011 under the supervision of Artur Czumaj and from Charles University in 2013 under the supervision of Dan Kral. After research fellowships at the University of Warwick and the Institute of Mathematics of the Czech Academy of Sciences, Jan will join the group in September 2016. Jan's research focuses on extremal graph theory, random discrete structures, and graph limits. His most important projects include progress on the Loebl-Komlos-Sos Conjecture, Caccetta-Haggkvist Conjecture, and the Tree Packing Conjecture.

Tereza Klimošová
(Currently at KAM, MFF UK)

Tereza is interested in a variety of problems in combinatorics. During her PhD she focused on using analytical tools for studying large discrete structures and algorithms for large inputs. This area is closely related to extremal combinatorics, using many tools from it, most notably Szemeredi regularity lemma. She has also been working on problems related to minors and immersions of graphs.

Christos Pelekis
(Currently at Institute of Mathematics of CAS)

I work in combinatorics, probability and game theory. An example of a question I have been considering, which arose in the analysis of a particular allocation game, is the following: Suppose that you want to poison your mother-in-law. You know she is going to eat k biscuits from a tray that contains n biscuits in total, but you do not know which biscuit she is going to choose. Each biscuit has the same probability of being chosen. You possess h>1 grams of arsenic whose lethal dose is one gramme. How should you distribute the poison in order to maximize the probability that your mother-in-law gets the lethal dose? My research interests include probabilistic and geometric analogues of this question.

Václav Rozhoň
(currently at ETH Zurich)

I am an undergraduate student interested in extremal graph theory and graph limits. My current research includes using Szemeredi regularity lemma as a tool for proving certain asymptotic extremal results regarding embedding trees in a host graph. Recently I got very interested in theory of graphons.

Tuan Tran
(currently at ETH Zurich)

My research interests lie in combinatorics, particularly in probabilistic combinatorics, extremal combinatorics and positional games, as well as its applications to other areas of mathematics.
A typical question in extremal combinatorics asks how large a structure can be without containing a given substructure. For instance, a classic theorem in extremal set theory determines the size of the largest families of k-sets of {1,2,...,n} with the property that any two k-sets has non-empty intersection. I am particularly interested in applications of algebraic, analytic and probabilistic methods to this type of problems.