[Facets-of-complexity] Invitation & Link to Monday Lecture & Colloquium - June 21 2021 - time is back to normal.

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our next Monday Lecture & Colloquium on June 21st.

Time is back to normal. 

Monday's Lecture & Colloquium will be online via Zoom, as used to.

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09
No password is required.

Online via:
Zoom - Invitation

Time: Monday, June 21st - 14:15 h

Lecture: Alexey Pokrovskiy (University College London)

Title: Linear size Ramsey numbers of hypergraphs

Abstract:

The size-Ramsey number of a hypergraph H is the minimum number of edges in a hypergraph G whose every 2-edge-colouring contains a monochromatic copy of H. This talk will be about showing that the size-Ramsey number of r-uniform tight path on n vertices is linear in n. Similar results about hypergraph trees and their powers will also be discussed. This is joint work with Letzter and Yepremyan.

Coffee Break!

Time: Monday, June 21st - 16:00 h s.t.

Colloquium: Patrick Morris (Freie Universität Berlin)

Title: Triangle factors in pseudorandom graphs

Abstract:

An (n, d, λ)-graph is an n vertex, d-regular graph with second eigenvalue in absolute value λ. When λ is small compared to d, such graphs have pseudo-random properties. A fundamental question in the study of pseudorandom graphs is to find conditions on the parameters that guarantee the existence of a certain subgraph. A celebrated construction due to Alon gives a triangle-free (n, d, λ)-graph with d = Θ(n^2/3) and λ = Θ(d^2/n). This construction is optimal as having λ = o(d^2/n) guarantees the existence of a triangle in a (n, d, λ)-graph. Krivelevich, Sudakov and Szab ́o (2004) conjectured that if n ∈ 3N and λ = o(d^2/n) then an (n, d, λ)-graph G in fact contains a triangle factor: vertex disjoint triangles covering the whole vertex set.  In this talk, we discuss a solution to the conjecture of Krivelevich, Sudakov and Szab ́o. The result can be seen as a clear distinction between pseudorandom graphs and random graphs, showing that essentially the same pseudorandom condition that ensures a triangle in a graph actually guarantees a triangle factor. In fact, even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition actually guarantees that such a graph G contains every graph on n vertices with maximum degree at most 2.