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.

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.