PhD seminar: Trees

  • Date:
  • Location: Ångströmlaboratoriet, Lägerhyddsvägen 1 64119
  • Lecturer: Johanna Strömberg
  • Contact person: Volodymyr Mazorchuk
  • Seminarium

Abstract:

Every connected graph has a spanning tree: a minimal connected subgraph. If the graph is weighted we can find a spanning tree of minimum weight. In this talk we will see a classical result by Alan Frieze on the expected weight of the minimum weight spanning tree of a graph with random edge weights as the number of vertices of the graph goes to infinity. For a sufficiently 'well-behaved' distribution of edges weights, the expected weight of the MST tends to $\xi(3)$, Apéry's constant. Both the classical proof and a more recent method build on the rich theory of random graphs. We will see an introduction to the relevant ideas from random graphs and a sketch of both proofs.