Doktorandseminarium: Trees

  • Datum:
  • Plats: Ångströmlaboratoriet 64119
  • Föreläsare: Johanna Strömberg
  • Kontaktperson: Volodymyr Mazorchuk
  • Seminarium


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.