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.

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.

09.07.2020

Michael Anastos (FU Berlin)

Sampling Colorings of Hypergraphs

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_{1}(k) log n, C_{2}(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.

02.07.2020

David Fabian (FU Berlin)

The running time of graph bootstrap percolation for trees

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_{0} := 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.

25.06.2020

Patrick Morris (FU Berlin)

Triangle factors in pseudorandom graphs

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^{2}/n, contains a triangle factor. This bound is best possible due a dense pseudorandom triangle free construction of Alon.

18.06.2020

Ander Lamaison (FU Berlin)

Coloring graphs by translates in the circle

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.

11.06.2020

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

Boolean dimension, components and blocks

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.

12.02.2020

Patrick Morris (FU Berlin)

Vertex Ramsey properties of randomly perturbed graphs

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.

05.02.2020

Pranshu Gupta (TU Hamburg)

Pattern gadgets and highly Ramsey-simple graphs

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.

30.01.2020

Michał Seweryn(Jagellonian University, Krakow)

Erdös-Hajnal properties for powers of sparse graphs

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.

29.01.2020

Charlotte Knierim(ETH Zürich)

Long Cycles, Heavy Cycles and Cycle Decompositions in Directed Graphs

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.

22.01.2020

Frederik Garbe(Czech Academy of Sciences)

Limits of Sequences of Latin Squares

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.

15.01.2020

Bhargav Narayanan(Rutgers University)

Disproportionate Division

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.

09.01.2020

Giulia Codenott(FU Berlin)

Unimodular covers of 3-dimensional parallelepipeds and Cayley sums

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.

18.12.2019

Olaf Parczyk(LSE)

The size-Ramsey number of tight 3-uniform paths

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.

12.12.2019

Simona Boyadzhiyska(FU Berlin)

On Ramsey minimal graphs for cliques

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_{0}(k) such that, for all n≥n_{0}(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.

04.12.2019

David Fabian (FU Berlin)

On infinite α-strong Sidon sets

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.

27.11.2019

Shagnik Das (FU Berlin)

Ramsey games near the critical threshold

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.

20.11.2019

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

Greedy maximal independent sets via local limits

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.

13.11.2019

Christoph Spiegel (UPC Barcelona)

A step beyond Freiman's theorem for set addition modulo a prime

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^{215} 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^{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.

07.11.2019

Karola Mészáros (Cornell University)

Encoding polytopal properties with (reductions on) graphs

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.

30.10.2019

Alp Müyesser (FU Berlin)

Turán-type results for unavoidable subgraphs

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.

24.10.2019

Michael Anastos (FU Berlin)

The longest path in a random graph has a scaling limit

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.