seminars in 2016

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 (Warwick University) 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 (ETH Zurich) 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.