Recent Comments

Recent Posts
 Preview: The solution by Keller and Lifshitz to several open problems in extremal combinatorics
 Basic Notions Seminar is Back! Helly Type Theorems and the Cascade Conjecture
 My Very First Book “Gina Says”, Now Published by “World Scientific”
 Itai Benjamini: Coarse Uniformization and Percolation & A Paper by Itai and me in Honor of Lucio Russo
 AfterDinner Speech for Alex Lubotzky
 Boaz Barak: The different forms of quantum computing skepticism
 Bálint Virág: Random matrices for Russ
 Test Your Intuition 33: The Great Free Will Poll
 Mustread book by Avi Wigderson
Top Posts & Pages
 Preview: The solution by Keller and Lifshitz to several open problems in extremal combinatorics
 Elchanan Mossel's Amazing Dice Paradox (your answers to TYI 30)
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 TYI 30: Expected number of Dice throws
 Basic Notions Seminar is Back! Helly Type Theorems and the Cascade Conjecture
 The KadisonSinger Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
 A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24
 Extremal Combinatorics I: Extremal Problems on Set Systems
 Stan Wagon, TYI 23: Ladies and Gentlemen: The Answer
RSS
Category Archives: Convex polytopes
Ziegler´s Lecture on the Associahedron
The associahedron in 3 dimension, and James Stasheff. This picture is taken from Bill Casselman’s article on the associahedron. The article is entitled “Strange Associations” and starts with “There are many other polytopes that can be described in purely combinatorial terms. Among the … Continue reading
Posted in Convex polytopes
Tagged Associahedron, Cyclohedron, Permutahedron, Permutoassociahedron
7 Comments
Telling a Simple Polytope From its Graph
Peter Mani (a photograph by Emo Welzl) Simple polytopes, puzzles Micha A. Perles conjectured in the ’70s that the graph of a simple polytope determines the entire combinatorial structure of the polytope. This conjecture was proved in 1987 by Blind … Continue reading
Posted in Convex polytopes, Open problems
Tagged Eric Friedman, Peter Mani, Roswitta Blind
5 Comments
A Diameter problem (7): The Best Known Bound
Our Diameter problem for families of sets Consider a family of subsets of size d of the set N={1,2,…,n}. Associate to a graph as follows: The vertices of are simply the sets in . Two vertices and are adjacent if . … Continue reading
A Diameter Problem (6): Abstract Objective Functions
George Dantzig and Leonid Khachyan In this part we will not progress on the diameter problem that we discussed in the earlier posts but will rather describe a closely related problem for directed graphs associated with ordered families of sets. The role models for … Continue reading
Posted in Combinatorics, Convex polytopes, Open problems
Tagged Hirsch conjecture, Linear programming
7 Comments
A Diameter Problem (5)
6. First subexponential bounds. Proposition 1: How to prove it: This is easy to prove: Given two sets and in our family , we first find a path of the form where, and . We let with and consider the family … Continue reading
Diameter Problem (4)
Let us consider another strategy to deal with our diameter problem. Let us try to associate other graphs to our family of sets. Recall that we consider a family of subsets of size of the set . Let us now associate … Continue reading
Diameter Problem (3)
3. What we will do in this post and and in future posts We will now try all sorts of ideas to give good upper bounds for the abstract diameter problem that we described. As we explained, such bounds apply … Continue reading
Posted in Combinatorics, Convex polytopes, Open problems
Tagged Hirsch conjecture, Linear programming, Quasiautomated proofs
1 Comment
A Diameter Problem (2)
2. The connection with Hirsch’s Conjecture The Hirsch Conjecture asserts that the diameter of the graph G(P) of a dpolytope P with n facets is at most nd. Not even a polynomial upper bound for the diameter in terms of d and … Continue reading
Posted in Combinatorics, Convex polytopes, Open problems
5 Comments
A Diamater Problem for Families of Sets.
Let me draw your attention to the following problem: Consider a family of subsets of size d of the set N={1,2,…,n}. Associate to a graph as follows: The vertices of are simply the sets in . Two vertices and are adjacent … Continue reading
Posted in Combinatorics, Convex polytopes, Open problems
10 Comments
Euler’s Formula, Fibonacci, the BayerBillera Theorem, and Fine’s CDindex
Bill Gessley proving Euler’s formula (at UMKC) In the earlier post about Billerafest I mentioned the theorem of Bayer and Billera on flag numbers of polytopes. Let me say a little more about it. 1. Euler Euler’s theorem … Continue reading
Posted in Combinatorics, Convex polytopes
Tagged BayerBillera's theorem, CDindex, Flag numbers
4 Comments