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 739 at the Institute of Education, 20 Bedford Way (note the change in venue from last term).

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

Next Speaker

• 24th March 2025 - Alexandru Malekshahian (King’s College, London)

  Many cycle lengths in degree-critical graphs and path lengths in trees

  
  

  A degree-3 critical graph is an $n$-vertex graph with $2n-2$ edges and no proper induced subgraph of minimum degree at least $3$. Proving a conjecture of Narins, Pokrovskiy and Szabó up to a constant factor, we show that every degree $3$-critical graph contains cycles of at least $\log n$ many different lengths. We also resolve two closely related conjectures of the same authors about trees: we prove that any $n$-vertex tree of maximum degree $\Delta$ has at least as many distinct leaf-to-leaf distances as the balanced $\Delta$-ary tree of the same order; and construct trees in which the set of these distances is “spread out” in a suitable sense.

  Joint work with Francesco Di Braccio, Kyriakos Katsamaktsis, Jie Ma and Ziyuan Zhao.