Francisco Santos Disproves the Hirsch Conjecture

A title and an abstract for the conference “100 Years in Seattle: the mathematics of Klee and Grünbaum” drew a special attention: Title: “A counter-example to the Hirsch conjecture” Author: Francisco Santos, Universidad de Cantabria Abstract:  I have been in Seattle only once, in January 2002, when I visited to give a colloquium talk at […]

The Polynomial Hirsch Conjecture: Discussion Thread, Continued

Here is a  link for the just-posted paper Diameter of Polyhedra: The Limits of Abstraction by Freidrich Eisenbrand, Nicolai Hahnle,  Sasha Razborov, and Thomas Rothvoss. And here is a link to the paper  by Sandeep Koranne and Anand Kulkarni “The d-step Conjecture is Almost true”  – most of the discussion so far was in this direction. We had a long and […]

The Polynomial Hirsch Conjecture: Discussion Thread

This post is devoted to the polymath-proposal about the polynomial Hirsch conjecture. My intention is to start here a discussion thread on the problem and related problems. (Perhaps identifying further interesting related problems and research directions.) Earlier posts are: The polynomial Hirsch conjecture, a proposal for Polymath 3 , The polynomial Hirsch conjecture, a proposal for Polymath […]

The Polynomial Hirsch Conjecture – How to Improve the Upper Bounds.

I can see three main avenues toward making progress on the Polynomial Hirsch conjecture. One direction is trying to improve the upper bounds, for example,  by looking at the current proof and trying to see if it is wasteful and if so where it can be pushed further. Another direction is trying to improve the lower-bound constructions for […]

The Polynomial Hirsch Conjecture, a Proposal for Polymath3 (Cont.)

The Abstract Polynomial Hirsch Conjecture A convex polytope is the convex hull of a finite set of points in a real vector space. A polytope can be described as the intersection of a finite number of closed halfspaces. Polytopes have a facial structure: A (proper) face of a polytope is the intersection of  with a […]

The Polynomial Hirsch Conjecture: A proposal for Polymath3

This post is continued here.  Eddie Kim and Francisco Santos have just uploaded a survey article on the Hirsch Conjecture. The Hirsch conjecture: The graph of a d-polytope with n vertices  facets has diameter at most n-d. We devoted several posts (the two most recent ones were part 6 and part  7) to the Hirsch conjecture and […]

Updates and plans III.

Update on the great Noga’s Formulas competition. (Link to the original post, many cash prizes are still for grab!) This is the third “Updates and plans post”. The  first one was from 2008 and the  second one from 2011. Updates: Combinatorics and more A lot is happening!  I plan  to devote special posts to some of these developments. […]

Combinatorics and More – Greatest Hits

Combinatorics and More’s Greatest Hits First Month Combinatorics, Mathematics, Academics, Polemics, … Helly’s Theorem, “Hypertrees”, and Strange Enumeration I (There were 3 follow up posts:) Extremal Combinatorics I: Extremal Problems on Set Systems (There were 4 follow up posts II ; III; IV; VI) Drachmas Rationality, Economics and Games Open problems Five Open Problems Regarding Convex Polytopes Seven Problems Around Tverberg’s Theorem F […]

Greatest Hits

Combinatorics and More’s Greatest Hits First Month Combinatorics, Mathematics, Academics, Polemics, … Helly’s Theorem, “Hypertrees”, and Strange Enumeration I (There were 3 follow up posts:) Extremal Combinatorics I: Extremal Problems on Set Systems (There were 4 follow up posts II ; III; IV; VI) Drachmas Rationality, Economics and Games Open problems Five Open Problems Regarding Convex Polytopes Seven Problems Around Tverberg’s Theorem F […]

Some old and new problems in combinatorics and geometry

Paul Erdős in Jerusalem, 1933  1993 Update: Here is a link to a draft of a paper* based on the first part of this lecture. Some old and new problems in combinatorial geometry I: Around Borsuk’s problem. I just came back from a great Erdős Centennial conference in wonderful Budapest. I gave a lecture on old and […]