Extremal graph theory group


Past seminars

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