Extremal graph theory group

Programme

MONDAY 23.10.2017 at 9:30 ÚI, room 318: Israel Rocha (Czech Academy of Sciences, ICS) Graphons counterparts of chromatic and clique number

Abstract: Graphons are the main objects in the theory of graph limits introduced in 2006 by Lovász and Szegedy, and recently developed by Borgs, Chayes, Lovasz, Sos and Vesztergombi. Graphons are limits of graph sequences in the cut metric. Graphs are particular types of graphons and the space of graphons is compact with respect the cut metric. This is equivalent to strong forms of Szemeredi’s Regularity Lemma. That implies that the space of graphons is indeed the completion of the space of finite graphs with the cut metric. Naturally, one wants to extend the classical graph parameters to graphons and hope to find continuity. Even though some parameters are continuous, as the density of triangles, some are not, as the matching number. Whenever we do not have continuity, properties do not follow directly from graphs. We introduce graphon counterparts of the chromatic and the clique number, the fractional chromatic number, the b-chromatic number, and the b-fractional clique number. Turns out these parameters are not continuous. In this talk I will explain how this can be done, the properties we can obtain, and the significant differences between the proofs for graphs and for graphons.


Past seminars

MONDAY 25.9.2017 at 10:00 ÚI, room 318: Maryam Sharifzadeh (Warwick) Proof of Komlós's conjecture on Hamiltonian subsets

Abstract: Komlós conjectured in 1981 that among all graphs with minimum degree at least d, the complete graph K_{d+1} minimises the number of Hamiltonian subsets, where a subset of vertices is Hamiltonian if it contains a spanning cycle. We prove this conjecture when d is sufficiently large. In fact we prove a stronger result: for large d, any graph G with average degree at least d contains almost twice as many Hamiltonian subsets as K_{d+1}, unless G is isomorphic to K_{d+1} or a certain other graph which we specify.
This is joint work with Jaehoon Kim, Hong Liu and Katherine Staden.

FRIDAY 8.9.2017 at 10:00 ÚI, room 318: Jonathan Noel (ETH Zurich) The Best Way to Spread a Rumour in a High-Dimensional Grid

Abstract:Bootstrap percolation is a simple process which is used as a model of propagation phenomena in real world networks including, for example, the spread of a rumour in a social network, the dynamics of ferromagnetism and information processing in neural networks. Given a graph G and an integer r, the r-neighbour bootstrap process begins with a set of "infected" vertices and, in each step, a "healthy" vertex becomes infected if it has at least r infected neighbours. A central problem in the area is to determine the size of the smallest initial infection which will spread to every vertex of the graph. In this talk, I will present a new trick for obtaining lower bounds on this quantity by transforming the problem into an infection problem on the edges of the graph and applying some basic facts from linear algebra. In particular, I will outline a proof of a conjecture of Balogh and Bollobás (2006) on the smallest infection which spreads to every vertex of a high-dimensional square lattice and mention some potential applications to analysing the behaviour of a random infection in this setting. This talk is based on joint work with Natasha Morrison.

FRIDAY 18.8.2017 at 10:00 ÚI, room 318: Jan Volec (McGill) On large multipartite subgraphs of H-free graphs

Abstract: A long-standing conjecture of Erdős states that any n-vertex triangle-free graph can be made bipartite by deleting at most n^2/25 edges. In this talk, we study how many edges need to be removed from an H-free graph for a general graph H. By generalizing a result of Sudakov for 4-colorable graphs H, we show that if H is 6-colorable then G can be made bipartite by deleting at most 4n^2/25 edges. Moreover, this amount is needed only in the case G is a complete 5-partite graph with balanced parts. As one of the steps in the proof, we use a strengthening of a result of Füredi on stable version of Turán's theorem.
This is a joint work with P. Hu, B. Lidický, T. Martins-Lopez and S. Norin.

FRIDAY 28.7.2017 at 10:00 ÚI, room 318: Matas Sileikis (Charles University) The open sandwich with a regular random graph

Abstract: The Sandwiching Conjecture of Kim and Vu (2004) which postulates that R(n,d) can be approximated by G(n,p) with p such that expected degree in G(n,p) is asymptotically equal to d (provided d grows faster than log n). We will discuss how much progress has been made towards the conjecture and its natural extensions to random bipartite graphs and random uniform hypergraphs. Joint work with {A. Dudek, A. Frieze, and A. Ruci\'{n}ski} and {T. Klimo\v{s}ov\'a, C. Reiher, and A. Ruci\'nski}

MONDAY 24.7.2017 at 10:00 ÚI, room 318: Gal Kronenberg (Tel Aviv University) 2-universality of random graphs

Abstract: For a family of graphs ℱ, a graph G is ℱ-universal if G contains every graph in ℱ as a (not necessarily induced) subgraph. A natural candidate to serve as universal graph G is the random graph G(n,p). In this case, we want to find an optimal p for which a typical G(n,p) is universal with respect to some given family ℱ. We focus on the family ℋ(n,\Delta), consisting of all graphs on n vertices with maximum degree bounded by \Delta. We prove that there exists a constant C such that for p \geq C \left( \frac{\log n}{n^2} \right)^{\frac{1}{3}} the binomial random graph G(n,p) is typically ℋ(n,2)-universal. This bound is optimal up to the constant factor as illustrated in the seminal work of Johansson, Kahn, and Vu for triangle factors. Our result improves significantly on the previous best bound of p\geq C \left(\frac{\log n}{n} \right)^{1/2} and yielding the first tight result for the ℋ(n,\Delta)-universality problem. In fact, we prove the stronger result. Let ℋ^{\ell}(n,2) be the family of all graphs on n vertices, of maximum degree at most two and of girth at least \ell. Then G(n,p) is typically ℋ^{\ell}(n,2)-universal when p\geq C\left( \frac{\log n}{n^{\ell-1}}\right)^{1/{\ell}}. This result is also optimal up to the constant factor.
Joint work with Asaf Ferber and Kyle Luh.

FRIDAY 23.6.2017 at 10:00 ÚI, room 318: Vojtech Kaluza (Charles University) Mapping n grid points onto a square forces an arbitrarily large Lipschitz constant

Abstract: The starting point of the presented work is a question of U. Feige originating in 1990s and asking the following: Is there a universal constant C>0 such that for every n ∈ ℕ and every set S ⊂ ℤ^2 of n^2 points there exists a C-Lipschitz bijection f: S → {1,2,...,n} × {1,2,...,n}?
We provide a strongly negative answer to this question. Our approach builds upon a work of Burago and Kleiner, and independently McMullen, in which they constructed a separated net S ⊂ ℤ^2 that is not bilipschitz equivalent to ℤ^2.
In this talk I will start with a motivation for the question and present a high-level overview of our proof. In the remainder I will provide more details for the key ingredient: a new bilipschitz decomposition of Lipschitz regular mappings.

FRIDAY 19.5.2017 at 10:00 ÚI, room 318: Tuan Tran (Czech Academy of Sciences) The structure of large sum-free sets of integers

Abstract: A set of integers is called sum-free if it contains no triple of elements x,y,z with x+y=z. We provide a structural characterisation of sum-free subsets of {1,2,…,n} of density at least 2/5−c, where c is an absolute positive constant. As an application, we derive 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. We then use this result to show that the number of subsets of {1,2,…,n} which can be partitioned into two sum-free sets is Θ(2^{4n/5}), confirming a conjecture of Hancock, Staden and Treglown [arXiv:1701.04754]. The presentation will be self-contained.

FRIDAY 5.5.2017 at 10:00 ÚI, room 318: Sebastian Richter (TU Chemnitz) A Chance Constraint Model for Multi-Failure Resilience in Communication Networks

Abstract: For ensuring network survivability in case of single component failures many routing protocols provide a primary and a back up routing path for each origin destination pair. We address the problem of selecting these paths so that in the event of multiple failures, occuring with given probabilities, the total loss in routable demand due to both paths being intersected is small with high probability. We present a chance constraint model and solution approaches based on an explicit integer programming formulation, a robust formulation and a cutting plane approach that yield reasonably good solutions assuming that the failures are caused by at most two elementary events, which may each affect several network components.

THURSDAY 20.4.2017 at 13:30 ÚI, room 318: Igor Carboni Oliveira (Charles University) On monotone circuits with local oracles and clique lower bounds

Abstract: I will describe the computational model of monotone Boolean circuits with local oracles. Understanding the power of these circuits might lead to some interesting consequences in proof complexity. In this talk we will discuss some partial results in this direction, which involve phase transitions and an extension of a classical lower bound in monotone circuit complexity. This is based on joint work with Jan Krajicek.

FRIDAY 7.4.2017 at 10:00 ÚI, room 318: Christos Pelekis (Czech Academy of Sciences ICS) A generalised isodiametric problem

Abstract: According to the isodiametric problem the area of a set whose diameter is 2 cannot be larger than π. What is the maximum area of a planar set, A, with the property that among any three points in A at least two are at distance less than or equal to 2? I will discuss the, devious, motivation behind this question and I will sketch the proofs of certain results and bounds on the maximum area of A.

FRIDAY 24.3.2017 at 10:00 ÚI, room 318: Jan Hladky (TU Dresden) Uniform spanning tree and limits of dense graphs

Abstract: Given any connected graph G, one can consider a uniformly chosen spanning tree of G (uniform spanning tree, or UST for short). There is a beautiful mathematical theory behind UST with applications to probability theory and statistical mechanics. I will explain a limit point of view (in the sense of the theory of so-called graphons) on UST. This is joint work with Asaf Nachmias, Wojciech Samotij and Tuan Tran.

MONDAY 6.3.2017 at 10:00 ÚI, room 318: Israel Rocha (Czech Academy of Sciences ICS) On the structure of spatial networks

Abstract: Spatial networks are graphs with vertices located in a space equipped with a certain metric. In a random spatial network two vertices are connected if their distance is in a given range. The goal is to recover the coordinates of vertices in that space. In a random linear graph vertices are points in a line. We are concerned with large amounts of vertices n, where they are connected with some probability if their distance is at most n/2 . Our problem is to reconstruct its linear embedding by recovering the natural order in which vertices are placed. In this talk we describe a simple algorithm that successfully retrieve the structure of vertices that are randomly distributed. Besides, we show that this order is correct with high probability, and we quantify how many vertices are misplaced. The application of our method to random linear graphs serves as a proof of concept, and it can be used to different graph structures. We discuss different geometries that we are investigating using the same technique.

MONDAY 20.2.2017 at 14:00 ÚI, room 419: Olaf Parczyk (Johann Wolfgang Goethe-Universität) Universality in random and sparse hypergraphs

Abstract: Finding spanning subgraphs is a well studied problem in random graph theory, in the case of hypergraphs less is known and it is natural to study the corresponding spanning problems for random hypergraphs. We study universality, i.e. when does an r-uniform hypergraph contain any hypergraph on n vertices and with maximum vertex degree bounded by ∆. For H(r)(n, p) we show that this holds for p = ω(ln n/n)^{1/∆} a.a.s. Furthermore we derive from explicit constructions of universal graphs due to Alon, Capalbo constructions of universal hypergraphs of size almost matching the lower bound Ω(n^{r−r/∆}). This is joint work with Samuel Hetterich and Yury Person.

seminars in 2016