Upcoming talks

• 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.