Talk:Hirsch conjecture

Untitled

Three statements in this article seem to be jointly anomalous. (1)"Hirsch's conjecture is known to be true for d < 4" [and by implication is not known to be true for d=4 or d=5]. (2)The d-step conjecture is said to be "equivalent" [implying that Hirsch's conjecture is true if and only if the d-step conjecture is true]. (3)"The d-step conjecture is known to be true for d < 6" [and thus is true for d=4 and d=5]. (2) and (3) imply that (1) should refer to d < 6, unless "equivalent" in (2) needs to be replaced by "similar". Am I missing something here? Duoduoduo (talk) 17:43, 4 March 2010 (UTC)

I think the issue is that (for all d, Hirsch) <==> (for all d, d-step) but that the two are not the same for any particular d. In order to show that Hirsch is true for some particular n-facet d-dimensional polytope you might need to use the d-step conjecture for dimension d+n or something like that. —David Eppstein (talk) 17:56, 4 March 2010 (UTC)

Thanks! I wonder why the d-step conjecture cannot be trivially proven as follows: Deform the 2d-facet polytope into a unit hypercube, with facets x_i = 0 and x_i = 1 for i=1,...,d. Then it takes at most d pivots to get between any two vertices, by switching the value of x_i for some or all i. Is there some reason the deformation doesn't always work? Duoduoduo (talk) 16:02, 5 March 2010 (UTC)

Because not every 2d-facet polytope, not even every simple 2d-facet polytope is combinatorially equivalent to a hypercube? E.g. in 3d consider the polytope with two pentagonal faces sharing an edge, two triangular faces between them adjacent to the shared edge, and two quadrilateral faces filling in the remaining gaps. How do you deform it to a hypercube? —David Eppstein (talk) 16:15, 5 March 2010 (UTC)

Nice example -- thanks again. Duoduoduo (talk) 18:57, 5 March 2010 (UTC)

It appears that a counterexample to the conjecture has been announced; see http://gilkalai.wordpress.com/2010/05/10/francisco-santos-disproves-the-hirsch-conjecture/ —Preceding unsigned comment added by 129.22.117.119 (talk) 17:07, 10 May 2010 (UTC)

Indeed. I have modified the article to reflect this, but a complete rewrite is probably in order. Ratfox (talk) 17:55, 10 May 2010 (UTC)

Maybe the rewrite should wait until Santos' paper becomes available? Kalai is enough of a recognized expert that we can use his blog post as a self-published source but it doesn't have much detail in it. —David Eppstein (talk) 17:57, 10 May 2010 (UTC)

I agree. Wikipedia should not claim the conjecture is "false", until we have a reliable (i.e., peer-reviewed) source that agrees with (and clarifies) the "counter-example" claim. I'm not familiar with this conjecture, but it's possible that the counter-example leaves open other (closely related) statements of the conjecture. Justin W Smith ^talk/_stalk 18:15, 10 May 2010 (UTC)

For example, unless it's an infinite family of counterexamples in any arbitrary dimension, it's possible that the conjecture is still true for "sufficiently large n" or "sufficiently large d".(?) Justin W Smith ^talk/_stalk 18:22, 10 May 2010 (UTC)

No, if you have a counterexample in dimension d then a prism over it forms a counterexample in dimension d + 1. So if the conjecture is false in some dimension it's false in all higher dimensions (at least in the case Santos looks at with n = 2d: the prism has two more faces and its diameter is greater by one). It doesn't rule out the possibility of a linear bound on the diameter with a bigger constant factor, though. —David Eppstein (talk) 18:24, 10 May 2010 (UTC)

Ok. I need to think about this more (to be convinced), but I'm sure you're correct.I'm convinced.(20:36, 10 May 2010 (UTC)) Thanks for clarifying, Justin W Smith ^talk/_stalk 18:32, 10 May 2010 (UTC)

Here I expand on David's claim that a counter-example in dimension d implies a counter-example in all higher-dimensions.

• Let P_d be a polytope in dimension d with n faces that is a counter-example to Hirsch's conjecture.
• Since P_d is a counter-example to Hirsch's conjecture, there exist vertices v₁ and v₂ such that the shortest path between them is, distance(v₁, v₂) > n−d.
• Let prism(P_d) be the d+1 dimensional prism constructed from P_d. For vertex v_i in P_d, label the two vertices in prism(P_d) corresponding to it as v'_i and v''_i.
• By this construction, prism(P_d) is in dimension d+1 and has n+2 faces.
• Clearly, distance(v'₁, v''₂) = distance(v₁, v₂)+1 > n−d+1.
• Which is sufficient, i.e., we needed distance(v'₁, v''₂) > (n+2)−(d+1) = n−d+1.

(Previously here was a similar construction, which used the variable n incorrectly, that questioned David's claim). Justin W Smith ^talk/_stalk 20:32, 10 May 2010 (UTC)

Remove unreliable and apparently Original Research claims

A manuscript that is to be presented at a conference is hardly reliable, notwithstanding the good works of Santos in oriented matroid theory etc. Please remove the scuttlebutt until a reliable source appears. One hears rumors that similar conjectures have been proved by a demigod at Lake Cayuga rather frequently, I'm sorry to report. Thanks Kiefer.Wolfowitz (talk) 20:46, 11 May 2010 (UTC)

I replaced the "proven false" claim with, "In May 2010, it was announced that Francisco Santos had found a counter-example to this conjecture." Feel free to update/clarify this wording. Justin W Smith ^talk/_stalk 21:02, 11 May 2010 (UTC)

As stated above, Gil Kalai (whose blog this appears on) meets the "established expert in the relevant field" exception to WP:SPS, and Santos himself while less senior is a well-published researcher in this area. We should be careful to state only that the counterexample has been announced, but this is all highly credible. I think it should stay. —David Eppstein (talk) 21:25, 11 May 2010 (UTC)

I agree with the remarks on Kalai. However, I read no statement on Kalai's website that Kalai had read the manuscript and checked the proofs, so Kalai's expertise is irrelevant. Let me quote from Santo's own post on that website:

Regarding the second part of his proof: "(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 (2) is not explicit. On the one hand there are the “perturbations”, which may be difficult to work out explicitly. On the other hand there is the problem that this polytope will be huge. My estimate is it may have a billion vertices. I am not sure whether it is within our current computational capabilities to compute its diameter."

Santos's own statement does not inspire confidence. (Imagine Louis de Branges announcing the solution of the invariant subspace problem: de Branges is a great mathematician, who solved the Bieberbach conjecture, etc.; however the manuscripts for such solutions may take years of refereeing ...). I remind USA scientists of the NAS or AAAS (I forget which) ethics guidelines, which strongly advise an embargo on publicity (specifically news media) until the publication date (under normal circumstances). Why should Santos's claim distract the public from Svante Pääbo's announcement on Neanderthals & modern h.s.s. inter-breeding, etc.? Let Santos have his well-deserved public attention when his paper is published, imho. Kiefer.Wolfowitz (talk) 17:44, 12 May 2010 (UTC)

The claim in the article that "a counterexample has been announced" is perfectly factual and, unlike most untested claims of mathematical breakthroughs, already has a reliable third-party source (Kalai's blog post) attesting to the fact of the announcement. The fact that Kalai takes this seriously eough to post about it lends it enough weight to include in the article — basically, professional researchers in this area are excited about the claim. We shouldn't write our article using phrasing that implies that the supposed counterexample is widely accepted and refereed until it actually is, but I don't think that's an issue with the current version. It is not for us to try to judge the truth of the mathematics here, as that is not something the current text addresses. As for embargoing research until it is properly refereed, it's also not for us to judge the ethics of the announcement, but it was aimed at other mathematicians rather than the popular press, and our article should ideally be useful to both audiences. As far as I can tell you see to be claiming that mathematicians should stay locked in their towers and not talk to each other about what they're doing until it is all over — that's very much the opposite of the practice at any time in history, I think. Maybe it works well for lab sciences in which large teams work independently of each other, but mathematicians tend to collaborate with each other rather than just competing with each other, and the imposition of the guidelines you describe would stymie that. —David Eppstein (talk) 17:53, 12 May 2010 (UTC)

I think that it's great that Santos shared his announcement in appropriate venues and that Kalai helped publicize the claim, particularly having Santos list some of the ideas. Having an atmosphere of open discussion and sharing is important, as with the vitality of the Maurey-Schwartz seminar on functional analysis. I am concerned about publicizing the announcement on Wikipedia or in the news media, not with professional e-mail lists, etc. I am not imposing guidelines, but reminding editors of suggested operating procedures and also reminding editors that similar announcements have sometimes had more flaws than Andrew Wiles's announced proof of Fermat's last theorem, which required unexpected work to be published. (Perhaps I am a timid soul . . . .) Thanks Kiefer.Wolfowitz (talk) 19:05, 12 May 2010 (UTC)

National Academies of USA: Publication guidelines

I'm sorry for the word choice "embargo on publicity", which is too restrictive. Kiefer.Wolfowitz (talk) 19:37, 12 May 2010 (UTC)

If you find out or remember whose ethics guidelines you're referring to and where to view them, I'd be interested in seeing the link. Because I don't see anything about that in the AMS guidelines and can't find the AAAS or NAS ones you might be referring to. —David Eppstein (talk) 22:15, 12 May 2010 (UTC)

The national academy press has a page on the report: http://www.nap.edu/openbook.php?record_id=4917 Best regards,  Kiefer.Wolfowitz  (Discussion) 15:19, 26 March 2011 (UTC) page 11 states the following:

QUOTE

But if publication practices, either new or traditional, bypass quality control mechanisms, they risk weakening conventions that have served science well.

An example is the scientist who releases important and controversial results directly to the public before submitting them to the scrutiny of peers. If the researcher has made a mistake or the findings are misinterpreted by the media or the public, the scientific community and the public may react adversely. When such news is to be released to the press, it should be done when peer review is complete—normally at the time of publication in a scientific journal.

ENDQUOTE

(WP's quoting has been buggy since I used Firefox 4 and installed the latest Java yesterday. The referencing ref command works okay today.)  Kiefer.Wolfowitz  (Discussion) 15:28, 26 March 2011 (UTC)

Lower vs upper bound

The page currently claims that "the diameter of a polytope provides a lower bound on the number of steps needed by the simplex method". Surely the diameter in fact provides an *upper* bound? 2001:638:906:2:C8BA:CF5E:71B8:CC5A (talk) 23:27, 1 October 2015 (UTC)

No, it's a lower bound. If you start at a point diametrally opposite from the optimum point, you must always take at least the diameter number of steps, but you might take even more steps than that. —David Eppstein (talk) 23:37, 1 October 2015 (UTC)

Why unfortunate?

In the section “Counterexample” you say “Unfortunately, the Hirsch conjecture is not true in all cases, as shown by Francisco Santos in 2011.” Now I am wondering from what standpoint it is unfortunate that such a statement is actually wrong. Unless there are very good reasons that I am missing, I believe an encyclopedia should refrain from characterizing certain mathematical truths as unfortunate. 2A02:3036:262:4AE4:3DF5:E5F2:4877:7DA4 (talk) 21:57, 25 March 2023 (UTC)

I also found this "unfortunate" an unhappy formulation. I guess for mathematicians in this field it's unfortunate, because the Hirsch conjecture could have been a great lower bound for simplex algorithms the holy grail of linear programming (as stated in the first sentence). 2A02:8109:A38E:EA00:D4E0:4F2D:F45:7186 (talk) 22:04, 6 February 2024 (UTC)

Upper bound. Or more accurately: if the Hirsch conjecture were true then the existence of short simplex paths would raise hope that we could actually find these paths quickly. But it is not true (at least not in the strong form of the conjecture), so that hope is gone. —David Eppstein (talk) 22:37, 6 February 2024 (UTC)