Tag Archives: Trees

Lawler-Kozdron-Richards-Stroock’s combined Proof for the Matrix-Tree theorem and Wilson’s Theorem

Posted on July 23, 2013 by

   David Wilson and a cover of Shlomo’s recent book “Curvature in mathematics and physics” A few weeks ago, in David Kazhdan’s basic notion seminar, Shlomo Sternberg gave a lovely presentation Kirchho ff and Wilson via Kozdron and Stroock. The lecture is based on … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Probability | Tagged , , | 4 Comments

A Proof by Induction with a Difficulty

Posted on July 22, 2009 by

  The time has come to prove that the number of edges in every finite tree is one less than the number of vertices (a tree is a connected graph with no cycle). The proof is by induction, but first you need … Continue reading →

Posted in Teaching, What is Mathematics | Tagged , | 17 Comments

A Beautiful Garden of Hypertrees

Posted on March 14, 2009 by

We had a series of posts (1,2,3,4) “from Helly to Cayley” on weighted enumeration of Q-acyclic simplicial complexes. The simplest case beyond  Cayley’s theorem were Q-acyclic complexes  with vertices, edges, and triangles. One example is the six-vertex triangulation of the … Continue reading →

Posted in Combinatorics | Tagged , , , , | Leave a comment

Helly’s Theorem, “Hypertrees”, and Strange Enumeration I

Posted on June 10, 2008 by

1. Helly’s theorem and Cayley’s formula Helly’s theorem asserts: For a family of n convex sets in , n > d, if every d+1 sets in the family have a point in common then all members in the family have a point in common. … Continue reading →

Posted in Combinatorics, Convexity | Tagged , , , , | 9 Comments