Tag Archives: Trees

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

   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

  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

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 , , , , | 1 Comment

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

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 , , , , | 10 Comments