Monday afternoon:
Simon Griffiths – Recent results on Ramsey numbers
Ramsey Theory is the study of inevitable structure, with examples occurring in various areas, including Graph Theory, Number Theory and Geometry. We discuss recent results on Ramsey numbers, including the exponential improvement for diagonal Ramsey numbers. Based on joint work with Marcelo Campos, Rob Morris and Julian Sahasrabudhe
Tuesday morning:
Penny Haxell – Degree criteria and stability for independent transversals
An independent transversal (IT) in a graph G with a given vertex partition P is an independent set of vertices of G (i.e. it induces no edges), that consists of one vertex from each part (block) of P. Over the years, various criteria have been established that guarantee the existence of an IT, often given in terms of P being t-thick, meaning all blocks have size at least t. One such result, obtained recently by Wanless and Wood, is based on b(G,P), the maximum of the degrees averaged over the blocks of P. They proved that if b(G,P) is at most t/4 then an IT exists. Resolving a problem posed by Groenland, Kaiser, Treffers and Wales (who showed that the ratio 1/4 is best possible), we give a best possible criterion for the existence of an IT in terms of b(G,P) and the maximum degree of G. This result interpolates between the criterion b(G,P) being at most t/4 and the old and frequently applied theorem that if G has maximum degree at most t/2 then an IT exists. We also extend a theorem of Aharoni, Holzman, Howard and Sprüssel, by giving a stability version of the latter result.
Tuesday afternoon:
Nicolás Sanhueza-Matamala – Separating systems
Given a graph G, say that a family F of paths in G is edge-separating if for every pair of edges there is a path in F which contains one but not the other. We are interested in finding edge-separating families of minimal size. We give an asympotically tight answer for all regular and “sufficiently connected” graphs. We also study a similar problem where in the definition we replace”edge” by “vertex”, and find the answer for many classes of random and quasirandom graphs. This is joint work with C. G. Fernandes and G. O. Mota; and with L. Lichev.
Wednesday morning:
Antonio Girão – Partitioning a tournament into sub-tournaments of high connectivity
A classical result of Hajnal and Thomassen asserts that for every $k$ there exists $K$ such that the vertices of every $K$-connected graph can be partitioned into two sets inducing $k$-connected subgraphs. Moreover they showed $K=O(k)$.
There is now a whole area of combinatorial problems concerned with questions of this type; namely, to understand whether for a certain (di)graph property any (di)graph which $\textit{strongly}$ satisfies that property has a vertex-partition into many parts where each part still has the property. K\”uhn, Osthus and Townsend proved the analogous result of Hajnal and Thomassen but in the tournament setting.
More precisely, they showed that every tournament which is $f(k,t)$-strongly-connected can be partitioned into $t$ parts such that each part is $k$-strongly connected. In this talk, we will discuss a recent result jointly with Shoham Letzter where we show $f(k,t)=O(kt)$ which is best possible and resolves a conjecture of the said authors.
Thursday morning:
Matias Pavez-Signé – Spanning trees in pseudorandom graphs
In 2007, Alon, Krivelevich and Sudakov conjectured that, under very mild conditions on the spectral gap, pseudorandom graphs are universal for the family of bounded-degree spanning trees. In this talk, we will show some progress towards resolving this conjecture, including some intermediate results that have been key in the recent solution of the Hamiltonicity problem in pseudorandom graphs by Draganić, Montgomery, Munhá Correia, Prokovsky and Sudakov.