Hirsch Conjecture 2

Here is more information about the counterexample to the Hirsch conjecture:

“my proof has two parts: (1) there is a 5-polytope with 48 facets, with the following properties: it has two vertices $u$ and $v$ contained in all the facets (each in 24 of them) and no path of length five joins $u$ to $v$. (2) Then there is what I call the “generalized $d$-step theorem” saying that from this, using certain wedges and perturbations, you can get a 43-dimensional polytope with 86 facets and without the Hirsch property. Part (1) is totally explicit and has been verified with computer software (polymake). Part (2) is not explicit.”

The above is from this post.

Also from the above post the polytope which provides the counterexample may have a billion vertices.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: