Abstract: A classical theorem of Kleitman in extremal combinatorics states that a collection of binary vectors in {0, 1}^{n} with diameter d has cardinality at most that of a Hamming ball of radius d/2.
In this talk, we present a new proof of Kleitman's diametric theorem via spectral methods, and discuss some extensions and generalizations of Kleitman's Theorem, as well as a few other related extremal problems.
Joint work with Oleksiy Klurman (KTH) and Cosmin Pohoata (Caltech).
19.06.2019
Tamás Mészáros (FU Berlin)
Unlabeled compression schemes and corner peelings for ample and maximum classes
Abstract: I will be presenting recent work by Chalopin, Chepoi, Moran and Warmuth.
"We examine connections between combinatorial notions that arise in machine learning and topological notions in cubical/simplicial geometry. These connections enable to export results from geometry to machine learning. Our first main result is based on a geometric construction by Tracy Hall (2004) of a partial shelling of the cross polytope which can not be extended. We use it to derive a maximum class of VC dimension 3 that has no corners. This refutes several previous works in machine learning from the past 11 years. In particular, it implies that all previous constructions of optimal unlabeled sample compression schemes for maximum classes are erroneous. On the positive side we present a new construction of an unlabeled sample compression scheme for maximum classes. We leave as open whether our unlabaled sample compression scheme extends to ample (a.k.a. lopsided or extremal) classes, which represent a natural and far-reaching generalization of maximum classes. Towards resolving this question, we provide a geometric characterization in terms of unique sink orientations of the 1-skeletons of associated cubical complexes."
13.06.2019
Tibor Szaabó (FU Berlin)
Slow bootstrap percolation
Abstract: Graph-bootstrap percolation, also known as weak saturation, was introduced by Bollobás in 1968. In this process, we start with initial "infected" set of edges E_{0}, and infect new edges according to a predetermined rule. Given a graph H and a set of previously infected edges E_{t} ⊆ E(K_{n}), we infect a non-infected edge e if it completes a new copy of H in G=([n], E_{t} ∪ e). A question raised by Bollobás asks for the maximum time the process can run before it stabilizes. Bollobás, Przykucki, Riordan, and Sahasrabudhe considered this problem for the most natural case where H=K_{r}. They answered the question for r ≤ 4 and gave a non-trivial lower bound for every r ≤ 5. They also conjectured that the maximal running time is o(n^{2}) for every integer r. In a joint work with József Balogh, Gal Kronenberg, and Alexey Pokrovskiy we disprove their conjecture for every r ≥ 6 and we give a better lower bound for the case that r=5 using Behrend's construction of large 3-term arithmetic progression-free sets of integers.
05.06.2019
Anurag Bishnoi (FU Berlin)
A construction for clique-free pseudorandom graphs
Abstract: A construction of Alon and Krivelevich gives highly pseudorandom K_{k}-free graphs on n vertices with edge density equal to Θ(n^{-1/(k-2)}). In this talk I will give a construction of an infinite family of highly pseudorandom K_{k}-free graphs with a higher edge density of Θ(n^{-1/(k-1)}), for all k≥3, using the geometry of quadratic forms over finite fields.
(Joint work with Ferdinand Ihringer and Valentina Pepe.)
22.05.2019
William T. Trotter (Georgia Institute of Technology)
Dimension and Maximum Degree
Abstract: The maximum degree of a poset is the maximum degree in the associated comparability graph. For an integer k, let f(k) denote the maximum dimension of a poset P with maximum degree k. It was shown in 1991 by Erdős, Kierstead and Trotter that f(k) = Ω(k logk). In 1986, Füredi and Kahn showed that f(k) = O(k log^{2}k). Just in 2018, Scott and Wood made the following subtle but dramatic improvement: f(k) = O(log^{1+o(1)}k). We outline the proof which uses an iterated application of the Lovász Local Lemma.
15.05.2019
Piotr Micek (Jagellonian University Krakow and TU Berlin)
p-centered colorings of planar graphs
Abstract: A p-centered coloring of a graph G is a coloring of its vertices such that for every connected subgraph H of G either H receives more than p colors or there is a color that appears exactly once in H. Very recently, we have shown that every planar graph admits a p-centered coloring with O(p^{3 }log(p)) colors. This improves an O(p^{19}) bound by Pilipczuk&Siebertz. We also know that some planar graphs require Omega(p^{2 }log(p)) colors. We have tight bounds for outerplanar graphs, stacked triangulations, and graphs of bounded treewidth.
Ongoing work with Stefan Felsner and Felix Schröder.
08.05.2019
Tuan Tran (ETH Zürich)
Dense induced bipartite subgraphs in triangle-free graphs
Abstract: The problem of finding dense induced bipartite subgraphs in H-free graphs has a long history, and was posed 30 years ago by Erdős, Faudree, Pach and Spencer. We obtain several results in this direction. First we prove that any H-free graph with minimum degree at least d contains an induced bipartite subgraph of minimum degree at least c_H log d/log log d, confirming (asymptotically) several conjectures by Esperet, Kang and Thomassé. Complementing this result, we further obtain optimal bounds for this problem in the case of dense triangle-free graphs, and we also answer a question of Erdős, Janson, Luczak and Spencer.
Joint work with Kwan, Letzter and Sudakov.
02.05.2019
Joonkyung Lee (Universität Hamburg)
On the extremal number of subdivisions
Abstract: The extremal number ex(n, H) is the maximum number of edges in an H-free graph with n vertices. When H has chromatic number at least three, the asymptotic behaviour of the extremal number is well understood, but when H is bipartite, the function remains mysterious. We give new estimates for the extremal numbers of various bipartite graphs H, especially if H can be obtained by subdividing edges of another graph H' in certain ways. Joint work with David Conlon and Oliver Janzer.
24.04.2019
Ander Lamaison (FU Berlin)
Ramsey upper density of infinite graphs
Abstract: Let H be an infinite graph. In a two-coloring of the edges of the complete graph on the natural numbers, what is the densest monochromatic subgraph isomorphic to H that we are guaranteed to find? We measure the density of a subgraph by the upper density of its vertex set. This question, in the particular case of the infinite path, was introduced by Erdős and Galvin. Following a recent result for the infinite path, we present bounds on the maximum density for other choices of H, including exact values for a wide class of bipartite graphs.
17.04.2019
Simona Boyadzhiyska (FU Berlin)
On counting problems related to (mutually) orthogonal Latin squares
Abstract: After the question of existence of a combinatorial structure satisfying given properties, a natural and important problem is to determine how many such objects there are. In this talk, we will consider some counting questions related to (mutually) orthogonal Latin squares. We will prove an upper bound on the number of ways to extend a set of k mutually orthogonal Latin squares to a set of k+1 mutually orthogonal Latin squares and discuss some applications, comparing the resulting bounds to previously known lower and upper bounds.
This talk is based on joint work with Shagnik Das and Tibor Szabó.
10.04.2019
Andrew Treglown (Birmingham)
A degree sequence Komlós theorem
Abstract: A classical topic is graph theory concerns finding minimum degree conditions that force a given spanning subgraph in a graph. There has also been interest in generalising such results via degree sequence conditions. Komlós' theorem determines the minimum degree that forces an H-tiling in a graph G covering a given proportion of the vertices in G. (An H-tiling is simply a collection of vertex-disjoint copies of H in G.) In this talk we will discuss a degree sequence generalisation of this result. This is joint work with Hong Liu and Joseph Hyde.
06.03.2019
Tibor Szabó (FU Berlin)
List Ramsey numbers
Abstract: We introduce the list colouring extension of classical Ramsey numbers, investigate when the two Ramsey numbers are equal, and in general, how far apart they can be from each other. We find graph sequences where the two are equal and where they are far apart. For l-uniform cliques we prove that the list Ramsey number is bounded by an exponential function, while it is well-known that the Ramsey number is super-exponential for uniformity at least 3. This is in great contrast to the graph case where we cannot even decide the question of equality for cliques. Joint work with Noga Alon, Matija Bucic, Tom Kalvari, and Eden Kuperwasser.
21.02.2019
Jan van den Heuvel (LSE)
Partial solutions to Hadwiger's Conjecture
Abstract: Hadwiger's Conjecture (1943) asserts that every graph without the complete graph K_{t+1} as a minor has a proper vertex-colouring using at most t colours. Since the conjecture is stubbornly refusing to be proved, we might look at relaxed versions of it. In the talk we discuss some results around the following question: If we are given t colours to colour a graph without K_{t+1}-minor, what kind of vertex-colourings can we guarantee with those t colours?
13.02.2019
Ferdinand Ihringer (Ghent University)
Rank Bounds on the Independence Number
Abstract: Recently, the breakthrough results by Croot, Lev, and Pach on progression-free sets in ℤ_{4}^{n}_{ }and by Ellenberg and Gijswijt on cap sets brought new attention to rank arguments for bounding sets in combinatorial problems. We discuss several traditional applications of rank arguments to bound the independence number of a graph. The examples include the orthogonality graph on {-1,1}^{n}, generalized quadrangles, Hermitian dual polar graphs, and quasisymmetric designs.
06.02.2019
David Fabian (FU Berlin)
Rainbow arithmetic progressions and anti-van der Waerden numbers
Abstract: Given a colouring of a set in an ambient abelian group, a rainbow arithmetic progression is an arithmetic progression whose elements receive pairwise distinct colours. We are going to consider two related problems that have been studied over the last years: First we ask whether any k-colouring of [n] with equally sized colour classes admits a rainbow arithmetic progression of length k. The second problem is to find the smallest positive integer r, for which every r-colouring of [n] contains a rainbow k-AP. We shall also have a look at the analogous problems when [n] is replaced by a finite abelian group.
30.01.2019
László Kozma (FU Berlin)
Hamiltonicity below Dirac's condition
Abstract: Dirac's theorem (1952) is a classical result of graph theory, stating that an n-vertex graph (n≥3) is Hamiltonian if every vertex has degree at least n/2. Both the value n/2 and the requirement for every vertex to have high degree are necessary for the theorem to hold. In this work we give efficient algorithms to determine whether a graph is Hamiltonian when either of the two conditions are relaxed.
Joint work with Bart Jansen and Jesper Nederlof.
23.01.2019
Anurag Bishnoi (FU Berlin)
Non-intersecting Ryser hypergraphs
Abstract: A famous conjecture of Ryser states that every r-partite hypergraph has vertex cover number at most r − 1 times the matching number. In recent years, hypergraphs meeting this conjectured bound, known as r-Ryser hypergraphs, have been studied extensively. It was proved by Haxell, Narins and Szabó that all 3-Ryser hypergraphs with matching number ν > 1 are essentially obtained by taking ν disjoint copies of intersecting 3-Ryser hypergraphs. In this talk we will see new infinite families of r-Ryser hypergraphs, for any given matching number ν > 1, that do not contain two vertex disjoint intersecting r-Ryser subhypergraphs.
16.01.2019
Jan Corsten (LSE)
Erdős-Rothschild problem for five and six colours
Abstract: Given positive integers n,r,k, the Erdős-Rothschild problem asks to determine the largest number of r-edge-colourings without monochromatic k-cliques a graph on n vertices can have. In the case of triangles, i.e. when k=3, the solution is known for r = 2,3,4. We investigate the problem for five and six colours.
09.01.2019
Péter Pál Pach (BME)
Polynomial Schur's theorem
Abstract: We consider the Ramsey problem for the equation x+y=p(z), where p is a polynomial with integer coefficients. Under the assumption that p(1)p(2) is even we show that for any 2-colouring of ℕ the equation x+y=p(z) has infinitely many monochromatic solutions. Indeed, we show that the number of monochromatic solutions with x,y,z∈ {1,2,\dots,n} is at least n^{2/d^3-o(1)}, where d=deg p.
On the other hand, when p(1)p(2) is odd, that is, when p attains only odd values, then there might not be any monochromatic solution, e.g., this is the case when we colour the integers according to their parity. We give a characterization of all 2-colourings avoiding monochromatic solutions to x+y=p(z).
This is a joint work with Hong Liu and Csaba Sándor.
19.12.2018
Christoph Spiegel (UPC)
Intervals in the Hales-Jewett Theorem
Abstract: The Hales–Jewett Theorem states that any r–colouring of [m]^{n} contains a monochromatic combinatorial line if n is large enough. Shelah’s proof of the theorem implies that for m = 3 there always exists a monochromatic combinatorial lines whose set of active coordinates is the union of at most r intervals. I will present some recent findings relating to this observation. This is joint work with Nina Kamcev.
12.12.2018
Jozef Skokan (LSE)
The k-colour Ramsey number of odd cycles via non-linear optimisation
Abstract: For a graph G, the k-colour Ramsey number R_{k}(G) is the least integer N such that every k-colouring of the edges of the complete graph K_{N} contains a monochromatic copy of G. Let C_{n} denote the cycle on n vertices. We show that for fixed k > 2 and n odd and sufficiently large,
R_{k}(C_{n}) = 2^{k-1}(n-1) + 1.
This generalises a result of Kohayakawa, Simonovits and Skokan and resolves a conjecture of Bondy and Erdős for large n. We also establish a surprising correspondence between extremal k-colourings for this problem and perfect matchings in the hypercube Q_{k}. This allows us to in fact prove a stability-type generalisation of the above. The proof is analytic in nature, the first step of which is to use the Regularity Lemma to relate this problem in Ramsey theory to one in convex optimisation.
This is joint work with Matthew Jenssen.
05.12.2018
Alexandra Wesolek (FU Berlin)
Bootstrap percolation in Ore-type graphs
Abstract: In the r-neighbour bootstrap process on a graph G we start with an initial set of infected vertices A_{0} ⊆ V(G) and a new vertex gets infected as soon as it has r infected neighbours. We call A_{0} percolating if an infection of A_{0} infects all of our graph. Under which conditions on G can we find a small percolating set A_{0}? In general, the denser our graph is the easier it is to infect new vertices as the initially infected vertices share potentially more neighbours. If v(G) ≤ r then we need to infect at least r vertices initially to infect all of our graph otherwise we will not be able to infect any new vertices during the bootstrap process. Gunderson showed that if a graph G on n vertices has minimum degree δ(G) ≤ ⌊ n/2 ⌋ + r - 3 then we can always find a percolating set of size r (if r ≤ 4 and n is big enough). How much can we decrease the minimum degree conditions if we are initially allowed to infect r+k vertices for k ∈ ℕ? What if we consider more general graphs where the sum of the degrees of any two non-adjacent vertices x and y is deg(x) + deg(y) ≤ D? This is more general because if a graph G has δ(G) = D/2 then for any two vertices in G it holds that deg(x) + deg(y) ≤ D. In this talk we give conditions on D=D(r,k) that guarantee a percolating set of size r + k, answering both open questions at once for small enough k=k(r).
29.11.2018
Hong Lius (Warwick)
Enumeration in arithmetic setting
Abstract: I will discuss several recent extremal results on enumerating subsets of integers/groups with various additive and multiplicative constraints.
28.11.2018
Andrew Newman (TU Berlin)
Small simplicial complexes with large torsion in homology
Abstract: From the work of Kalai on ℚ-acyclic complexes it is known that for d ≥ 2 a d-dimensional simplicial complex on n vertices can have enormous torsion, on the order of exp(Θ_{d}(n^{d})), in its (d-1)st homology group. However, explicit constructions of complexes which realize this enormous-torsion phenomenon have been somewhat rare. Therefore, in this talk we consider and affirmatively answer the following inverse question: Given a finite abelian group of order m, can one always construct a d-dimensional simplicial complex on Θ_{d}((log m)^{1/d}) vertices which realizes the given group in its (d - 1)st homology group?
21.11.2018
Sophia Elia (FU Berlin)
A comparison of Quotient Posets
Abstract: Given an equivalence relation on the elements of a poset, place a new relation on the equivalence classes of elements. If this new relation is reflexive, antisymmetric, and transitive, then a quotient poset is created. We survey different types of quotient posets and see how they compare. In particular, we look at quotient posets that arise from lattice congruences, order-preserving group actions, and as images of surjective maps. We characterize quotient posets that correspond to a certain relation on equivalence classes by defining a sequence related to transitivity. Then we look at an application of quotient posets arising from order-preserving group actions. Let Hom(P,n) be the set of order-preserving maps from a poset P to a chain with elements. Stanley showed that |Hom(P,n)| is given by a polynomial in . Given an order-preserving group action on P, there is an induced group action on Hom(P,n). Katharina Jochemko showed that the number of maps in Hom(P,n)up to equivalence under the induced group action is also polynomial in using quotient posets. We touch on an alternative approach to the proof through the Ehrhart theory of order polytopes.
31.10.2018
Patrick Morris (FU Berlin)
On the discrepancy of permutation families
Abstract: For a set family S⊆ 2^{n}, the discrepancy of S is
One can think of this as a colouring problem. Given a set system, we are interested in colouring the ground set red/blue such that in every set the difference between the number of red and number of blue points is as small as possible. Given a set of permutations π_{1},...,π_{k} on [n], we can define a set family S(π_{1},...,π_{k}) by taking all sets that occur as intervals in each of the permutations. Formally,
How large can the discrepancy of such a family be?
It turns out that for any n∈ ℕ and two permutations, π,σ on [n], we have that disc(S(π,σ))≤ 2. What about three permutations? Beck conjectured (around 1987) that this should also be bounded by a constant. In 2009, Matoušek described this as ``one of the most tantalising questions in combinatorial discrepancy". In this talk, we will present the eventual resolution of this conjecture by Newman and Nikolov in 2011. The talk will end with an invitation to an open problem.
31.10.2018
Tamás Mészáros (FU Berlin)
Sample compression schemes
Abstract: In this talk we concentrate on two fundamental concepts of classical machine learning theory: learning and compression. Motivated by the fact that if a concept class admits a small sample compression scheme then it is efficiently learnable (Littlestone and Warmuth), we propose to study the relationship between the size of sample compression schemes and the combinatorial notion of VC dimension. In particular, we propose several directions to tackle the compression scheme conjecture which states that the smallest possible size of a sample compression scheme is linear in the VC dimension of the underlying concept class.
24.10.2018
Roman Glebov (Ben Gurion University)
Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs
Abstract: Consider the random process in which the edges of a graph G are added one by one in a random order. A classical result states that if G is the complete graph K_{2n} or the complete bipartite graph K_{n,n}, then typically a perfect matching appears at the moment at which the last isolated vertex disappears. We extend this result to arbitrary k-regular bipartite graphs G on 2n vertices for all k=Ω(n). Surprisingly, this is not the case for smaller values of k. We construct sparse bipartite k-regular graphs in which the last isolated vertex disappears long before a perfect matching appears. Joint work with Zur Luria and Michael Simkin.