02.07.2020

David Fabian
(FU Berlin)

25.06.2020

Patrick Morris
(FU Berlin) 

18.06.2020

Ander Lamaison
FU Berlin 

11.06.2020

Tamás Mészáros
(FU Berlin)

12.02.2020

Patrick Morris
(FU Berlin)

05.02.2020

Pranshu Gupta
(TU Hamburg)

30.01.2020

Michał Seweryn
(Jagellonian University, Krakow)

29.01.2020

Charlotte Knierim
(ETH Zürich)

22.01.2020

Frederik Garbe
(Czech Academy of Sciences) 

15.01.2020

Bhargav Narayanan
(Rutgers University)

09.01.2020

Giulia Codenotti
(FU Berlin)

18.12.2019

Olaf Parczyk
(LSE)

12.12.2019

Simona Boyadzhiyska
(FU Berlin)

04.12.2019

David Fabian
(FU Berlin)

27.11.2019

Shagnik Das
(FU Berlin)

20.11.2019

Tamás Mészáros
(FU Berlin)

13.11.2019

Christoph Spiegel
(UPC Barcelona)

07.11.2019

Karola Mészáros
(Cornell University)

The longest path in a random graph has a scaling limit

Abstract: Group testing is concerned with identifying t defective items in a set of m items, where each test reports whether a specific subset of items contains at least one defective. In non-adaptive group testing, the subsets to be tested are fixed in advance. By testing multiple items at once, the required number of tests can be significantly smaller than m. In fact, if t is constant, the optimal number of (non-adaptive) tests is known to be Θ(log m). We consider the problem of non-adaptive group testing in a geometric setting, where the items are points in the plane and the tests are rectangles. We present upper and lower bounds on the required number of tests under this geometric constraint. In contrast to the general, combinatorial case, the bounds in our geometric setting are polynomial in m.

Joint work with László Kozma.

Abstract: The talk will consist of two parts, both concerning sampling colorings of (random) hypergraphs.

At the first part we will study an MCMC algorithm for sampling a (near) uniform q-coloring of a simple k-uniform hypegraph with n vertices and maximum degree D. Here q > max{ C₁(k) log n, C₂(k) D^{1/(k − 1)} }. For the second part we will let W_q denote the set of proper q-colorings of the random graph G(n,m), m = dn/2 and let H_q be the graph with vertex set W_q where two vertices are connected iff the corresponding proper colorings differ in a single vertex. We will show that for sufficiently large d, if q > (1+o(1)) d/log d then H_q is connected, providing an asymptotic matching upper bound to the lower bound given by Achlioptas and Coja-Oghlan. We then extend this result to random hypergraphs.

This talk is based on  joint work with Alan M. Frieze.

Abstract: Graph bootstrap percolation is a model introduced by Bollobás in 1968. Given a fixed, small graph H the H-bootstrap process on a graph G is the sequence (G_i) _{i ≥ 0} for which G₀ := G and G_i is obtained from G_i-1 by adding every edge that completes a copy of H. We investigate the maximum number of steps this process needs to stabilise when H is a tree and G has n vertices. More precisely, we show that for any tree T there exists a constant c_T such that the T-bootstrap process on any graph stabilises after at most c_T steps.

Abstract: We discuss a conjecture of Krivelevich, Sudakov and Szabó which states that there exists a constant c such that any n vertex d-regular graph with n ∈ 3ℕ and second eigenvalue in absolute value at most cd²/n, contains a triangle factor. This bound is best possible due a dense pseudorandom triangle free construction of Alon.

Abstract : The fractional and circular chromatic numbers are the two most studied non-integral refinements of the chromatic number of a graph. Starting from the definition of a coloring base of a graph, which originated in work related to ergodic theory, we formalize the notion of a gyrocoloring of a graph: the vertices are colored by translates of a single Borel set in the circle group, and neighbouring vertices receive disjoint translates. The corresponding gyrochromatic number of a graph always lies between the fractional chromatic number and the circular chromatic number. We investigate basic properties of gyrocolorings. In particular, we provide an example of a graph in which no optimal gyrocoloring exists, and study the separation between fractional, circular and gyrochromatic numbers. Joint work with Pablo Candela, Carlos Catalá, Robert Hancock, Adam Kabela, Dan Kraľ and Lluís Vena.

Abstract: We investigate the behavior of Boolean dimension with respect to components and blocks. To put our results in context, we note that for Dushnik-Miller dimension, we have that if dim(C) ≤ d for every component C of a poset P, then dim(P) ≤ max{2,d}; also if dim(B) ≤ d for every block B of a poset P, then dim(P) ≤ d + 2. By way of constrast, local dimension is well behaved with respect to components, but not for blocks: if ldim(C) ≤ d for every component C of a poset P, then ldim(P) ≤ d+2; however, for every d ≥ 4, there exists a poset P with ldim(P) = d and dim(B) ≤ 3 for every block B of P. In this paper we show that Boolean dimension behaves like Dushnik-Miller dimension with respect to both components and blocks: if bdim(C) ≤ d for every component C of P, then bdim(P) ≤ 2+d+4·2^d; also if bdim(B) ≤ d for every block B of P, then bdim(P) ≤ 19 + d + 18·2^d.

This is joint work with Piotr Micek and William T. Trotter. 

Abstract: Given graphs F,H and G, we say that G is (F,H)_v -Ramsey if every red/blue vertex colouring of G contains a red copy of F or a blue copy of H. Results of Łuczak, Ruciński and Voigt and, subsequently, Kreuter determine the threshold for the property that the random graph G(n,p) is (F,H)_v -Ramsey. In this talk we consider the sister problem in the setting of randomly perturbed graphs. In particular, we determine how many random edges one needs to add to a dense graph to ensure that with high probability the resulting graph is (F,H)_v -Ramsey for all pairs (F,H) that involve at least one clique.

This represents joint work with Shagnik Das and Andrew Treglown. 

Abstract: We say a graph G is q-Ramsey for another graph H if in every q-colouring of the edges of G there is a monochromatic copy of H. Additionally, if no proper subgraph of G is q-Ramsey for H, we say that G is minimal q-Ramsey for H. Let M_q(H) denote the set of all minimal q-Ramsey graphs for H. In 1976, Burr, Erdős, Lovász initiated the study of properties of this set. In particular, the parameter s_q(H)= min { δ(G) : G ∈ M_q(H) } has been of considerable interest. It is not difficult to show that s_q(H) ≥ qδ(H) - (q-1). We call a graph H q-Ramsey simple if this lower bound is the correct value of s_q(H). In 2010, Szabó et al. showed that many classes of bipartite graphs are 2-Ramsey simple. We define a graph H to be highly q-Ramsey simple if it is q-Ramsey simple and for every positive integer k there exists a minimal Ramsey graph for H with at least k vertices of degree s_q(H). We develop a new tool, called a pattern gadget, which helps us show that cycles of length at least four are highly q-Ramsey simple for all q ≥ 2. We also discuss similar results for other graphs.

This is a joint work with Simona Boyadzhiyska and Dennis Clemens.

Abstract: The notion of nowhere dense classes of graphs attracted much attention in recent years and found many applications in structural graph theory, algorithmics and logic. The powers of nowhere dense graphs do not need to be sparse, for instance the second power of star graphs are complete graphs. However, it is believed that powers of sparse graphs inherit somewhat simple structure. In this spirit, we show that for a fixed nowhere dense class of graphs and a positive integer d, in any n-vertex graph G in the class, there are disjoint vertex subsets A and B, each of size almost linear in n, such that in the d^th power of G, either there is no edge between A and B, or there are all possible edges between A and B.

This is joint work with Marcin Briański, Piotr Micek and Michał Pilipczuk.

Abstract: In this talk I show a connection between heavy cycles and cycle decompositions. We prove that every directed Eulerian graph can be decomposed into at most O(n log Δ) disjoint cycles, thus making progress towards the conjecture by Bollobás and Scott, and matching the best known upper bound from the undirected case. This also implies the existence of long cycles differing to the Erdős-Gallai bound for undirected graphs in only a log factor Our approach is based on finding heavy cycles in certain edge-weightings of directed graphs. As a further consequence of our techniques, we prove that for every edge-weighted digraph in which every vertex has out-weight at least 1, there exists a cycle with weight at least Ω(log log n/log n), thus resolving a question by Bollobás and Scott.

This is joint work with Maxime Larcher, Anders Martinsson and Andreas Noever.

Abstract: We introduce a limit theory for sequences of Latin squares paralleling the ones for dense graphs and permutations. The limit objects are certain distribution valued two variable functions, which we call Latinons, and left-convergence is defined via densities of kxl subpatterns of Latin Squares. The main result is a compactness theorem stating that every sequence of Latin squares of growing orders has a Latinon as an accumulation point. Furthermore, our space of Latinons is minimal, as we show that every Latinon can be approximated by Latin squares. This relies on a result of Keevash about combinatorial designs. We also introduce an analogue of the cut-distance and prove counterparts to the counting lemma, sampling lemma and inverse counting lemma.
This is joint work with R. Hancock, J. Hladky, and M. Sharifzadeh.

Abstract: A finite number of agents, each with their own measure of utility, would like to cut up a piece of cake amongst themselves. How efficiently can they do this? Almost everything one would like to know about this problem is known in the case where the agents all want a fair share of the cake. The more general problem where the agents have different claims to the cake is less well understood; in this talk, I shall present a new, efficient division procedure for the general problem that yields nearly optimal bounds. We’ll take the scenic route to the problem, first through some algebraic topology, and then end up at some combinatorics.

Abstract: We introduce unimodular triangulations, covers and the integer decomposition property of lattice polytopes, and briefly touch on motivations for their study. We then show that the following special classes of lattice polytopes have unimodular covers, in dimension three: the class of parallelepipeds and the class of Cayley sums of two polytopes where one is a weak Minkowski summand of the other.

The talk is based on joint work with Francisco Santos.

Abstract: Given a hypergraph H, the size-Ramsey number is the smallest integer m such that there exists a graph G with m edges with the property that in any colouring of the edges of G with two colours there is a monochromatic copy of H. Extending on results for graphs we prove that the size Ramsey number of the 3-uniform tight path on n vertices is linear in n.

This is joint work with Jie Han, Yoshiharu Kohayakawa, and Guilherme Mota.

Abstract: A graph G is Ramsey for another graph H if any two-coloring of the edges of G contains a monochromatic copy of H. We call G Ramsey minimal for H if G is Ramsey for H but no proper subgraph of G is. In this talk, we will present a result of Rödl and Siggers, showing that, for any k≥3 and n sufficiently large, there exist many graphs on at most n vertices that are Ramsey minimal for the k-clique. More precisely, we will show that, for any k≥3, there exist constants c(k)>1 and n₀(k) such that, for all n≥n₀(k), there are at least c^{n^2} Ramsey minimal graphs for K_k on at most n vertices.

This talk is based on the paper "On Ramsey minimal graphs" by V. Rödl and M. Siggers.

Abstract: Given a real parameter 0≤α<1, an α-strong Sidon set is a subset S⊂N of the positive integers such that for any w,x,y,z∊S with {w,x}≠{y,z} one has |(w+x)-(y+z)|≥ max{w^α,x^α,y^α,z^α}. In this talk we focus on the setting when S is infinite and study the asymptotics of the counting function S(n):=|S∩[n]|. By generalizing a construction of Cilleruelo we show that there exists an α-strong Sidon set S with counting function S(n) = n^{\sqrt{(1+α)^2+1}-(1+α)+o(1)}. Finally, we take a look at how α-strong Sidon sets can be used to bound the density of the largest Sidon set contained in a random infinite subset of the positive integers. We also describe how these results can be extended to B_h-sets.

This is joint work with Juanjo Rué and Christoph Spiegel.

Abstract: A well-known result of Rödl and Ruciński states that for any graph H there exists a constant C such that if p ≥ C n^{- 1/m_2(H)}, then the random graph G_n,p is a.a.s. H-Ramsey, that is, any 2-colouring of its edges contains a monochromatic copy of H. Aside from a few simple exceptions, the corresponding 0-statement also holds; that is, there exists c>0 such that if p≤ cn^-1/m_2(H) the random graph G_n,p  is a.a.s. not H-Ramsey.

We show that near this threshold, even when G_n,p  is not H-Ramsey, it is often extremely close to being H-Ramsey. More precisely, we prove that for any constant c > 0 and any strictly 2-balanced graph H, if p ≥ c n^-1/m_2(H), then the random graph G_n,p  a.a.s. has the property that every 2-edge-colouring without monochromatic copies of H cannot be extended to an H-free colouring after Ω(1) extra random edges are added. This generalises a result by Friedgut, Kohayakawa, Rödl, Ruciński and Tetali, who in 2002 proved the same statement for triangles, and addresses a question raised by those authors. We also provide a wide variety of examples to show that these theorems need not hold when H is not strictly 2-balanced, and extend a result of theirs in the 3-coloured setting.

This is joint work with David Conlon, Joonkyung Lee and our very own Tamás Mészáros.

Abstract: The greedy algorithm for finding a maximal independent set in a graph G on vertices V = {v_{1, ...,} v_n} can be described as follows. Let σ be a permutation of [n] chosen uniformly at random. Starting from an empty set R, at step i add v_σ(i) to the set R if and only if R∪{v_σ(i)} is an independent set in G. This very natural algorithm has been studied extensively in various settings in combinatorics, probability, computer science - and even in chemistry.

In this talk we present a natural and general framework for calculating the asymptotics of the proportion of the yielded independent set for sequences of (possibly random) graphs, involving a useful notion of local convergence. We use this framework both to give short and simple proofs for results on previously studied families of graphs, such as paths and binomial random graphs, and to study new ones, such as random trees.

This is joint work with Michael Krivelevich, Peleg Michaeli and Clara Shikhelman.

Abstract: Freiman's 2.4-Theorem states that any subset A of Z_p satisfying |2A| ≤ 2.4 |A| - 3 and |A| < p/35 can be covered by an arithmetic progression of length at most |2A| - |A| + 1. A more general result of Green and Ruzsa implies that this covering property holds for any set satisfying |2A| ≤ 3|A| - 4 as long as the rather strong density requirement |A| < p/10²¹⁵ is satisfied.

In this talk I will present a version of this statement that allows for sets satisfying |2A| ≤ 2.48|A| - 7 with the more modest density requirement of |A| < p/10¹⁰. In doing so, I hope to shed some light on how the methods of rectification and modular reduction go hand-in-hand when proving these types of small doubling covering property both in the cyclic setting and in the integers.

This is joint work with Pablo Candela and Oriol Serra.

Abstract: The flow polytope F_G associated to an acyclic graph G is the set of all nonnegative flows of size 1 on the graph G.  Fundamental questions about this and other flow polytopes include: (1) what is the polytope’s volume? (2) how many integer points are in it? I will explain how to use a reduction procedure on graphs to answer these question.

Abstract: We say that a two-coloring of a K_2k is k-unavoidable if one color forms either a clique of order k or two disjoint cliques of order k. Bollob\'as conjectured that for any ε and k, there exists an integer R(ε,k) such that any n≥R(ε,k) vertex graph with at least ε{n choose 2} edges in each color contains a k-unavoidable graph. This was proven by Cutler and Montágh, and Fox and Sudakov showed R(ε, k)=(1/ε)^θ(k). Here, we obtain several Turán-type variants of this result, such as showing that in any two-colored graph with density 1-(1/ε)^O(k) and at least ε fraction of the edge set in each color, there exists a k-unavoidable subgraph. A result with a similar flavour was recently obtained by DeVos et al. who showed that any graph with density above 2/3 whose edges are colored half red and half blue must contain a non-monochromatic triangle. We solve this same problem entirely for all cycles, and up to an additive constant, for all cliques.

This is joint work with Boris Bukh and Michael Tait.

Abstract: Let G(n,p) denote the random graph on n vertices where each edge appears independently with probability p=c/n. It is well known that p=1/n is the threshold for the existence of a giant component.  Erdős conjectured that if c > 1 then w.h.p. the length of the longest path of G(n,c/n), denoted by L(c,n), satisfies L(c,n) ≥ l(c)n where l(c) > 0 is independent of n. This was proved by Ajtai, Komlós and Szemerédi and in a slightly weaker form by de la Vega. The lower bound  was then improved in a series of papers. In this talk we go a step further and we show that  for sufficiently large c, w.h.p. L (c,n)/n  tends to some function f(c)  as n tends  to infinity.  In addition we give a method of computing f(c) to arbitrary accuracy.

This talk is based on joint work with Alan M. Frieze.