Talks take place at Arnimallee 3, 14195 Berlin, Room A3/SR005, unless stated otherwise.
Date | Speaker | Title |
---|---|---|
23.07.2015 11:15 |
Dániel Korándi ETH Zürich |
A random triadic process |
15.07.2015 16:15 |
Clément Requilé FU Berlin |
Triangles in random cubic planar graphs |
08.07.2015 16:15 |
Jozsef Balogh University of Illinois at Urbana-Champaign |
On the applications of counting independent sets in hypergraphs |
02.07.2015 10:15 |
Boris Bukh Carnegie Mellon University |
Common subsequences in words and permutations |
25.06.2015 10:15 |
Christopher Kusch FU Berlin |
Strong Ramsey Games: Drawing on an infinite board |
17.06.2015 16:15 |
Florian Pfender UC Denver |
Semidefinite programming in extremal graph theory and Ramsey theory |
04.06.2015 10:15 |
Benny Sudakov ETH Zürich |
Grid Ramsey problem and related questions |
03.06.2015 16:15 |
Ana Zumalacárregui University of New South Wales |
Additive bases for intervals |
27.05.2015 16:15 |
Sylwia Antoniuk Adam Mickiewicz University |
On the connectivity Waiter-Client game |
21.05.2015 10:15 |
Shagnik Das FU Berlin |
Comparable pairs in set families |
30.04.2015 10:15 A3 SR 211 |
Open Mic | Problem Session |
09.04.2015 11:15 A3 SR210 |
Ewan Davies London School of Economics |
Counting in hypergraphs via regularity inheritance |
23.03.2015 10:15 A3 SR119 |
Imre Leader University of Cambridge |
Tiling with Arbitrary Tiles |
19.03.2015 10:15 A3 SR119 |
Alexey Pokrovskiy FU Berlin |
Rainbow matchings and rainbow connectedness |
12.03.2015 10:15 A3 SR119 |
Lluis Vena Charles University Prague |
Deducing an arithmetic removal lemma from the removal lemma for hypergraphs and its applications |
26.02.2015 10:15 A3 SR119 |
Alexey Pokrovskiy FU Berlin |
Open problems in Ramsey Theory (pt 2) |
19.02.2015 10:15 A3 SR119 |
Tibor Szabó and Alexey Pokrovskiy FU Berlin |
Open problems in Ramsey Theory |
12.02.2015 10:15 A3 SR119 |
Christopher Pütz FU Berlin |
An exposition of the Green-Tao theorem |
22.01.2015 11:00 ZIB |
Dennis Clemens FU Berlin |
Reiher's Clique Density Theorem |
21.01.2015 16:15 A3 SR210 |
Codruț Grosu FU Berlin |
On transversals avoiding complete subgraphs |
15.01.2015 10:15 A6 SR017 |
Juanjo Rué FU Berlin |
Arithmetic removal lemmas and independent sets in hypergraphs |
08.01.2015 10:15 A6 SR017 |
Christopher Kusch FU Berlin |
Random Algebraic Constructions |
18.12.2014 10:15 A6 SR017 |
Dimitrios Thilikos University of Athens |
Erdős–Pósa property for minor and topological minor models |
10.12.2014 16:15 A3 SR210 |
Piotr Micek Jagiellonian University TU Berlin |
Posets and minors |
04.12.2014 10:15 A6 SR017 |
Cathryn Supko FU Berlin |
TBA |
27.11.2014 10:15 A6 SR017 |
Clément Requilé FU Berlin |
A parameterized algorithm for the diameter improvement problem for plane graphs |
20.11.2014 10:15 A6 SR017 |
Tuan Tran FU Berlin |
A removal lemma for Kneser graphs |
12.11.2014 16:15 |
Tibor Szabó FU Berlin |
On the minimum degree of minimal Ramsey graphs |
05.11.2014 14:15 A7 SR140 |
Olaf Parczyk FU Berlin |
Relative entropy and Sidorenko’s conjecture |
Abstracts:
05.11.2014 |
---|
Olaf Parczyk (FU Berlin) |
Relative entropy and Sidorenko’s conjecture |
Abstract: Following the paper by Balázs Szegedy we introduce the family of graphs H that admit a probability distribution of copies in an arbitrary graph G obtained by iterating conditionally independent couplings starting from the uniform distribution on edges. We investigate the famous conjecture by Erdős-Simonovits and Sidorenko inside this family. As a tool we use an inclusion exclusion type formula for relative entropy. The method gives a unified treatment for most known cases of the conjecture and it implies various new results as well. |
12.11.2014 |
---|
Tibor Szabó (FU Berlin) |
On the minimum degree of minimal Ramsey graphs |
Abstract: A graph G is r-Ramsey for H if for any r-coloring of its edges there is a monochromatic copy of H. G is called r-Ramsey minimal for H if it is r-Ramsey for H, but no subgraph of it is r-Ramsey for H. We study the smallest minimum degree an r-Ramsey-minimal graph for the clique K_{k} can have. This function was introduced and determined for two colors by Burr, Erdős and Lovász in 1975. We extend their theorem for r colors and connect the function to the so-called Erdős-Rogers function, which was introduced and studied more than a decade earlier. This represents joint work with Jacob Fox, Andrey Grinshpun, Anita Liebenau, and Yury Person. |
20.11.2014 |
---|
Tuan Tran (FU Berlin) |
A removal lemma for Kneser graphs |
Abstract: Given natural numbers n, k with 2 ≤ k < n/2. We write ([n] choose k) for the family of all subsets of size k of [n]. The Kneser graph K(n, k) is the graph whose vertex set is ([n] choose k ) where two sets A, B ∈ ([n] choose k ) are adjacent if and only if A ∩ B = ∅. The celebrated theorem of Erdős-Ko-Rado from 1961 says that every independent set in K(n, k) has size at most (n - 1 choose k - 1), and the only independent sets of this size are stars. We prove a removal lemma for these graphs. Loosely speaking, it tells us that every subfamily of ([n] choose k) of size roughly (n - 1 choose k - 1) with few disjoint pairs must be very close to a star. Armed with this lemma, we establish a sparse version of the Erdős-Ko-Rado theorem. This settles a question of Bollobás, Narayanan and Raigorodskii (2014). The talk represents joint work with Shagnik Das. |
27.11.2014 |
---|
Clément Requilé (FU Berlin) |
A parameterized algorithm for the diameter improvement problem for plane graphs |
Abstract: A problem mentioned by Chung in 1987: given a plane graph and an integer d, is it possible to reduce the diameter of the graph to at most d by adding non-edges, while conserving planarity? Fellows and Dejter have shown in an unpublished paper in 1993 that the oriented case was NP-Complete and that both the oriented and undirected cases were FPT (FIxed Parameter Tractable). But their proof is mostly based on the Robertson and Seymour theorem and is therefore non-constructive as of yet. This type of result is in essence theoretical, but it gives us good hopes of finding efficient FPT algorithms. We will focus on a natural variant of this problem in the undirected case, where the number of edges that can be added per face is upper-bounded by an integer k. We will then give an FPT algorithm (parameterized by d and k) for this variant, build on dynamic programming. This talk is based on joint work with Dimitrios Thilikos (LIRMM, France/University of Athens). |
04.12.2014 |
---|
Cathryn Supko (FU Berlin) |
TBA |
Abstract: Abstract: TBA |
10.12.2014 |
---|
Piotr Micek (Jagiellonian University, TU Berlin) |
Posets and minors |
Abstract: Posets of height 2 may have arbitrarily large dimension. But posets of bounded height with somehow restricted cover graphs do have bounded dimension. (If you are about to give up this talk. Let me just mention that I will try to make it a kind of introductory into posets dimension theory) In 1977, Trotter and Moore proved that a poset has dimension at most 3 whenever its cover graph is a forest. In a series of papers it is proved that when a poset has bounded height and its cover graph is planar (2014), or has bounded treewidth (2015+), or most generally excludes a fixed graph as a topological minor (2015+), then the poset has bounded dimension. We conjecture that a restriction on bounded height, forbidding a long chain in a poset, may be relaxed to exclusion of two long incomparable chains. We support our feeling providing three theorems: (1) Every poset without two long incomparable chains whose cover graph has bounded pathwidth has bounded dimension; (2) For every poset without two long incomparable chains whose cover graph excludes a fixed graph as a topological minor, all standard examples in the poset are small; (3) Every interval order, i.e. (2+2)-free poset, whose cover graph excludes a fixed graph as a topological minor has bounded dimension. |
18.12.2014 |
---|
Dimitrios Thilikos (University of Athens) |
Erdős–Pósa property for minor and topological minor models |
Abstract: A class of graphs C satisfies the Erdős–Pósa property if there exists a function f such that, for every integer k and every graph G, either G contains k vertex-disjoint subgraphs each isomorphic to a graph in C, or there is a subset S of V(G) of at most f(k) vertices such that G ∖ S has no subgraph in C. Erdős and Pósa (1965) proved that the set of all cycles satisfies this property for all graphs with f(k) = O(k log k). Given a connected graph H, let M(H) be the class of graphs that contain H as a minor. Robertson and Seymour (1986) proved that M(H) satisfies the Erdős-Pósa property if and only if H is planar. When H is planar, finding the smallest possible function f_{M(H)} has been an active area of research in the last years. In this talk we will survey some recent combinatorial and algorithmic results in this direction, and we will particularly focus on other variants of the Erdős–Pósa property such as the case where the k subgraphs have to be edge-disjoint or the case where M(H) is the class of graphs that contain a graph H as a topological minor. On going work with Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau. |
08.01.2015 |
---|
Christopher Kusch (FU Berlin) |
Random Algebraic Constructions |
Abstract: The aim of this talk is to introduce Bukh's random algebraic construction of large graphs not containing a given bipartite subgraph. If time permits, we discuss this method in the context of graphs with few paths of prescribed length between any two vertices as done by Conlon. |
15.01.2015 |
---|
Juanjo Rué (FU Berlin) |
Arithmetic removal lemmas and independent sets in hypergraphs |
Abstract: In the last years, several authors have studied sparse and random analogues of a wide variety of results in extremal combinatorics. Very recently, due to the work of Balogh, Morris, and Samotij, and the work of Saxton and Thomasson on the structure of independent sets on hypergraphs, several of these questions have been addressed in a new framework by using the so-called containers in hypergraphs. In this talk I will present how to use this technology together with arithmetic removal lemmas due to Serra, Vena and Kral in the context of arithmetic combinatorics. We will show how to get sparse (and random) analogues of well-known additive combinatorial results even in the non-abelian situation. This talk is based on a work (still in progress!) joint with Oriol Serra and Lluís Vena. |
21.01.2015 |
---|
Codruț Grosu (FU Berlin) |
On transversals avoiding complete subgraphs |
Abstract: Let G be a multipartite graph with each block of size b and maximum degree d. It was shown by Haxell that b ≥ 2d is a sufficient (and best possible) condition for G to contain an independent transversal. Szabó and Tardos studied a generalization of this problem, where one requires the transversal to be K_{s}-free instead of independent. They conjectured that the optimal lower bound for b is of the order of d/s. The purpose of this talk is to present an symptotic proof of this conjecture, due to Harris and Srinivasan. The proof uses a new version of the Local Lemma, which I will try to explain. |
22.01.2015 |
---|
Dennis Clemens (FU Berlin) |
Reiher's Clique Density Theorem |
Abstract: One of the most classic results in Extremal Graph Theory is Turán's Theorem, which guarantees the existence of cliques of given order r in a graph G, provided that its edge density d exceeds a certain threshold. Naturally, one may wonder how many such cliques must necessarily be contained in G when the edge density d becomes larger than this threshold. Lovász and Simonovits [1] conjectured their number to be at least F_{r}(d)n^{r} + O(n^{r-2}), where F describes a certain piecewise concave function. After some partial results in the last decades, the conjecture was proven by Christian Reiher [2] recently, by using weighted graphs and Lagrange multipliers which help to transfer this discrete problem into a continuous setting. In the talk we will see a construction showing that the above bound is tight asymptotically and then we will see an overview on the proof by Christian Reiher. [1] L. Lovász and M. Simonovits: On the number of complete subgraphs in a graph II, Studies in pure mathematics, pages 459-495, Birkhäuser, 1983. [2] C. Reiher: The Clique Density Theorem, Hamburger Beiträge zur Mathematik 462, pages 1-25, 2012. |
12.02.2015 |
---|
Christopher Pütz (FU Berlin) |
An exposition of the Green-Tao theorem |
Abstract: Szemerédi's theorem states that any subset A of the positive integers with positive natural density limsup_{N→∞} |A ∩ [N]|/N contains arbitrary long arithmetic progressions. Allowing sets to have natural density zero the assertion remains true under certain conditions. This result is called the relative Szemerédi theorem. One is able to construct a function that corresponds to a superset of almost all prime numbers, for which the relative Szemerédi theorem holds and provides arbitrary long arithmetic progressions in the prime numbers. This result is also known as the Green-Tao theorem and was first proven by Ben Green and Terence Tao. Lately there was a paper of Conlon, Fox and Zhao who gathered simplifications of the original proof that have been made in recent years and introduced a new key step that further simplifies the proof. In this talk I will give a sketch of the proof of the relative Szemerédi theorem for the special case of 3-term arithmetic progressions as well as an outline of how to construct such a function associated with a superset of almost all prime numbers. I will include the proofs of some well-chosen intermediate results. |
19.02.2015 |
---|
Tibor Szabó and Alexey Pokrovskiy (FU Berlin) |
Open problems in Ramsey Theory |
Abstract: A selection of fascinating open problems in all areas of Ramsey Theory will be presented. These problems were collected at the AIM Graph Ramsey Theory workshop, San Jose, January 2015. |
26.02.2015 |
---|
Alexey Pokrovskiy (FU Berlin) |
Open problems in Ramsey Theory (pt 2) |
Abstract: A selection of fascinating open problems in all areas of Ramsey Theory will be presented. These problems were collected at the AIM Graph Ramsey Theory workshop, San Jose, January 2015. If anyone has a problem they would like to present (not necessarily in Ramsey theory), feel free to bring it and present it. |
12.03.2015 |
---|
Lluis Vena (Charles University Prague) |
Deducing an arithmetic removal lemma from the removal lemma for hypergraphs and its applications |
Abstract: The (hyper)graph removal lemma says that if a large (hyper)graph K does not have many copies of a given (hyper)graph H, then K can be made free of copies of H by deleting a small number of edges. An arithmetic removal lemma says the following. Given a group G and some subset X_{i} of G, if a linear system Ax = 0 does not have many solutions with x_{i} in X_{i}, then we can obtain new sets X_{i}' where the linear system Ax = 0 does not have any solutions if the variables x_{i} take values in X_{i}'. The sets X_{i}' have been obtained from X_{i} by removing few of its elements. One of the applications of the arithmetic removal lemmas is a more direct proof of Szemerédi's Theorem, regarding finding arbitrarily long arithmetic progressions on the integers (or in other groups), and its multidimensional counterpart, regarding finding k-dimensional simplicies in Z^{k}. In this talk we show a deduction of an arithmetic removal lemma using the combinatorial one. |
19.03.2014 |
---|
Alexey Pokrovskiy (FU Berlin) |
Rainbow matchings and rainbow connectedness |
Abstract: Aharoni and Berger conjectured that every bipartite graph which is the union of n matchings of size n + 1 contains a rainbow matching of size n. This conjecture is a generalization of several old conjectures of Ryser, Brualdi, and Stein about transversals in Latin squares. I will discuss an approximate version of the Aharoni-Berger Conjecture - that if the matchings all have size at least n + o(n), then there is a rainbow matching of size n. The proof involves studying connectedness in coloured, directed graphs. The notion of connectedness that we introduce is perhaps of independent interest. |
23.03.2015 |
---|
Imre Leader (University of Cambridge) |
Tiling with Arbitrary Tiles |
Abstract: A `tile' is a finite subset T of Z^{n}. It may or may not be possible to partition Z^{n} into copies of T. However, Chalcraft conjectured that every T does tile Z^{d} for some d. In this talk, we will discuss some examples, and also a proof of the conjecture, recently obtained in joint work with Vytautas Gruslys and Ta Sheng Tan. |
09.04.2015 |
---|
Ewan Davies (London School of Economics) |
Counting in hypergraphs via regularity inheritance |
Abstract: We develop a theory of regularity inheritance in 3-uniform hypergraphs. As a simple consequence we deduce a slight strengthening of a counting lemma of Frankl and Rödl. We believe that the approach is sufficiently flexible and general to permit extensions of our results in the direction of a hypergraph blow-up lemma. |
30.04.2015 |
---|
Open Mic |
Problem Session |
Abstract: This week we will have an informal problem session. Everyone is encouraged to come with a conjecture or problem which they would like to see solved. |
21.05.2015 |
---|
Shagnik Das (FU Berlin) |
Comparable pairs in set families |
Abstract: Given a family of subsets of , we say two sets are comparable if or . Sperner’s celebrated theorem gives the size of the largest family without any comparable pairs. This result was later generalised by Kleitman, who gave the minimum number of comparable pairs appearing in families of a given size.
In this talk we shall consider a complimentary problem posed by Erdös and Daykin and Frankl in the early ‘80s. They asked for the maximum number of comparable pairs that can appear in a family of subsets of , a quantity we denote by . We will first resolve an old conjecture of Alon and Frankl, showing that when . Time (and interest) permitting, we shall then discuss some further improvements to bounds on for various ranges of the parameters. This is joint work with Noga Alon, Roman Glebov and Benny Sudakov. |
27.05.2015 |
---|
Sylwia Antoniuk (Adam Mickiewicz University) |
On the connectivity Waiter-Client game |
Abstract: We consider a variation of the connectivity Waiter-Client game played on an -vertex graph which consists of disjoint spanning trees. In this game in each round Waiter offers Client edges of which have not yet been offered. Client chooses one edge and the remaining edges are discarded. The aim of Waiter is to force Client to build a connected graph. If this happens Waiter wins. Otherwise Client is the winner. It is known that for and for and even , Waiter can always force Client to build a connected graph. Bednarska-Bzdega et al. [BBHKL2014] asked if this is true for the remaining values of . We give and answer to this question, namely we show that for most of the Waiter does not always have a Winning strategy. This is a joint work with Codrut Grosu and Lothar Narins. [BBHKL2014] M. Bednarska-Bzdega, D. Hefetz, M. Krivelevich, T. Łuczak, Manipulative waiters with probabilistic intuition |
03.06.2015 |
---|
Ana Zumalacárregui (University of New South Wales) |
Additive bases for intervals |
Abstract: A set is said to be an additive basis for the
interval if every element in the interval can be represented as
sum of two elements of the set. A natural question arises in this
context: how small could such a basis be?
In this talk we will address this question and study the minimal
cardinality of a Basis for (that is, the number of
representations of every element in is at least ). Even
though it is clear that such quantity is of order , an
asymptotic for
is not known to exist (even in the simplest case ). We will study
this quantity and show that both the and the tend to the
same constant as grows.
The strategy follows the lines of [CRV'10] where the case of -Sidon
sets for intervals was
studied (that is the number of representations is at most ) and
approaches the problem by considering successive constructions of sets
whose support is restricted.
A key point in the argument is to exploit good constructions -based on
ideas from Ruzsa [R'90]- of sets on finite groups whose representation
function is closed to be constant. Joint work with Javier Cilleruelo and Carlos Vinuesa. [CRV'10] J. Cilleruelo, I. Ruzsa, and C. Vinuesa. Generalized Sidon sets. Adv. Math., 225(5):2786-2807, 2010. [R'90] I. Z. Ruzsa. A just basis. Monatsh. Math., 109(2):145-151, 1990. |
04.06.2015 |
---|
Benny Sudakov (ETH Zürich) |
Grid Ramsey problem and related questions |
Abstract: The Hales-Jewett theorem is one of the pillars of Ramsey theory,
from which many other results follow. A celebrated result of Shelah says that Hales-Jewett numbers are primitive recursive. A key tool used in his proof, known as cube lemma, has become famous in its own right. In its simplest form, it says that if we color the edges of the Cartesian product in colors then, for sufficiently large, there is a rectangle with both pairs of opposite edges receiving the same color. Hoping to improve Selah’s result, Graham, Rothschild and Spencer asked more than 20 years ago whether cube lemma holds with , which is polynomial in . We show that this is not possible by providing a superpolynomial lower bound in . We also discuss a number of related questions, among them a solution of the problem of Erdos and Gyarfas on generalized Ramsey numbers. Joint work with Conlon, Fox and Lee. |
17.06.2015 |
---|
Florian Pfender (UC Denver) |
Semidefinite programming in extremal graph theory and Ramsey theory |
Abstract:
Ten years ago, Razborov developed the theory of flag algebras. In this theory, many extremal problems on densities of small substructures in large structures can easily be expressed and studied. One of the most successful methods inside this theory is the so called "plain flag algebra method." In this method, semidefinite programming is used to optimally combine a large set of true equalities and inequalities to bound densities in the extremal object. Many new results in extremal graph theory have been proved this way. In general, the method is often successful if the extremal example is a simple blow up of a small graph --- a very common outcome in this field. Another common outcome is an iterated blow up of a small graph. In this situation, the plain flag algebra method alone rarely succeeds. In this talk I will present a way how to extend the plain method to deal with a number of questions of this flavor. In the last part of the talk I will show a surprising trick how to use the plain method to improve the upper bounds on some small Ramsey numbers. This is joint work with Bernard Lidický. |
25.06.2015 |
---|
Christopher Kusch (FU Berlin) |
Strong Ramsey Games: Drawing on an infinite board |
Abstract: We will consider a strong Ramsey-type game played on the edges of the complete -uniform hypergraph with infinitely many vertices. Two players, first player and second player, try to claim edges to build a copy of a fixed graph . First player starts and whoever builds a copy of first wins. It is known that if they play on finitely many vertices, player one can guarantee to win, if the number of vertices is large enough. We will then prove that this is false on infinitely many vertices and provide sufficient conditions a hypergraph needs to satisfy in order for second player to guarantee a draw as well as a -uniform example of such a hypergraph. This is joint work with Dan Hefetz, Lothar Narins, Alexey Pokrovskiy, Clément Requilé and Amir Sarid. |
02.07.2015 |
---|
Boris Bukh (Carnegie Mellon University) |
Common subsequences in words and permutations |
Abstract: Every sufficiently large collection of objects always contains two similar objects. For example, a large collection of words contains a pair of words with a long common subsequence. How long? In this talk, we look at several versions of this problem. We will see how this problem leads to some algebraic constructions, Fourier-like arguments, and an innocently-looking problem about monotone functions. The talk is based on the joint works with Lidong Zhou, Jie Ma and Venkatesan Guruswami. The work began 3 years ago, on a visit to FU Berlin. |
08.07.2015 |
---|
Jozsef Balogh (University of Illinois at Urbana-Champaign) |
On the applications of counting independent sets in hypergraphs |
Abstract: Recently, Balogh-Morris-Samotij and Saxton-Thomason developed a method of counting independent sets in hypergraphs. I will survey the field, and explain several applications. This includes counting maximal triangle-free graphs, counting -free graphs, estimate volume of metric spaces, etc. These results are partly joint with Liu, Morris, Petrickova, Samotij, Sharifzadeh, and Wagner. |
15.07.2015 |
---|
Clément Requilé (FU Berlin) |
Triangles in random cubic planar graphs |
Abstract: This talk will be about the exact counting of triangles in cubic planar graphs, and some asymptotic consequences. The starting point is the study, done in [BKLMcD] by means of generating functions, of the asymptotic number of labeled cubic planar graphs with a fixed number of vertices. Our approach, following theirs, is based on connectivity decomposition and generating functions which reduce the problem to a map enumeration question. We show how to adapt this decompositions in order to encode triangles. At the end of the talk we will explain how to use these equations to get limiting laws for the number of triangles in cubic planar graphs, as well as the asymptotic number of triangle-free planar graphs on a given number of vertices. Work in progress with Juanjo Rué. [BKLMcD] M. Bodirsky, M. Kang, M. Löffler and C. McDiarmid. Random Cubic Planar Graphs. Random Structures and Algorithms, 30 (2007) 78-94. |
23.07.2015 |
---|
Dániel Korándi (ETH Zürich) |
A random triadic process |
Abstract: Given a random 3-uniform hypergraph H=H(n,p) on n vertices where each triple independently appears with probability p, consider the following graph process. We start with the star G_0 on the same vertex set, containing all the edges incident to some vertex v_0, and repeatedly add an edge xy if there is a vertex z such that xz and zy are already in the graph and xzy∈H. We say that the process propagates if it reaches the complete graph before it terminates. In this talk we show that the threshold probability for propagation is p=1/2√n using the differential equation method. As an application, we obtain the upper bound p=1/2√n on the threshold probability that a random 2-dimensional simplicial complex is simply connected. Joint work with Yuval Peled and Benny Sudakov. |