Tag Archives: Topological combinatorics

Polymath3 (PHC6): The Polynomial Hirsch Conjecture – A Topological Approach

Posted on April 13, 2011 by

This is a new polymath3 research thread. Our aim is to tackle the polynomial Hirsch conjecture which asserts that there is a polynomial upper bound for the diameter of graphs of -dimensional polytopes with facets. Our research so far was … Continue reading →

Posted in Convex polytopes, Geometry, Polymath3 | Tagged , , | 37 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 II: The Formula

Posted on June 18, 2008 by

In the first part of this post we discussed an appealing conjecture regaring an extension of Cayley’s counting trees formula. The number of d-dimensional “hypertrees” should somehow add up  to . But it was not clear to us which complexes we want … Continue reading →

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

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

A Small Debt Regarding Turan’s Problem

Posted on June 9, 2008 by

Turan’s problem asks for the minimum number of triangles on n vertices so that every 4 vertices span a triangle. (Or equivalently, for the maximum number of triangles on n vertices without a “tetrahedron”, namely without having four triangles on … Continue reading →

Posted in Combinatorics | Tagged , | 2 Comments