Combinatorics Seminar 2014/2015

Talks take place at Arnimallee 3, 14195 Berlin, Room A3/SR005, unless stated otherwise.

DateSpeakerTitle
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 Kk 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(nk) is the graph whose vertex set is ([n] choose k ) where two sets AB ∈ ([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(nk) 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 GS 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 fM(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 Ks-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 Fr(d)nr + O(nr-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 limsupN→∞ |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 Xi of G, if a linear system Ax = 0 does not have many solutions with xi in Xi, then we can obtain new sets Xi' where the linear system Ax = 0 does not have any solutions if the variables xi take values in Xi'. The sets Xi' have been obtained from Xi 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 Zk.

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 Zn. It may or may not be possible to partition Zn into copies of T. However, Chalcraft conjectured that every T does tile Zd 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.