Abstract: What large structures appear in every dense digraph? A celebrated result of Komlós, Sárközy and Szemerédi, answering a conjecture of Bollobás, states that for all ε > 0, every sufficiently large graph of order n and minimum degree n(1/2 + ε) contains every spanning tree of bounded maximum degree. This was later strengthened by the same authors to allow trees of degree c_ε n/log n (where c_ε is a constant depending on ε). The result has also been extended in a large number of directions.

In this talk, we discuss a generalization of this result for digraphs: for all ε > 0, every sufficiently large digraph G of order n and minimum semidegree n(1/2 + ε) contains every spanning tree of bounded degree (the minimum semidegree of G is the minimum of in- and out-degrees over all vertices of G).

In fact, our method establish the presence of a much more general family of arbitrarily oriented spanning subdigraphs, such as large subdivisions of a small graph, or collections of o(n^1/4) vertex-disjoint cycles.

Abstract: What large structures appear in every dense digraph? A celebrated result of Komlós, Sárközy and Szemerédi, answering a conjecture of Bollobás, states that for all ε > 0, every sufficiently large graph of order n and minimum degree n(1/2 + ε) contains every spanning tree of bounded maximum degree. This was later strengthened by the same authors to allow trees of degree c_ε n/log n (where c_ε is a constant depending on ε). The result has also been extended in a large number of directions.

In this talk, we discuss a generalization of this result for digraphs: for all ε > 0, every sufficiently large digraph G of order n and minimum semidegree n(1/2 + ε) contains every spanning tree of bounded degree (the minimum semidegree of G is the minimum of in- and out-degrees over all vertices of G).

In fact, our method establish the presence of a much more general family of arbitrarily oriented spanning subdigraphs, such as large subdivisions of a small graph, or collections of o(n^1/4) vertex-disjoint cycles.

Ths is joint work with Richard Mycroft.

08.07.2021

Alp Müyesser (FU Berlin)

Transversals in multiplication tables of abelian groups

Abstract: Given an n x n matrix M filled in with arbitrary symbols, a transversal is a selection of n entries of M which do not share a row, a column, or a symbol. When M is the multiplication table of a finite group G, Hall and Paige conjectured in 1955 that M has a transversal if and only if the Sylow 2-subgroups of G are trivial or non-cyclic. In 2009, Wilcox, Evans, and Bray gave a proof of this conjecture using the classification of finite simple groups. Giving a characterisation of sub-matrices of M with transversals is currently open, and even the abelian case is not fully understood. In this talk, we will characterise sub-matrices of multiplication tables of abelian groups which admit transversals. In particular, we will address a conjecture of Snevily from 1999.

This is joint work with Alexey Pokrovskiy.

30.06.2021

Igor Balla (Tel Aviv University)

Equiangular lines and graph spectra

Abstract: A set of lines passing through the origin in R^{r} is called equiangular if every pair of lines makes the same angle. In 1973, Lemmens and Seidel asked to determine the maximum number N_{α}(r) of equiangular lines in R^{r} with common angle arccos(α). Recently, B., Dräxler, Keevash, and Sudakov showed that N_{α}(r) ≤ 2r-2 for any fixed α ∈ (0,1) when r is exponentially large in 1/α, with equality if and only if α = 1/3. Building on their work, Jiang, Tidor, Yao, Zhang, and Zhao were able to determine N_{α}(r) completely for all α such that there exists a graph whose spectral radius is (1/α-1)/2 and when r is at least doubly exponentially large in 1/α. In both cases, the approach crucially relies on using Ramsey's theorem in order to bound the maximum degree of a corresponding graph.

In this talk we will discuss how we can use orthogonal projections of matrices with respect to the Frobenius inner product in order to overcome this limitation and thereby prove new bounds on N_{α}(r) which effectively bridge the gap between 2r(1+o(1)) when α = Θ(1) and (1-o(1))r^{2}/2 when α = Θ(1/r^{1/2}), as well as significantly improving on the only previously known universal bound N_{α}(r) ≤ 2/3 · r/α^{2} · (1+o(1)), due to Glazyrin and Yu.

Using the connection to real equiangular lines, our methods can also be used to obtain bounds on eigenvalues of the adjacency matrix of a regular graph. In particular, we show that for any k-regular graph on n vertices whose adjacency matrix has second and last eigenvalue λ_{2} and λ_{n} such that the spectral gap satisfies k - λ_{2} = o(n), we have λ_{2} ≥ (1 - o(1)) max(k^{1/3}, (-λ_{n})^{1/2}). In fact, our bounds work up to O(1) provided that the spectral gap is slightly smaller than n/2, and since we do not need an assumption on the diameter, this can be seen as the first generalization of the Alon-Boppana theorem to dense graphs.

Finally, we note that our method provides new inequalities involving the corresponding Gram matrix, which become equalities whenever there exist r·(r+1)/2 equiangular lines in R^{r}. We also derive analogous inequalities for complex equiangular lines and time permitting, we will discuss how our results generalize to this setting.

23.06.2021

Olaf Parczyk (LSE)

Resilience for Hamiltonicity in random hypergraphs

Abstract: Sudakov and Vu introduced the concept of local resilience of graphs for measuring robustness with respect to satisfying a given property. A classical result of Dirac states that any subgraph G of the complete graph on n vertices of minimum degree n/2 contains a Hamilton cycle. In the binomial random graph G(n,p) the threshold for the appearance of a Hamilton cycle is log(n)/n. Lee and Sudakov generalised Dirac’s result to random graphs by showing that with p > C log(n)/n asymptotically almost surely any subgraph G of G(n,p) with minimum degree (1/2+ε)n contains a Hamilton cycle, where C depends only on ε>0. These kind of resilience problems in random graphs received a lot of attention. In this talk we discuss a generalisation of the result of Lee and Sudakov to tight Hamilton cycles in random hypergraphs.

This is joint work with Peter Allen and Vincent Pfenninger.

16.06.2021

Julian Sahasrabudhe (University of Cambridge)

The singularity probability of random symmetric matrices

Abstract: Let M_{n} be drawn uniformly from all {+1,-1}-symmetric n by n matrices. We consider the following basic problem: what is the probability M_{n} is singular? While the analogous problem for matrices with all entries independent is now well understood, the case of symmetric matrices has remained somewhat more mysterious, despite the attention it has received. In this talk I will discuss our recent result which shows that the singularity probability is exponentially small. This talk is based on joint work with Marcelo Campos, Matthew Jenssen and Marcus Michelen.

10.06.2021

Simona Boyadzhiyska (FU Berlin)

Ramsey simplicity of random graphs

Abstract: We say that a graph G is q-Ramsey for another graph H if any q-coloring of the edges of G yields a monochromatic copy of H. Much of the research related to Ramsey graphs is concerned with determining the smallest possible number of vertices in a q-Ramsey graph for a given H, known as the q-color Ramsey number of H. In the 1970s, Burr, Erdős, and Lovász initiated the study of another graph parameter in the context of Ramsey graphs: the minimum degree.

A straightforward argument shows that, if G is a minimal q-Ramsey graph for H, then we must have δ(G) ≥ q(δ(H) - 1) + 1, and we say that H is q-Ramsey simple if this bound can be attained. In this talk, we will ask how typical Ramsey simplicity is; more precisely, we will discuss for which pairs p and q the random graph G(n,p) is almost surely q-Ramsey simple.

This is joint work with Dennis Clemens, Shagnik Das, and Pranshu Gupta.

02.06.2021

Giulia Maesaka (Universität Hamburg)

Embedding spanning subgraphs in uniformly dense and inseparable graphs

Abstract: In this talk we consider sufficient conditions for the existence of k-th powers of Hamiltonian cycles in n-vertex graphs G with minimum degree μn for arbitrarily small μ>0. About 20 years ago Komlós, Sarközy, and Szemerédi resolved the conjectures of Pósa and Seymour and obtained optimal minimum degree conditions for this problem by showing that μ=k/(k+1) suffices for large n. For smaller values of μ, the given graph G must satisfy additional assumptions. We show that inducing subgraphs of density d>0 on linear subsets of vertices and being inseparable, in the sense that every cut has density at least μ>0, are sufficient assumptions for this problem and, in fact, for a variant of the bandwidth theorem. This generalises recent results of Staden and Treglown.

Joint work with O. Ebsen, C. Reiher, M. Schacht and B. Schülke

26.05.2021

Leticia Mattos (IMPA)

Asymmetric Ramsey properties of random graphs for cliques and cycles

Abstract: We say that G ⟶ (F,H) if in every red and blue colouring of the edges of G we can find a red copy of F or a blue copy of H. In 1997, Kohayakawa--Kreuter conjectured the value of the threshold for this property when G is a random graph G(n,p). In this talk, we sketch the proof of Kohayakawa--Kreuter conjecture for the case that F is a clique and H is a cycle. Our main tool is a structural characterisation of Ramsey graphs for pairs of cliques and cycles.

Joint work with Anita Liebenau, Walner Mendonça and Jozef Skokan.

19.05.2021

Hong Liu (University of Warwick)

Sublinear expander and embeddings in sparse graphs

Abstract: A notion of sublinear expander has played a central role in the resolutions of a couple of long-standing conjectures in embedding problems in graph theory, including e.g. the odd cycle problem of Erdos and Hajnal that the harmonic sum of odd cycle length in a graph diverges with its chromatic number, Komlos's conjecture on the number of Hamilton subsets, average degree forcing dense/sparse graphs as minors etc. I will survey some of these developments.

12.05.2021

Andrea Freschi (University of Birmingham)

On Deficiency Problems for Graphs

Abstract: Nenadov, Sudakov and Wagner recently introduced the notion of graph deficiency: given a global spanning property P (eg Hamiltonicity) and a graph G, the deficiency def(G) of G with respect to P is the smallest non-negative integer t such that the join G*K_{t} has property P, where G*K_{t} is the graph obtained by adding t new vertices to G and adding all edges incident to at least one of the new vertices.

In particular, Nenadov, Sudakov and Wagner raised the question of determining how many edges an n-vertex graph G needs to ensure G*K_{t} contains a K_{r}-factor (for any fixed r >= 3). In this talk we present a solution to this problem. We also briefly discuss about an analogous result which forces G*K_{t} to contain any fixed bipartite (n+t)-vertex graph of bounded degree and small bandwidth.

This is joint work with Joseph Hyde and Andrew Treglown.

05.05.2021

Raphael Steiner (TU Berlin)

Zero sum cycles in complete digraphs

Abstract: Given a non-trivial finite Abelian group (A,+), let n(A)≥2 be the smallest integer such that for every labelling of the arcs of the bidirected complete graph of order n(A) with elements from A there exists a directed cycle for which the sum of the arc-labels is zero. The problem of determining n(Z_{q}) for integers q≥2 was recently considered by Alon and Krivelevich, who proved that n(Z_{q})=O(qlogq). Here we improve their bound and show that n(Z_{q}) grows linearly. More generally we prove that for every finite Abelian group A we have n(A)≤8|A|, while if |A| is prime then n(A)≤32|A|. As a corollary we also obtain that every K_{16q}-minor contains a cycle of length divisible by q for every integer q≥2, which improves a result by Alon and Krivelevich.

This is joint work with Tamás Mészáros.

28.04.2021

Peleg Michaeli (Tel Aviv University)

Discrepancies of Spanning Trees

Abstract: Discrepancy theory is concerned with colouring elements of a ground set so that each set in a given set system is as balanced as possible. In the graph setting, the ground set is the edge set of a given graph, and the set system is a family of subgraphs. In this talk, I shall discuss the discrepancy of the set of spanning trees in general graphs, a notion that has been recently studied by Balogh, Csaba, Jing and Pluhár. More concretely, for every graph G and a number of colours r, we look for the maximum D such that in any r-colouring of the edges of G one can find a spanning tree with at least (n-1+D)/r edges of the same colour. As our main result, we show that under very mild conditions (for example, if G is 3-connected), D is equal, up to a constant factor, to the minimal integer s such that G can be separated into r equal parts by removing s vertices. This strong and perhaps surprising relation between the extremal quantity D and a geometric quantity allows us to estimate the spanning-tree discrepancy for many graphs of interest. In particular, we reprove and generalize results of Balogh et al., as well as obtain new ones. For certain graph families, we also obtain tight asymptotic results.

The talk is based on joint work with Lior Gishboliner and Michael Krivelevich.

22.04.2021

Shagnik Das (FU Berlin)

Isomorphic bisections of cubic graphs

Abstract: Graph partitioning is the division of a graph into two or more parts based on certain combinatorial conditions, and problems of this kind of have been studied extensively. In the 1990s, Ando conjectured that the vertices of every cubic graph can be partitioned into two parts that induce isomorphic subgraphs. Using probabilistic methods together with delicate recolouring arguments, we prove Ando's conjecture for large connected graphs.This is joint work with Alexey Pokrovskiy and Benny Sudakov.

17.02.2021

Dömötör Pálvölgyi (ELTE)

At most 4.47^{n} stable matchings

Abstract: We improve the upper bound for the maximum possible number of stable matchings among n men and n women from O(131072^{n}) to O(4.47^{n}). To establish this bound, we develop a novel formulation of a probabilistic technique that is easy to apply and may be of independent interest in counting other combinatorial objects. Joint work with Cory Palmer.

10.02.2021

Tuan Tran (IBS)

Minimum saturated families of sets

Abstract: A family F of subsets of [n] is called s-saturated if it contains no s pairwise disjoint sets, and moreover, no set can be added to F while preserving this property. More than 40 years ago, Erdős and Kleitman conjectured that an s-saturated family of subsets of [n] has size at least (1 – 2^{-(s-1)})2^{n}. It is easy to show that every s-saturated family has size at least 2^{n-1}, but, as was mentioned by Frankl and Tokushige, even obtaining a slightly better bound of (1/2 + ε)2^{n}, for some fixed ε > 0, seems difficult. We prove such a result, showing that every s-saturated family of subsets of [n] has size at least (1 – 1/s)2^{n}. In this talk, I will present two short proofs. This is joint work with M. Bucic, S. Letzter and B. Sudakov.

03.02.2021

Michael Anastos (FU Berlin)

On a k-matching algorithm and finding k-factors in cores of random graphs

Abstract: We prove that for k+1 ≥ 3 w.h.p. the (k+1)-core of G_{n,p}, if non empty, spans a (near) spanning k-regular subgraph. This improves upon a result of Chan and Molloy and completely resolves a conjecture of Bollobas, Kim and Verstraëte. In addition, we show that w.h.p. such a subgraph can be found in linear time. A substantial element of the proof is the analysis of a randomized algorithm for finding k-matchings in random graphs with minimum degree k+1.

27.01.2021

David Fabian (FU Berlin)

The running time of Q_{3}-bootstrap percolation

Abstract: The bootstrap process of a graph H on a graph G is the sequence (G_{i})_{i≥0}, where G_{0} := G and G_{i} is obtained from G_{i-1} by adding every edge which completes a copy of H. Let M_{H}(n) be the smallest integer such that G_{i+1} = G_{i} for all i ≥ M_{H}(n) and every graph G on n vertices. It was shown by Bollobás, Przykucki, Riordan and Sahasrabudhe and, independently, by Matzke that M_{K_4}(n) = n-3. In 2019 Balogh, Kronenberg, Pokrovskiy and Szabó found a construction that gives M_{K_r}(n) = Θ(n^{2}) for r ≥ 6. In this talk we consider the problem of determining M_{H}(n) when H = Q_{3} and show that there exist constants c,C > 0 such that cn^{3/2} ≤ M_{Q_3}(n) ≤ Cn^{8/5} for all n ∈ N.

This is joint work with Patrick Morris and Tibor Szabó.

20.01.2021

Raphael Steiner (TU Berlin)

Complete minors via dichromatic numver

Abstract: The dichromatic number of a directed graph is the smallest integer k for which the vertex-set of the graph can be partitioned into k acyclic sets (not spanning a directed cycle). Inspired by the famous Hadwiger conjecture for undirected graphs, several groups of authors have recently studied the containment of complete digraph minors in directed graphs with given dichromatic number. We present a very short argument which improves the existing exponential upper bounds to almost linear bounds by reducing the problem to a recent result of Postle on Hadwiger's conjecture.

The talk represents recent joint work with Tamás Mészáros (FU Berlin).

13.01.2021

Yannick Mogge (TU Hamburg)

r-cross t-intersecting families via necessary intersection points

Abstract: Given integers r ≥ 2 and n,t ≥1 we call families ℱ_{1},...,ℱ_{r } ⊆ ℘([n]) r-cross t-intersecting if for all F_{i }∈ ℱ_{i}, i ∈ [r], we have |⋂_{i ∈ [r]} F_{i}| ≥ t. We obtain a strong generalisation of the classic Hilton-Milner theorem on cross intersecting families. In particular, we determine the maximum of ∑_{j ∈ [r]} |ℱ_{j}| for r-cross t-intersecting families in the cases when these are k-uniform families or arbitrary subfamilies of ℘([n]). Only some special cases of these results had been proved before. We obtain the aforementioned theorems as instances of a more general result that considers measures of r-cross t-intersecting families. This also provides the maximum of ∑_{j ∈ [r] }|ℱ_{j}| for families of possibly mixed uniformities k_{1},...,k_{r}.

This is a joint work with Pranshu Gupta, Simón Piga and Bjarne Schülke.

07.01.2021

Alp Müyesser (FU Berlin)

A proof of Ringel's Conjecture

Abstract: A typical decomposition question asks whether the edges of some graph G can be partitioned into disjoint copies of another graph H. One of the oldest and best known conjectures in this area, posed by Ringel in 1963, concerns the decomposition of complete graphs into edge-disjoint copies of a tree. It says that any tree with n edges packs 2n+1 times into the complete graph K_{2n+1}. Here we present a recent breakthrough result of Montgomery, Pokrovskiy and Sudakov that proves this conjecture for large n.

17.12.2020

Patrick Morris (FU Berlin)

A robust Corrádi-Hajnal Theorem

Abstract: The Corrádi-Hajnal Theorem states that any graph G with n ∈ 3ℕ vertices and minimum degree δ(G) ≥ 2n/3, contains a triangle factor, i.e. a collection of n/3 pairwise vertex-disjoint triangles. We show that any such G is `robust' with respect to this property, in that almost all (sufficiently dense) subgraphs of G contain a triangle factor. In detail, we define p*(n):=n^{-2/3 }log^{1/3}n and for a graph G and p=p(n), we define G_{p} to be random sparsification of G: the graph obtained from G keeping each edge independently with probability p. Our main result then states that there exists a C>0 such that for any G satisfying the Corrádi-Hajnal condition and any p=p(n) ≥ Cp*(n), G_{p} contains a triangle factor with high probability.

The minimum degree condition is tight due to the existence of graphs of minimum degree 2n/3 - 1 that do not contain a triangle factor. The bound on the probability is also tight up to the value of C. Indeed, as shown in seminal work of Johansson, Kahn and Vu, p* is the threshold for containing a triangle factor in G(n,p) (that is, taking G=K_{n} above). Our result can thus be seen as a common strengthening of the theorems of Corrádi-Hajnal and Johansson-Kahn-Vu.

This represents joint work with Peter Allen, Julia Böttcher, Jan Corsten, Ewan Davies, Matthew Jenssen, Barnaby Roberts and Jozef Skokan.

10.12.2020

Simona Boyadzhiyska (FU Berlin)

Hyperplane coverings with multiplicities

Abstract: It is known that the minimum number of hyperplanes needed to cover all points of F_{2}^{n} \ {0} while leaving the origin uncovered is n. In this talk, we will consider a variant of this problem in which the points have to be covered with certain multiplicities. More specifically, we will discuss the problem of determining the smallest number of hyperplanes required to cover all points of F_{2}^{n} \ {0} at least k times while covering the origin at most k-1 times and give tight bounds for certain ranges of the parameters n and k.

This talk is based on joint work with Anurag Bishnoi, Shagnik Das, and Tamás Mészáros.

03.12.2020

Ander Lamaison (Masaryk University Brno)

Quasirandom Latin squares

Abstract: In this talk we present the notion of quasirandom Latin squares, analogous to similar definitions in other discrete structures such as graphs and permutations. Proving a conjecture of Garbe et al., we will show that a sequence of Latin squares is quasirandom if and only if every $2\times 3$ pattern has density $1/720+o(1)$, and that $2\times 2$ or $1\times k$ patterns are not enough to guarantee quasirandomness. The main tool that we will use will be Latinons, a limit structure for Latin squares introduced by Garbe et al.

Joint work with Jacob Cooper, Dan Král’ and Samuel Mohr.

26.11.2020

Anurag Bishnoi (TU Delft)

Lower bounds for diagonal Ramsey numbers

Abstract: In a recent breakthrough Conlon and Ferber gave an exponential improvement in the lower bounds on diagonal Ramsey number R(t, t, \dots, t), when the number of colours is at least 3. We discuss their construction, along with the further improvement of Wigderson, and the finite geometry behind it.

18.11.2020

Raphael Steiner (TU Berlin)

Disjoint cycles of distinct lengths in directed graphs of large connectivity or large minimum degree

Abstract: A classical result by Thomassen from 1983 states that for every k ≥1 there is an integer f(k) such that every digraph with minimum out-degree f(k) contains k vertex-disjoint directed cycles. The known proof methods for Thomassen's result however do not give any information concerning the lengths of the k disjoint cycles.

In undirected graphs, it is true that sufficiently large minimum degree guarantess k disjoint cycles of equal lengths, as shown by Alon (1996), and also k disjoint cycles of distinct lengths, as shown by Bensmail et al (2017). Alon also gave a construction showing that there are digraphs of unbounded minimum out- and in-degree containing no k disjoint directed cycles of the same length.

In 2014 Lichiardopol made the following conjecture: For every k there exists an integer g(k) such that every digraph of minimum out-degree g(k) contains k vertex-disjoint directed cycles of pairwise distinct lengths.

This conjecture seems quite challenging, as already the existence of g(3) is unknown. For general k the conjecture is only proved in some special cases such as tournaments and regular digraphs by Bensmail et al. (2017).

In my talk I will present some recent ideas for finding disjoint cycles of distinct lengths in digraphs based on a new tool from structural digraph theory. I have the following partial results.

For every k there exists an integer s(k) such that every strongly s(k)-connected digraph contains k vertex-disjoint directed cycles of pairwise distinct lengths.

There exists an integer K such that every digraph of minimum out- and in-degree at least K contains 3 vertex-disjoint directed cycles of pairwise distinct lengths.

12.11.2020

Tibor Szabó (FU Berlin)

Mader-perfect digraphs

Abstract: We investigate the relationship of dichromatic number and subdivision containment in digraphs. We call a digraph Mader-perfect if for every (induced) subdigraph F, any digraph of dichromatic number at least v(F) contains an F-subdivision. We show that, among others, arbitrary orientated cycles, bioriented trees, and tournaments on four vertices are Mader-perfect. The first result settles a conjecture of Aboulker, Cohen, Havet, Lochet, Moura, and Thomassé, while the last one extends Dirac's Theorem about 4-chromatic graphs containing a K_{4}-subdivision to directed graphs.

The talk represents joint work with Lior Gishboliner and Raphael Steiner.

04.11.2020

Alp Müyesser (FU Berlin)

A rainbow version of Hajnal-Szemerédi Theorem

Abstract: Let G_{1}, … , G_{n/k} be a collection of graphs on the same vertex set, say [n], such that each graph has minimum degree (1-1/k+o(1))n. We show that [n] can then be tiled with k-cliques, each clique coming from a distinct graph. (Here, k is a constant and n is sufficiently large.) When all the graphs are identical, this result reduces to the celebrated Hajnal-Szemerédi Theorem. This extends a result of Joos and Kim, who considered the problem when k=2, and has applications to the study of cooperative colorings, a notion of graph coloring introduced by Aharoni, Holzman, Howard, and Sprüssel.