Return to Calendar

Photo of University Hall

University Calendar

Trees and subtrees

March 27, 2017, 3:00 pm - 4:00 pm
Location Science Hall - 102 the Sokol Room
Posted InCollege of Science and Mathematics
Mathematical Sciences Seminar Colloquium

Gary Gordon, Lafayette University

About the Seminar

Trees and subtrees are ubiquitous in graph theory. We’ll consider 2 questions involving them in this talk:

  1. Suppose T is a tree, and let sa,b be the number of subtrees of T with a edges and b leaves. Can you reconstruct T from all the sa,b’s?
  2. Suppose a subtree is randomly selected from the collection of all subtrees of Kn.

What is the probability that your subtree spans Kn?

The techniques used to solve both problems are elementary, and they are connected by two different graph polynomials. We will be able to answer both questions completely in this talk.

This is joint work with Alex Chin, David Eisenstat, Kellie MacPhee, Eleanor McDonnell and Charles Vincent.