The University College London (UCL) Combinatorics Seminar is held every Monday at 4–5pm during term time.

The venue for this week’s seminar is Room 706 at 25, Gordon Street.

To subscribe to the mailing list, please email Luke Collins at luke [dot] collins [dot] 22 [at] ucl [dot] ac [dot] uk.

Next Speaker

• 25th November 2024 - Jun Yan (University of Warwick)

  Ramsey Number of Trees

  
  

  Given a graph $G$, the Ramsey number $R(G)$ is defined to be the smallest $N$ such that any red/blue colouring of the complete graph $K_N$ contains a monochromatic copy of $G$. For a tree $T$ whose bipartition classes have sizes $t_1\geq t_2$, two simple constructions shows that $R(T)\geq R_B(T):=\max{t_1+2t_2,2t_1}-1$, and Burr conjectured in 1974 that $R(T)=R_B(T)$.

   It has been shown that Burr’s conjecture is false for certain trees called the double stars, though all of these known counterexamples have large maximum degrees. In 2002, Haxell, Łuczak and Tingley showed that an approximate version of Burr’s conjecture is true if one imposes a maximum degree condition. In an upcoming joint work with Richard Montgomery and Matías Pavez-Signé, we prove that Burr’s conjecture is true for all trees with up to small linear maximum degrees. That is, there exists $c>0$ such that for all trees $T$ on $n$ vertices with $\Delta(T)\leq cn$, $R(T)=R_B(T)$.