https://igorpak.wordpress.com/2024/10/01/the-bunkbed-conjecture-is-false/ Igor Pak's blog Views on life and math * Home * About Igor Pak * [ ] [] Home > Advice, Combinatorial inequalities, Combinatorics, Employment, Math writing, Mathematics, Mathematics Journals, New papers, Philosophy of Mathematics, power of negative thinking > The bunkbed conjecture is false The bunkbed conjecture is false October 1, 2024 igorpak Leave a comment Go to comments What follows is an unusual story of perseverance. We start with a conjecture and after some plot twists end up discussing the meaning of truth. While the title is a spoiler, you might not be able to guess how we got there... The conjecture The bunkbed conjecture (BBC) is a basic claim about random subgraphs. Start with a finite graph G=(V,E) and consider a product graph G x K [2] obtained by connecting the corresponding vertices on levels V^(1) and V^(2). Sort of like a bunkbed. Now consider random subgraphs of a this product graph. Bunkbed Conjecture: The probability that vertices u^(1) and v^(1) are connected is greater or equal than the probability that vertices u^(1) and v^(2) are connected. In other words, the probability of connecting two vertices on the same level cannot be smaller than when connect vertices on different levels. This is completely obvious, of course! And yet the conjecture this problem defeated several generations of probabilists and remained open until now. For a good reason, of course. It was false! The origins of the conjecture are murky, but according to van den Berg and Kahn it was conjectured by Kasteleyn in the early 1980s. There are many versions of this conjecture; notably one can condition on the subset of vertical edges and ask the same question. Many partial results are known, as well as results for other probabilistic models. The conjecture is false nonetheless! The direction Why look for a counterexample if the conjecture is so obviously true? Well, because you always should. For any conjecture. Especially if everyone else is so sure, as in completely absolutely sure without a doubt, that the conjecture is true. What if they are all wrong? I discuss this at length in this blog post, so there is no need to rehash this point. The counterexample We disprove the conjecture in a joint paper with Nikita Gladkov (UCLA) and Alexandr Zimin (MIT), both graduate students. Roughly speaking we take the following 3-hypergraph from a recent paper by Hollom. [hollom-graph] We then replace each yellow triangle with the following gadget using n=1204, placing a in the shaded vertex, while v[1] and v[n] are placed in the other vertices of the triangle (so the red path goes into the red path). For a stronger version of the conjecture that's all there is. For a weaker version, some additional tweaks needed to be made (they are not so important). And we are done! [image] The resulting graph is has 7523 vertices and 15654 edges. The difference between probabilities for paths between u[1] and u[10] at the same and different levels as in the conjecture is astronomically small, on the order of -10^-6500. But it's negative, which is all we need. Very very roughly speaking, the red path is the only path which avoids shaded vertices and creates a certain bias which give this probability gap. Formalizing this is a bit technical. The experiments Of course, the obvious way to verify our counterexample computationally would fail miserably -- the graph is much too large. Instead, we give a relatively elementary completely combinatorial disproof of the BBC that is accessible to a wide audience. I would rather not rehash technical details and ideas in the proof -- it's all in our paper, which is only 12 pages! See also the GitHub code and some explanation. I do want to mention that giving formal disproof was not our first choice. It's what we ended up doing after many failures. There is always a bit of a stigma people have about publicly discussing their failures. I know very few examples, only this one famous enough to be mentioned. So let me mention briefly how we failed. Since I was sure the bunkbed conjecture is false (for reasons somewhat different from my contrarian philosophy), we started with a myriad of computer experiments trying all small graphs. When those failed, we tried to use AI and other computer assisted tools. We burned many hours on a giant UCLA Hoffman2 Cluster getting closer for a while. In hindsight, we didn't look in the right place, obviously. After several months of computer experiments and no clear counterexample, it felt we are wasting time. We then thought a bit more about philosophy of what we are doing and stopped. Before I tell you why we stopped, let me make a general recommendation. Please do try computer experiments for whatever you are working on. Make an effort to think it through and design a good experiment. Work hard to test as much as your computer technology allows. If you need some computing power, ask around. Your university might just have the resources. Occasionally, you can even ask a private company to donate theirs. If you succeed, write a paper and publish it. Make your code and work notes publicly available. If you fail, do exactly the same. If the journals refuse to publish your paper, just keep it on the arXiv. Other people in your area would want to know. And as far as the NSF is concerned, all of this is "work product". You can't change the nature of the problem and the results you are getting, but you deserve the credit regardless. Let me repeat: Do not fear telling other you have not succeeded in your computer testing. Fear others making the same mistakes or repeating the same work that you did. The curse One reason we stopped is because in our initial rush to testing we failed to contemplate the implications of Monte Carlo testing of even moderately large graphs. Here is a quote from the paper: Suppose we did find a potential counterexample graph with only m= 100 edges and the probability gap was large enough to be statistically detectable. Since analyzing all of 2^m [?] 10^30 subgraphs is not feasible, our Monte Carlo simulations could only confirm the desired inequality with high probability. While this probability could be amplified by repeated testing, one could never formally disprove the bunkbed conjecture this way, of course. This raises somewhat uncomfortable questions whether the mathematical community is ready to live with an uncertainty over validity of formal claims that are only known with high probability. It is also unclear whether in this imaginary world the granting agencies would be willing to support costly computational projects to further increase such probabilities (cf. [Garrabrant+'16], [Zeilberger'93]). Fortunately, our failed computational effort avoided this dystopian reality, and we were able to disprove the bunkbed conjecture by a formal argument. Societal implications aside, it is an interesting question whether a reputable math journal should accept a counterexample that is tested with 99.99% confidence, and the results can be replicated and rechecked by others. Five sigma may be a gold standard in nuclear physics, but math journals tend to prefer 100% correctness (even though some papers they publish are 100% incorrect). What I do know, is that most journals would refuse to even consider a "five sigma counterexample". While details of the situations differ quite a bit, I knew what happened to the (rather interesting) Sills-Zeilberger paper, which was eventually published, but not after several desk rejections. But PhD students need jobs in reality, not in theory. That is really why we stopped. Why persevere and create controversy when you can just try doing something else? P.S. There is yet another layer to all of this. Back in 1999, I asked Avi Wigderson if P=BPP? He said "Yes". Last week I asked him again. This is 25 years later, almost to the day. He said "Yes, I am absolutely sure of that." It's one of his favorite conjectures, of course. If he is right, every probabilistic counterexample can be turned into deterministic. In other words, there would be a fully rigorous way to estimate both probabilities and prove on a computer that the conjecture is false. But you must have guessed what I was thinking when I heard what he said -- now he used "absolutely sure"... Share this: * Twitter * Facebook * Like Loading... Related Categories: Advice, Combinatorial inequalities, Combinatorics, Employment, Math writing, Mathematics, Mathematics Journals, New papers, Philosophy of Mathematics, power of negative thinking Tags: Alexandr Zimin, Avi Wigderson, Bernoulli percolation, Bunkbed Conjecture, Combinatorics, connected graph, Doron Zeilberger, GitHub, Jacob van den Berg, Jeff Kahn, mathematical writing, Mathematics journals, Monte Carlo testing, Nikita Gladkov, NSF, P=BPP, Philosophy , What if they are all wrong? Comments (0) Trackbacks (3) Leave a comment Trackback 1. No comments yet. 1. October 2, 2024 at 9:01 am Hacker News Jin Ri TOP 20| 2024-10-02 - Chu Hai Jue Jin ,Wu Xian Ke Neng . Wei Du Li Kai Fa Zhe , Kua Jing Dian Shang Cong Ye Zhe , Hai Wai Zi Mei Ti Ti Gong Zui Xin Chu Hai Zi Xun He Zi Yuan -Chu Hai Jue Jin , Wu Xian Ke Neng . Wei Du Li Kai Fa Zhe , Kua Jing Dian Shang Cong Ye Zhe , Hai Wai Zi Mei Ti 2. October 2, 2024 at 9:07 am The bunkbed conjecture is false surprisetalk on October 2, 2024 at 10:01 3. October 2, 2024 at 10:23 am The bunkbed conjecture is false | Igor Pak's blog Leave a comment We deserve better journals RSS feed * Google * Youdao * Xian Guo * Zhua Xia * My Yahoo! * newsgator * Bloglines * iNezha Search for: [ ] [Search] Recent Posts * The bunkbed conjecture is false * We deserve better journals * Two constructions * The power of negative thinking: Combinatorial and geometric inequalities * The journal hall of shame Archives * October 2024 * May 2024 * April 2024 * September 2023 * April 2023 * December 2022 * October 2022 * September 2022 * June 2022 * February 2022 * January 2022 * August 2021 * July 2021 * June 2021 * May 2021 * April 2021 * March 2021 * February 2021 * December 2020 * October 2020 * April 2019 * March 2019 * September 2018 * March 2018 * July 2017 * May 2017 * November 2016 * September 2016 * May 2015 * November 2014 * September 2014 * February 2014 * December 2013 * November 2013 * June 2013 * May 2013 * February 2013 * December 2012 * October 2012 * September 2012 * August 2012 * July 2012 * March 2012 Categories * Academic dishonesty * Academic life * Advice * Antisemitism * Asymptotic Group Theory * Awards * College Admissions * Combinatorial inequalities * Combinatorics * Discrete Geometry * Employment * English * Enumerative Combinatorics * Geometric inequalities * Graduate Schools * History of mathematics * humor * Journals * Math writing * Mathematicians * Mathematics * Mathematics Journals * Mathematics Publishers * Mathematics videos * New papers * Philosophy of Mathematics * polygon triangulations * power of negative thinking * predictions * Uncategorized * Undergraduate education * University administration Meta * Register * Log in * Entries feed * Comments feed * WordPress.com Top Blog at WordPress.com. * Comment * Reblog * Subscribe Subscribed + [croppe] Igor Pak's blog Join 181 other subscribers [ ] Sign me up + Already have a WordPress.com account? Log in now. * + [croppe] Igor Pak's blog + Customize + Subscribe Subscribed + Sign up + Log in + Copy shortlink + Report this content + View post in Reader + Manage subscriptions + Collapse this bar Loading Comments... You must be logged in to post a comment. %d [b]