Extremal graph theory group

Programme

FRIDAY 30.6.2017 at 10:00 ÚI, room 318: Matas Sileikis (Charles University) TBA

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.


Past seminars

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.

MONDAY 7.11.2016 at 14:00 ÚI, room 419: Shagnik Das (Freie Universität Berlin) Erdős-Ko-Rado: removal, stability and sparseness

Abstract: The study of intersecting families is central to extremal set theory, starting with the celebrated Erdős-Ko-Rado theorem of 1961. This theorem asserts that when n ≥ 2k, the largest k-uniform intersecting set family over [n] has size \(\binom{n-1}{k-1}\), and that when n > 2k, the only such families are trivial. Since its publication, the theorem has inspired a great deal of research, as it can be extended in several ways. One particularly important extension is that of stability: to show that large intersecting families must be close to trivial in their structure. In this talk we will present a removal lemma for intersecting families, which extends the stability results beyond the intersecting setting. In particular, we show that large families with relatively few disjoint pairs must be close to trivial in structure. We shall then demonstrate an application of this result, answering a question of Bollobás, Narayanan and Raigorodskii concerning a sparse random version of the Erdős-Ko-Rado theorem. This is joint work with Tuan Tran.

MONDAY 10.10.2016 at 14:00 ÚI, room 318: Daniel Kral (University of Warwick) Large networks, graph limits and their uniqueness

Abstract: Theory of graph limits aims to provide analytic models representing large networks/graphs. Such models have found applications in various areas of computer science, mathematics and network science. In this talk, we will focus on large dense graphs and their limits. Motivated by problems from extremal graph theory, Lovasz and Szegedy initiated a systematic study of graph limits that are uniquely determined by finitely many density constraints, so-called finitely forcible graphons, and conjectured that all such graphons must have a simple structure. On the contrary, we will show that finitely forcible graphons can contain any computable graphon as a subgraphon. Our result provides a unified framework for constructing complex finitely forcible graphons, which includes many earlier ad hoc constructions of finitely forcible graphons.
The talk is based on joint work with Jacob Cooper and Taisa Martins. The presentation will be self-contained and no previous knowledge of graph limits will be assumed.

MONDAY 19.9.2016 at 14:00 ÚI, room 419: Lluis Vena (Charles University) A removal lemma for linear systems in compact abelian groups

Abstract: The removal lemma for graphs, introduced in 1976 by Ruzsa and Szemeredi, claims that a graph with few triangles can be made triangles-free by removing a few of its edges. One of its main applications is a simple proof of Roth's theorem on the existence of 3-term arithmetic progressions in dense sets of the integers.
In this work we consider analogues of this result for integer linear systems in compact abelian groups, where if a set has a small measure of solutions to a given integer linear system, then it can be made solution-free by removing a set of small measure. This shows that the supersaturation phenomena exhibit by integer linear systems over finite abelian groups (Kral, Serra and the third author), extends to the compact abelian setting. This generalizes a previous result for the circle from Candela and Sisask. This is a joint work with Balazs Szegedy and Pablo Candela.

MONDAY 15.8.2016 at 10:00 ÚI, room 318: Peter Allen (LSE) Regularity inheritance in hypergraphs

Abstract: I will introduce hypergraph regularity from the basics, and explain why the statement has to be as it is, and why this makes it hard to use. I will then outline two tools which make it easier to use, and sketch the proof of one.

MONDAY 8.8.2016 at 10:00 ÚI, room 318: Yaqiao Li (McGill University) A characterization of functions with vanishing averages over products of disjoint sets

Abstract: Given α1, ..., αm ∈ (0,1), we characterize all integrable functions f: [0,1]m ⟶ ℂ satisfying ∫A1 × ... × Am f = 0 for any collection of disjoint measurable sets A1, ...., Am ⊆ [0,1] of respective measures α1, ...., αm. We use this characterization to settle some of the conjectures in [S. Janson and V. Sos, More on quasi-random graphs, subgraph counts and graph limits] about the relation between subgraph counts and quasi-randomness of graph sequences. This is a joint work with Hamed Hatami (McGill) and Pooya Hatami (IAS).

MONDAY 18.7.2016 at 14:00 ÚI, room 318: Jan Hladky (the Czech Academy of Sciences, IM) Graceful tree conjecture

Abstract: The Graceful Tree Conjecture of Rosa from 1967 asserts that the vertices of each tree T of order n can be injectively labelled by using the numbers {1,2,...,n} in such a way that the absolute differences induced on the edges are pairwise distinct. We prove a relaxation of the conjecture in which slightly more labels are used, say {1,2,...,(1+γ)n}, where γ>0 is arbitrary, and the maximum degree of T is bounded by n/log (n). The proof proceeds by showing that a certain very natural randomized algorithm produces a desired labelling with high probability. Joint work with Anna Adamaszek, Peter Allen, and Codrut Grosu. The talk will be self-contained.

MONDAY 27.6.2016 at 14:00 ÚI, room 318: Ágnes Backhausz (Eotvos Lorand University and Renyi Institute) On the graph limit approach to eigenvectors of random regular graphs

Abstract: The goal of the talk is to show how the graph limit approach can be used to understand spectral properties of large random regular graphs. A large random regular graph has large girth with high probability, and locally looks like a tree. To put it in another way, a sequence of random regular graphs converges to the infinite regular tree in the Benjamini--Schramm (local) sense of graph convergence. In our work, we consider invariant random processes on the infinite tree that satisfy the eigenvalue equation. As a consequence of the results in the infinite setting, we could prove that delocalized eigenvectors of finite random regular graphs are close to Gaussian. Joint work with Balázs Szegedy.

MONDAY 13.6.2016 at 14:00 ÚI, room 318: Tuan Tran (Czech Academy of Sciences ICS) Erdos-Rothschild problem for intersecting families

Abstract: Given some class of structures, and some monotone decreasing property P, the typical extremal problem asks for the largest structure with property P. The Erdos-Rothschild problem is an extension of this extremal problem, asking for the structure with the maximum number of r-colourings where every colour class has property P. While it first was asked in the context of graph theory, there has been much recent investigation of the Erdos-Rothschild problem for intersecting families of various kinds. In this talk we will see a unified proof for the three-colours case that covers the previous results and introduces some new ones. This method also provides far better (and sometimes optimal) bounds on the parameters of the families in question. Time permitting, we shall briefly discuss the multi-coloured setting as well. This is joint work Shagnik Das and Dennis Clemens.

MONDAY 25.4.2016 at 14:00 (ÚI, room 318): Hong Liu (University of Warwick) Some enumeration results in extremal combinatorics

Abstract: In this talk, I will discuss some recent developments on some enumeration problems in extremal combinatorics. Among others, I will discuss two problems asked by Cameron and Erdős: one on counting the number of maximal sum-free sets of integers, and the other one on counting the number of sets without any arithmetic progressions of fixed length.