Amazing: Hao Huang Proved the Sensitivity Conjecture!

Today’s arXived amazing paper by Hao Huang

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

Contains an amazingly short and beautiful proof of a famous open problem from the theory of computing – the sensitivity conjecture posed by Noam Nisan and Mario Szegedi

Hao Huang

Abstract: In this paper, we show that every 2^{n-1}+1-vertex induced subgraph of the n-dimensional cube graph has maximum degree at least \sqrt n. This result is best possible, and improves a logarithmic lower bound shown by Chung, Füredi, Graham and Seymour in 1988. As a direct consequence, we prove that the sensitivity and degree of a boolean function are polynomially related, solving an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.

The proof relies on the important relation found by Gotsman and Linial between the two problems mentioned in the abstract. It makes beautiful use of Cauchy’s interlace theorem (for eigenvalues).

Thanks to Noga Alon for telling me about the breakthrough. For more on the conjecture and a polymath project devoted to solving it, see this post on Aaronson’s Shtetl Optimized (SO).  See also this post on GLL.

Also today on the arXive a paper by Zuzana (Zuzka) Patáková and me: Intersection Patterns of Planar Sets. Like one of my very first papers “Intersection patterns of convex sets” the new paper deals with face numbers of nerves of geometric sets.

Links to further discussion of Huang’s breakthrough

See this new lovely post on SO (and don’t miss the excellent comment thread); and this post by Boaz Barak on WOT (Window on Theory) explains the main ingredient of Huang’s proof. Here is a post by Lance Fortnow on CC (Computational Complexity) mentioning a remarkable tweet by Ryan O’Donnell (see below the fold). Here is a comment by Hao on SO on the history of his own work on the problem since he heard it from Mike Saks in 2012.

More: And here is a lovely new post by Ken Regan on GLL, and here on Fedor Petrov’s new blog (congratulations, Fedya!) you can see the proof without the interlace theorem (as was also noted by Shalev Ben David); and here on CC Lance explains the proof of the Gotsman Linial reduction. (On Fedor’s blog you can find a combinatorial proof that  e⩽π!)

July, 25: An excellent QM (Quanta Magazine) article by Erica Klarreich. And another lovely post on GLL with a message that I and many other share: Huang’s new method is very very promising.

July 27-29: A great expository post on WN (What’s new) where Terry Tao presents the proof and describe a connection with Clifford algebras. It mentions a preprint by Roman Karasev where a connection of Huang’s “signed adjacency matrix” with exterior algebra is described. A connection of Huang’s “signing” of the edges of the discrete cube and Clifford algebras was also observed by  Tom Mrowka, and by Daniel Mathiews who used it to give a weighted generalization of the result.  Hao himself explains his motivation for the signing in a comment to Terry’s post.  In comment 83 on the SO thread, Vitor Bosshard points out a connection between Huang’s signing (actually, a small variation) and the Klee-Minty cube! Very interesting discussions of Huang’s proof in a wider persepective can be found in  Anurag math blog and also in the Ratio Bound the blog of (Ferdinand Ihringer). Anurag describes a related earlier work by Hao Huang, Oleksiy Klurman and Cosmin Pohoatato,  proving a theorem of Kleitman and various new extensions.

Don Knuth wrote a 1-page writeup of Huang’s proof. (Comment 85 on SO; he added “(but I’m not sure if God will vote for it)”. Wenjie Zheng (Comment 86 on SO) also wrote a post about it. Dima Pasechnik asked (comment 84): Does Huang’s matrix have a large monomial (i.e. signed permutation matrices) centraliser? Ferdinand Ihringer’s interesting and decorated comment over WN showed that there is a large body of research on pseudo-adjacency matrices of graphs with few eigenvalues. And over La Ciencia de la Mula Francis, el blog de Francisco R. Villatoro, “La conjetura de la sensibilidad ha sido demostrada.”

July 31: A very nice article by Rafi Letzter on LiveScience.  A quote by me: “Huang took this matrix, and he modified it in a very ingenious and mysterious way,” Kalai said. “It’s like you have an orchestra and they play some music, and then you let some of the players, I don’t know, stand on their head, and the music becomes completely different — something like that.”

Belated links on Yaroslav Shitov’s disproof of Hedetniemi’s conjecture

A few months ago we discussed Yaroslav Shitov’s disproof of Hedetniemi’s 1966 conjecture. Here are links to strengthening of the result by  Claude Tardif and Xuding Zhu and by by Xiaoyu He and Yuval Wigderson. And here is a lovely Quanta Magazine article by Erica Klarreich about it, ending with a quote by Noga Alon: “Sometimes, the reason that a conjecture is very hard to prove is simply that it is false.”

Continue reading

Advertisements
Posted in Combinatorics, Computer Science and Optimization | Tagged , | 18 Comments

Another sensation – Annika Heckel: Non-concentration of the chromatic number of a random graph

Annika Heckel

Sorry for the long period of non blogging. There are a lot of things to report and  various other plans for posts and I hope to come back to it soon. But it is nice to break the silence with another sensational result by Annika Heckel. I first heard about it some time ago and Noam Lifshitz just informed be that the paper is on the arXive!

Non-concentration of the chromatic number of a random graph

And here is the abstract: We show that the chromatic number of $latex G(n,1/2)$ is not concentrated on fewer than n^{1/4-\epsilon}  consecutive values. This addresses a longstanding question raised by Erdős and several other authors.

The Introduction tells the history of the problem very nicely.

Posted in Combinatorics | Tagged | Leave a comment

A sensation in the morning news – Yaroslav Shitov: Counterexamples to Hedetniemi’s conjecture.

Two days ago Nati Linial sent me an email entitled “A sensation in the morning news”. The link was to a new arXived paper by Yaroslav Shitov: Counterexamples to Hedetniemi’s conjecture.

Hedetniemi’s 1966 conjecture asserts that if G and H are two graphs, then the chromatic number of their tensor product G \times H equals the minimum of their individual chromatic numbers.  Here, the vertex set of G \times H is the Cartesian product of V(G) and V(H) and two vertices (g_1,h_1) and (g_2,h_2) are adjacent if g_1 is adjacent to g_2 and  h_1 is adjacent to h_2. (mistake corrected.) Every coloring of G induces a coloring  of G \times H, and so is every coloring of H.  Therefore, \chi (G \times H) \le \min (\chi (G), \chi (H)). Hedetniemi conjectured that equality always hold and this is now refuted by  by Yaroslav Shitov.

The example and the entire proof are quite short (the entire paper is less than 3 pages; It is a bit densely-written).

Yaroslav Shitov 

To tell you what the construction is, I need two important definitions.  The first  is the notion of the exponential graph {\cal E}_c(H).

The exponential graph  {\cal E}_c(H) arose in the study of Hedetniemi’s conjecture in a 1985 paper by El-Zahar and Sauer. The vertices of {\cal E}_c(H) are all maps from V(H) to \{1,2,\dots,c\}. Two maps \phi, \psi are adjacent if whenever v,u are adjacent vertices of H then \phi(u) \ne \psi (v)El-Zahar and Sauer showed that importance of the case  that H is a graph and G is an exponential graph of H for Hedetniemi’s conjecture. (The entire conjecture reduces to this case.) It is thus crucial to study  coloring of exponential graphs which is the subject of the three claims of Section 1 of Shitov’s paper.

The second definition is another important notion of product of graphs: The strong product G ⊠ H of two graphs H and G. The set of vertices is again the Cartesian product of the two sets of vertices. This time,  (g_1,h_1) and (g_2,h_2) are adjacent in G ⊠ H if either

(a) g_1 is adjacent to g_2 and  h_1 is adjacent to h_2

OR

(b) g_1 is adjacent to g_2 and  h_1 = h_2 or g_1 =g_2 and  h_1 is adjacent to h_2

(The edges of condition (a) are the edges of the tensor product of the two graphs and the edges of condition (b) are the edges of the Cartesian product of the two graphs.)

For Shitov’s counterexample given in Section 2 of his paper, H is the strong product of a graph L with girth at least 10 and fractional chromatic number at least 4.1 with a large clique of size q. The second graph G is the exponential graph {\cal E}_c(H). Put c =\lceil 4.1q \rceil.  Shitov shows that when c is sufficiently large then  the chromatic number of both H,G is c,  but the chromatic number of their tensor product is smaller than c.

(Have a look also at Yaroslav’s other arXived papers! )

Finite and infinite combinatorics

Let me make one more remark. (See the Wikipedea article.) The infinite version of Hedetniemi’s conjecture was known to be false.  Hajnal (1985) gave an example of two infinite graphs, each requiring an uncountable number of colors, such that their product can be colored with only countably many colors. Rinot (2013) proved that in the constructible universe, for every infinite cardinal , there exist a pair of graphs of chromatic number greater than , such that their product can still be colored with only countably many colors. (Here is the paper.) Is there a relation between the finite case and the infinite case? (Both theories are quite exciting but direct connections are rare. A rare statement where the same proof applies for the finite and infinite case is the inequality 2^n>n.

More information

Here is a link to a survey article by Claude Tardif, (2008), “Hedetniemi’s conjecture, 40 years later” .

A few more thing worth knowing:

1) The weak version of the conjecture that asserts that If \chi (G)= \chi (H))=n, then \chi (G \times H) \ge f(n) where f(n) tends to infinity with n is still open.

2)  Xuding Zhu proved in 2011 that the fractional version of the conjecture is correct,

3) The directed version of the conjecture was known to be false (Poljak and Rodl, 1981).

4) The conjecture is part of a rich and beautiful theory of graph homomorphisms (and the category of graphs) that I hope to come back to in another post.

Posted in Combinatorics, Open problems, Updates | Tagged , | 15 Comments

Answer to TYI 37: Arithmetic Progressions in 3D Brownian Motion

Consider a Brownian motion in three dimensional space. We asked (TYI 37) What is the largest number of points on the path described by the motion which form an arithmetic progression? (Namely, x_1,x_2, x_t, so that all x_{i+1}-x_i are equal.)

Here is what you voted for

TYI37 poll: Final-results

Analysis of the poll results:  Almost surely 2 is the winner with 30.14% of the 209 votes, and almost surely infinity (28.71%) comes close at second place. In the  third place is  almost surely 3 (14.83%),  and then comes positive probability for each integer (13.4%), almost surely 5 (5.26%),  almost surely 6 (2.87%), and  almost surely 4 (2.39%).

Test your political intuition: which coalition is going to be formed?

Almost surely 2 (briefly AS2) and almost surely infinity (ASI) can form a government  with no need for a larger coalition. But they represent two political extremes. Is AS3 politically closer to AS2 or to ASI? “k with probability p_k for every k>2” (briefly, COM) represent a complicated political massage. Is it closer to AS2 or to ASI? (See the old posts on which coalition will be formed.)

 

TYI37 poll: Partial results. It was exciting to see how the standing of the answers changed in the process of counting the votes.

And the correct answer is: Continue reading

Posted in Combinatorics, Open discussion, Probability | Tagged , , | 1 Comment

The last paper of Catherine Rényi and Alfréd Rényi: Counting k-Trees

A k-tree is a graph obtained as follows: A clique with k vertices is a k-tree. A k-tree with n+1 vertices is obtained from a k-tree with n-vertices by adding a new vertex and connecting it to all vertices of a  k-clique. There is a beautiful formula by Beineke and Pippert (1969) for the number of k-trees with n labelled vertices. Their number is

{{n} \choose {k}}(k(n-k)+1)^{n-k-2}.

If we count rooted k-trees where the root is a k-clique the formula becomes somewhat simpler.

(k(n-k)+1)^{n-k-1}.

In 1972, when I was a teenage undergraduate student I was very interested in various extensions of Cayley’s formula for counting labeled trees. I thought about the question of finding a Prüfer code for k-trees and  how to extend the results by Beineke and  Pippert when  for every clique of size k-1 in the k-tree we specify its “degree”, namely, the number of k-cliques containing it. (I will come back to the mathematics at the end of the post.) I thank Miki Simonovits for the photos and description and very helpful comments.

Above, Kató Renyi, Paul Turan, Vera Sós, and Paul Erdős ; below Kató, Vera, and Lea Schönheim. Pictures: Jochanan (Janos) Schönheim.

 

 

renyi-turan-erdos

From right, Rényi, Turán and Erdős and Grätzer. 

 

While I was working on enumeration of k-trees I came across  a paper by Catherine Rényi and Alfréd Rényi that did everything I intended to do and quite a bit more.

What caught my eye was a heartbreaking footnote: when the paper was completed Catherine Rényi was no longer alive.

The proceedings where the paper appeared were of a conference in combinatorics in Hungary in 1969. This was the first international conference in combinatorics that took place in Hungary.  The list of speakers consists of the best combinatorialists in the world and many young people including Laci Lovasz, Laci Babai, Endre Szemeredi, and many more who since then have become world-class  scientists.

Years later Vera Sós told me the story of Alfréd Rényi’s lecture at this conference, the first international conference in combinatorics that took place in Hungary:  “Kató died on August 23, on the day of arrival of the conference on “Combinatorial Theory and its Applications” (Balatonfured, August 24-29). Alfréd Renyi gave his talk (with the same title as the paper) on August 27 and his talk was longer than initially scheduled.  They proved the results in the paper just the week before the conference. The paper appeared in the proceedings  of the conference.”

Alfréd Renyi was one of the organizers of the conference and also served as one of the editors of the proceedings of the conference, which appeared in 1970. A few months after the conference, on February 1, 1970 Alfréd Rényi  died of a violent illness. The proceedings are dedicated to the memory of Catherine Rényi and Alfréd Rényi.

 

Two pictures showing Alfréd and Catherine Rényi and a picture of Alfred Rényi and Paul Erdős.

 

Repeating a picture from last-week post. From left: Sándor Szalai,  Catherine Rényi, Alfréd Rényi, András Hajnal and Paul Erdős (Matrahaza)

Going back to my story. I was 17 at the time and naturally I wondered if counting trees and similar things is what I want to do in my life. Shortly afterwards I went to the army. Without belittling the excitement of the army I quickly reached the conclusion that I prefer to count trees and to do similar things. My first result as a PhD student was another high dimensional extension of Cayley’s formula (mentioned in this post and a few subsequent posts).  The question of how to generalize both formulas for k-trees and for my hypertrees is still an open problem. We know the objects we want to count,  we know what the outcome should be, and we know that we can cheat and use weighted counting, but still I don’t know how to make it work.

Some more comments on k-trees:

  1. Regarding the degree sequences for k-trees. You cannot specify the actual (k-2)-faces because those (in fact just the graph) determines the k-tree completely. So you need to count rooted k-trees and to specify the (k-2)-faces in terms of how they “grew” from the root.
  2. The case that all degrees are 1 and 2 that correspond to paths for ordinary trees and to triangulating polygons with diagonals for 2-trees are precisely the stacked (k-1)-dimensional polytopes. This is a special case of the Renyi & Renyi formula that was also  found, with a different proof, by Beineke and Pippert.
  3. It is  unlikely that there would be a matrix-tree formula for k-trees since telling  if a graph contains a 2-tree  is known to be NP complete. See this MO question. Maybe some matrix-tree formulas are available when we start with special classes of graphs.
  4. Regarding the general objects – those are simplicial complexes that are Cohen-Macaulay and their dual (blocker) is also Cohen-Macaulay.

This post is just about a single paper of Catherine Rényi and Alfréd Rényi mainly through my eyes from 45 years ago. Catherine Rényi’s  main interest originally was  Number theory, she was a student of Turàn, and soon she became  interested in the theory of Complex Analytic Functions. Alfréd Rényi was a student of Frigyes Riesz and he is known for many contributions in number theory, graph theory and combinatorics and primarily in probability theory.  Alfréd Rényi wrote several papers about enumeration of trees, and this joint paper was Catherine Rényi ‘s first paper on this topic.

Posted in Combinatorics, People | Tagged , , | 7 Comments

Are Natural Mathematical Problems Bad Problems?

One unique aspect of the conference “Visions in Mathematics Towards 2000” (see the previous post) was that there were several discussion sessions where speakers and other participants presented some thoughts about mathematics (or some specific areas), discussed and argued.  In the lectures themselves you could also see a large amount of audience participation and discussions which was very nice.

Let me draw your attention to  one question raised and discussed in one of the discussion sessions.

3.4 Discussion on Geometry with introduction by M. Gromov

Now, lets skip a lot of interesting staff and move to minute 23:20 where Noga Alon asked Misha Gromov to elaborate a statement from his opening lecture of the conference that  the densest packing problem in R^3 is not interesting.  In what follows Misha Gromov passionately argued that natural problems are bad problems (or are even stupid questions), and a lovely discussion emerged (in 25:00 Yuval Neeman commented about cosmology in response to Connes’s earlier remarks but then around 27:00 Vitali asked Misha to name some bad problems in geometry and the discussion resumed.) Misha made several lovely provocative further comments: he rejected the claim that this is a matter of taste, and argued that people make conjectures when they absolutely have no right to do so.

Misha argues passionately that natural problems are stupid problems

Actually one problem that Misha mentioned in his lecture as interesting (see also Gromov’s proceedings paper Spaces and questions), and that was raised both by him and by me is to prove an exponential upper bound for the number of simplicial 3-spheres with n facets. I remember that we talked about it in the conference and Misha was certain that the problem could be solved for shellable spheres while I was confident that the case of shellable spheres would be as hard as the general case.  He was right! This goes back to works of physicists Durhuus and Jonsson see this paper On locally constructible spheres and balls by Bruno Benedetti and  Günter M. Ziegler.

(Disclaimer: I asked quite a few questions that were both unnatural and stupid and made several conjectures when I had no right to do so.)

Continue reading

Posted in Combinatorics, Conferences, Open discussion, What is Mathematics | Tagged | 1 Comment

An Invitation to a Conference: Visions in Mathematics towards 2000

Let me invite you to a conference. The conference took place in 1999 but only recently the 57 videos of the lectures and the discussion sessions are publicly available. (I thank Vitali Milman for telling me about it.) One novel idea of Vitali Milman was to hold discussion sessions and they were quite interesting. (But, I am biased, I like discussions.) I will invite you to one of the heated discussions in the next post. There were very many nice talks and very many nice visions. And it is fun to watch the videos and judge the ideas in the perspective of time.

The proceedings appeared as GAFA special volumes, but alas the articles are not electronically available even to GAFA’s subscribers. Let me encourage both Birkhauser and the contributors to make them more available. My talk was: An invitation to Tverberg’s theorem, and my own contribution to the Proceedings Combinatorics with a Geometric Flavor is probably the widest scope survey article I ever wrote.  At the end of each section I added a brief philosophical thought about mathematics and those are collected in the post “about mathematics“.

Two more things: The conference (and few others organized by Vitali) was  in Tel Aviv with a few days at the dead see and this worked very nicely.  Vitali also organized in the mid 90s another very successful geometry conference unofficially celebrating Gromov’s 50th birthday with, among others, a very nice lecture by Gregory Perelman. If videos will become available I will be delighted to invite you to that conference as well. Update from Vitali: It was also the week of Jeff Cheeger’s 50th birthday which was also celebrated. Grisha Perelman gave an absolutely excellent talk  talk on works of Cheeger.  Lectures were not videotaped.

Avi Wigderson’s lecture

Are so called “natural questions” good for mathematics. Specifically is Kepler’s questions about the densest packing of unit balls in 3-space interesting? Watch a discussion of Misha Gromov, Noga Alon, Laci Lovasz and others. (next post)

We were all so much younger!  (And in that old millennium,  we were also all men 😦 )

Misha Gromov argues passionately that natural problems are bad problems (see next post)

Pictures of most participants ad two slides are below

Continue reading

Posted in Conferences, What is Mathematics | Tagged | 1 Comment

The (Random) Matrix and more

Three pictures, and a few related links.

Van Vu

Spoiler: In one of the most intense scenes, the protagonist, with his bare hands and against all odds, took care of the mighty Wigner semi-circle law in two different ways. (From VV’s FB)

More information on Van Vu’s series of lectures. Van Vu’s home page; Related posts: did physicists really just prove that the universe is not a computer simulation—that we can’t be living in the Matrix? (Shtetl-Optimized); A related 2012 post on What’s New;

Two more pictures the first also from FB Continue reading

Posted in Combinatorics, People, What is Mathematics | Tagged , , , , , , | 1 Comment

Gothenburg, Stockholm, Lancaster, Mitzpe Ramon, and Israeli Election Day 2019

Lancaster – Watching the outcomes of the Israeli elections (photo: Andrey Kupavskii)

Sweden

I just came back from a trip to Sweden and the U.K. I was invited to Gothenburg to be the opponent for a Ph. D. Candidate  Malin Palö Forsström (by now Dr. Malin Palö Forsström),  who wrote her excellent Ph. D. thesis under the supervision of Jeff Steif in Chalmers University. We also used the opportunity for a lovely mini-mini-workshop

From Gothenburg I took the train to Stockholm to spend the weekend with Anders Björner and we talked about some old projects regarding algebraic shifting.  We had dinner with several colleagues including Svante Linusson who is a candidate for the European parliament!

Stockholm: With Anders and Cristins in the late 80s (left, I think this was also when I was an opponent), Svante Linusson ten days ago (right)

The United Kingdom

The British Mathematical Colloquium at Lancaster was a lovely 4-day general meeting, an opportunity to meet some old and new friends (and Internet MO friend Yemon Choi in real life), and to learn about various new developments. I am aware of the fact that my list of unfulfilled promises is longer than those of most politicians, but I do hope to come back to some mathematics from this trip to Sweden and to Lancaster.

Election Day

Last week’s Tuesday was election day in Israel,  and as much as I like to participate (and to devote a post to election day here on the blog – in 2009, 2012, and 2015) I had to miss the election, for the first time since 1985. (I still tried to follow the outcomes in real time.)

The Negev, Israel

And we are now spending a three-day vacation and doing some mild hiking in Mitzpe Ramon, in the Negev, the Israeli desert.  The view around here is spectacular. I first fell in love with the sights of the Negev when I spent six months here when I was 19 (in the army). Since then we have been caming here many times over the years, and in 2002 the annual meeting of the Israeli Mathematical Union took place here, in the same hotel.

 

Ein Ovdat (left). The 2002 Annual meeting of the IMU (right). A large number of Israeli mathematicians come to a substantial fraction of these annual events.

The stance of the main Israeli parties on quantum computing

One anecdote about the Israeli election is that both major political parties of Israel, the Likud, led by Benjamin (Bibi) Netanyahu that won 35 seats in the parliament and will probably lead the coalition, and the newly formed “Blue-and-White” party, led by Benny (Benjamin) Gantz that also won 35 seats and will probably lead the opposition, stand behind quantum computing! 🙂

Left – A paragraph from “Blue and White’s” charter with a pledge to quantum computing (I thank Noam Lifshitz for telling me about it). Right –  a news item (click for the article) about the quantum computing vision of Netanyahu and the Likud party.

 

Posted in Combinatorics, Probability, Updates | 1 Comment

Is it Legitimate/Ethical for Google to close Google+?

Update April 2, 2019: the links below are not working anymore. 

Google Plus is a nice social platform with tens of millions participants. I found it especially nice for scientific posts, e.g. by John Baez, Moshe Vardi, or about symplectic geometry,  about Majorana Fermions, and with a discussion about What is combinatorics. A few months ago Google announced  that Google+ will be closed. This is going to happen today (March 31, 2019) in a few hours. For example, I am not even sure if the above valuable links will continue to operate. (Every individual user can get his own stuff.)

For possible answers on why Google shut down Google Plus see this Quora question.

My question is different. Is it legitimate for Google to close Google+? Is it legitimate and is it ethical for Google to eliminate existing content from the public domain? 

Let me state clearly my opinion:

Google has strong ethical/moral obligation to maintain at least for several years public access to all Google+ existing material.

The fact that huge content that millions of people spent time and effort creating and that people spent time and effort to search and find, is deleted — by a huge and successful company — is very problematic

 

(Related post: What do firms want .)

Posted in Economics, Open discussion, Rationality | Tagged | 11 Comments