Greetings from Oberwolfach from a great conference on algebraic, geometric, and topological combinatorics. Stay tuned for more pictures and updates from Oberwolfach and CERN, and also in case you did not see it already here is the link to the previous post with the sunflower news. And towards the end of this post a connection to Saint-Exupéry’s “Le Petit Prince”.

Here is the abstract: We prove that the total positive Gauss-Kronecker curvature of any closed hypersurface embedded in a complete simply connected manifold of nonpositive curvature $latex M^n, n\ge 2$, is bounded below by the volume of the unit sphere in Euclidean space $latex R^n$. This yields the optimal isoperimetric inequality for bounded regions of finite perimeter in M, via Kleiner’s variational approach, and thus settles the Cartan-Hadamard conjecture. The proof employs a comparison formula for total curvature of level sets in Riemannian manifolds, and estimates for smooth approximation of the signed distance function. Immediate applications include sharp extensions of the Faber-Krahn and Sobolev inequalities to manifolds of nonpositive curvature.

The proof is quite involved (the paper is 80 pages long) and is based on extending Kleiner’s approch for the 3- and 4- dimensional case. Or Hershkovich raised on FB an even more general question related to isospectral relations based on higher homology.

WOW! The new paper https://arxiv.org/abs/1908.08483 improved bounds for the sunflower lemma gives the most dramatic progress on the sunflower conjecture since it was asked. Congratulations to Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang.

(Written on my smartphone will expand it when reconnected to my laptop.) (Reconnected) Rather, I will write about it again in a few weeks. Let me mention now that while the old difficult and ingenious improvements stayed in the neighborhood of Erdos and Rado initial upper bound the new result is in the neighborhood of the conjecture! (And is tight for a certain robust version of the problem!)

Let me also mention that we discussed the sunflower conjecture here many times and polymath10 (wiki page, first post, last post) was devoted to the problem.)

Update: Let me mention an important progress on the sunflower conjecture from 2018 by Junichiro Fukuyama in his paper Improved Bound on Sets Including No Sunflower with Three Petals. I missed Fukuyama’s paper at the time and I thank Sasha Kostochka and Andrew Thomason for telling me about it now.

Let me announce my CERN colloquium this Thursday, August 22, 2019, 16:30-17:30 entitled “The argument against quantum computers.” If you are at CERN or the neighborhood, please please come to the lecture. (Tea and coffee will be served at 16:00. ) If you are further away, there is a live broadcast.

A few weeks ago I uploaded to the arXive a new paper with the same title “The argument against quantum computers“. The paper will appear in the volume: Quantum, Probability, Logic: Itamar Pitowsky’s Work and Influence, Springer, Nature (2019), edited by Meir Hemmo and Orly Shenker. A short abstract for the lecture and the paper is:

We give a computational complexity argument against the feasibility of quantum computers. We identify a very low complexity class of probability distributions described by noisy intermediate-scale quantum computers, and explain why it will allow neither good-quality quantum error-correction nor a demonstration of “quantum supremacy.” Some general principles governing the behavior of noisy quantum systems are derived.

A slide from a lecture by Scott Aaronson where he explains why soap bubble computers cannot solve the NP-complete Steiner-tree problem. Noisy intermediate scale quantum (NISQ) circuits are computationally much more primitive than Scott’s soap bubble computers and this will prevent them from achieving neither “quantum supremacy” nor good quality quantum error correcting codes. (source for the picture)

Low-entropy quantum states give probability distributions described by low degree polynomials, and very low-entropy quantum states give chaotic behavior. Higher entropy enables classical information.

Today I would like to report about some breakthroughs in the area of combinatorics, and about blog posts in Yufei Zhao’s blog that describe these remarkable results (better than I can). Many of the coauthors in these breakthroughs are undergraduate students.

A collection of equiangular lines is a collection of lines so that the angles between every pair of lines in the same?

Here are two classical questions:

What is the maximum number of equiangular lines in ?

Given an angle what is the maximum number of equiangular lines in ? so that the angle between every two lines is

In 2000 Dom de Caen found for the first time an equiangular set of lines in space of size . (The crucial observation that one of the graphs in the Cameron–Seidel association scheme has a certain eigenvalue of large multiplicity. Prior to this construction, the largest sets had sizes of order . In de Caen’s example the lines have angles approaching 90 degrees, and question 2 for a fixed value of led to very different bounds. (For another result by Dom, see this post.)

There were some important progress on this problem by Igor Balla, Felix Dräxler, Peter Keevash, and Benny Sudakov, as featured in this Quanta Magazine article written by Kevin Hartnett. Zilin, Jonathan, Yuan, Shengtong, and Yufei finished off the problem in a clean and crisp manner, in a 10-page paper with a self-contained proof. On the way they proved the following very interesting theorem.

Theorem: A bounded degree graph must have sublinear second eigenvalue multiplicity.

Abstract: We prove a conjecture of Fox, Huang, and Lee that characterizes directed graphs that have constant density in all tournaments: they are disjoint unions of trees that are each constructed in a certain recursive way.

“Constant density in all tournaments” means that for some (and hence for all , every tournament with vertices has the same number of copies of . (On the nose!)

This result is related to the famous Sidorenko’s conjecture. Let me copy its description from the paper:

For undirected graphs, conjectures of Sidorenko and Erdős–Simonovits (commonly referred to as Sidorenko’s conjecture) say that for every bipartite graph , the -density in a graph of fixed density is minimized asymptotically by a random graph. Lately the conjecture has been proved for many families of though the conjecture remains open in general. In particular, the case is open.

Yufei Zhao

More

Let me describe briefly three additional posts on Yufei’s blog with two results from 2018 and one result from 2014.

These are two remarkable papers by the same team of researchers. The paper on the number of independent sets in a regular graph settled a famous 2001 conjecture by Jeff Kahn. An earlier breakthrough on the problem was made by Zhao in 2009 when he was an undergraduate student.

Recently I wrote a post Matan Harel, Frank Mousset, and Wojciech Samotij and the “the infamous upper tail” problem describing a major breakthrough on the infamous upper tail problem. Over the years I heard a lot of lectures and private explanation on upper tails and the remarkable related mathematics. I remember lectures by Kim and Vu from the early 2000’s and by Varadhan from ICM 2010 describing (among other things) the fundamental paper by Chatterjee and Varadhan, and later works by DeMarco and Kahn, and by Chatterjee and Dembo and Lubetzky and Zhao and others. But when I wrote the post I realized my knowledge is too sparse for giving a thorough description, and I decided not to wait and write a short post. This post by Yufei describes some of the history very nicely as well as the major papers by Eyal and Yufei from 2012 and 2014.

I am very happy to announce two quantum events. First, I would like to announce a course “Computation, quantization, symplectic geometry, and information” in the first 2019/2020 semester at the Hebrew University of Jerusalem (HUJI). The course will by on Sundays 14:00-16:00. Second, I would also like to announce The 4th Advanced School in Computer Science and Engineering on The Mathematics of Quantum Computation on December 15 – December 19, 2019, at IIAS HUJI.

Emmy Noether (left) Grete Hermann (right)

A quantum “Kazhdan’s seminar” at HUJI: Computation, quantization, symplectic geometry, and information.

“In the fall of 2019 Dorit Aharonov, Gil Kalai, Guy Kindler and Leonid Polterovich intend to run a new one semester course (as a Kazhdan seminar) attempting to connect questions about noise and complexity in quantum computation, with ideas and methods about “classical-quantum correspondence”.that are well studied in symplectic geometry. The course will be highly research-oriented, and will attempt to teach the basics in both areas, and define and clarify the interesting research questions related to the connections between these areas, with the hope that this will lead to interesting insights. The course is oriented to grad students (and faculty), with reasonable background in mathematics, and with interest in the connections between mathematical and computational aspects of quantum mechanics. (See below for a full description.)”

The course will by on Sundays 14:00-16:00 in Ross building.

“We will be organizing a math-oriented quantum computation school in the IIAS at the Hebrew university. No prior knowledge on quantum will be assumed. The school will introduce TCS and math students and faculty, who are interested in the more mathematical side of the area, to the beautiful and fascinating mathematical open questions in quantum computation, starting from scratch. We hope to reach a point where participants gain initial tools and basic perspective to start working in this area. (See below for a full description.)

Organizers: Dorit Aharonov, Zvika Brakerski, Or Sattath, Amnon Ta-Shma,

Main (confirmed) Speakers: Sergey Bravyi, Matthias Christandl, Sandy Irani, Avishay Tal, Thomas Vidick, (1-2 additional speakers may be added later).

Additional (confirmed) lectures will be given by: Dorit Aharonov, Zvika Brakerski, and/ Or Sattath. (1-2 additional speakers may be added later).”

The Isreali Institute of Advanced Study hosted already a 2014 school about quantum information as part of its legendary physics series of schools, and also hosted QSTART in 2013.

The cover of Avi Wigderson’s book “Mathematics and computation” as was first exposed to the public in Avi’s Knuth Prize videotaped lecture. (I had trouble with 3 of the words: What is EGDE L WONK 0? what is GCAAG?GTAACTC ? TACGTTC ? I only figured out the first one.)

One main theme of the book is the rich connection between the theory of computing and other areas (in fact, most areas) of mathematics. See also this self contained survey (based on Chapter 13 of the book) by Avi Interactions of Computational Complexity Theory and Mathematics, which in 27 pages overviews relations to number theory, Geometry, Operator Theory, Metric Geometry, Group Theory, Statistical Physics, Analysis and Probability, Lattice Theory and Invariant Theory. Of course, over the last four decades, Avi himself has been among the main heroes in finding many paths between mathematics and the theory of computing.

Another theme of the book and of several talks by Avi is that the theory of computing has revolutionary connections with many fields of science and technology. Again, this theme is present in the entire book and is emphasized in Chapter 20, which also appeared as a self contained paper “On the nature of the Theory of Computation (ToC).” Let me quote one sentence from Avi’s book that I propose for discussion. (For the complete quote see the end of the post.)

The intrinsic study of computation transcends human-made artifacts, and its expanding connections and interactions with all sciences, integrating computational modeling, algorithms, and complexity into theories of nature and society, marks a new scientific revolution!

Of course, similar ideas were also expressed by several other prominent scientists, and let me mention Bernard Chazelle’s essay: The Algorithm: Idiom of Modern Science. (Feel free to give further examples and links in the comment section.)

Let’s discuss: Integrating computational modeling, algorithms, and complexity into theories of nature, marks a new scientific revolution!

I propose to discuss in the comment section the idea that the theory of computing offers a scientific revolution. Very nice cases to examine are the computational study of randomness and connections to statistics, connections with economy and connections with biology. Comments on the relations between the theory of computation and other areas of mathematics are also very welcome.

Avi’s concluding slide compared these three great theories of human understanding.

Update: and here is a great interview of Noga in English and the interviewer is Narkis Alon, Noga’s youngest daughter and Amalya Duek.

I was very happy to interview my academic doctoral twin and long-time friend Noga Alon. The interview is an initiative of the Israel Academy of Sciences and Humanities. (This is my second interview of this kind. See here for an interview with Yisrael Aumann.) The interview is in Hebrew. (Update: Automatically-produced English subtitles are available.)

For our English speaking readers here is a recent Numberphile video with Noga.

We agreed in advance that most of the interview would be about mathematics, and most of the time we courageously (and perhaps somewhat recklessly) tried to explain to a large audience (starting from scratch) some of Noga’s research directions and results. We hope that people will enjoy the beauty of it even with the missing details and background.

Noga’s parents, family and childhood

In the first part of the interview Noga talked about his family, his parents, Dror and Hemda, his great uncle Yigal Alon, his early childhood, and his early interest in mathematics. Noga liked to solve mathematical riddles from a young age. One reason Noga was drawn to mathematics is that unlike other topics, in mathematics there are absolute truths, and a mathematical proof (when such exists) is perhaps the only way you can settle a debate. Noga gave an amusing example from his youth regarding the Eurovision song context. Then he mentioned the Hebrew Reali school in Haifa, a mathematics teacher there, Yaakov Kaplan, newly immigrated from the former Soviet Union, who greatly influenced Noga. Noga also talked about his participation in the Israeli Mathematical Olympiad where the two of us first met 45 years ago. Next, the two of us met during our military service, and in parallel to his service, Noga finished his M. Sc. and Ph. D with Micha A. Perles, who was also my supervisor.

An hour of mathematics

The mathematical part of the video starts with Noga’s overview of combinatorics. Then we moved to specific topics.

(22:40- 33:30) Noga’s negative solution to Shannon’s conjecture about the capacity of two graphs (and a little about Claude Shannon and information theory)

(33:30- 40:25) The combinatorial nullstellensatz and the polynomial method and a little about the game SET

(40:25 – 46:50) The probabilistic method and a little on the history of probability and about Paul Erdos.

(46:50- 54:50) Streaming algorithms, a topic introduced by Noga Alon, Yossi Matias, and Mario Szegedy, and more generally, about positive and negative results in computer science, and their practical applications.

(54:50 – 59:25) Expander graphs and “spectroscopy of graphs”

59:25 -1:05:40 Ramsey theory

1:05:40-1:12:20 Factoring integers with quantum computers and with classical methods

1:12:00-1:20:00 Combinatorics, economics and game theory: Noga’s theorem that large committees require a large budget!

Going back from mathematics to life itself

After a full hour of mathematics, we returned to life itself. Memories from our years as postdocs at MIT, and our 1993 conference in Jerusalem. Noga talked a little about women in science and in society, about his three daughters, about the possibility that science, like sport, can bridge different groups and different peoples, and about politics and prospects for better relations with our Arab neighbors and Iran (Noga is somewhat optimistic and so am I), prospects about getting old (we are hopeful about it), and advice to young researchers. Noga’s message at the end was that there are many paths to mathematical research and he encouraged young people that like mathematics to follow and enjoy them.

There is a class of children that have just finished elementary school. Now they all move from elementary school to high school and classes are reshuffled. Each child lists three friends, and the assignment of children into classes ensures that each child will have at least one of these three friends in his class.

One of the children heard from five of his schoolmates that they found that they can make their selections in a way that will ensure that all five will be assigned to the same class!

Test your intuition: Is there a strategy for five of the children that will ensure that all five will be assigned to the same class?

Can a larger group of children coordinate their choices to ensure that they will all necessarily be assigned to the same class?

Suppose that X is a bounded-degree polynomial with nonnegative coefficients on the p-biased discrete hypercube. Our main result gives sharp estimates on the logarithmic upper tail probability of X whenever an associated extremal problem satisfies a certain entropic stability property. We apply this result to solve two long-standing open problems in probabilistic combinatorics: the upper tail problem for the number of arithmetic progressions of a fixed length in the p-random subset of the integers and the upper tail problem for the number of cliques of a fixed size in the random graph . We also make significant progress on the upper tail problem for the number of copies of a fixed regular graph H in To accommodate readers who are interested in learning the basic method, we include a short, self-contained solution to the upper tail problem for the number of triangles in for all p=p(n) satisfying .

The introduction does a very nice job of presenting the rich history of the problem. Here is a 2002 paper by Svante Janson and Andrzej Ruciński on the infamous upper tail. (And a lot has happened since then with regard to this problem and on non linear large deviation theory). Following, there is a lovely section with a short solution for the case of triangles.

Forthcoming reference [48] talks about lower tails! Stay tuned!

A tweet-long summary: The cyclic polytope is wonderful and whenever we construct an analogous object we are happy. Examples: Neighborly cubic polytopes; The amplituhedron; and as of last week, the Novik-Zheng new construction of neighborly centrally symmetric spheres!

In 1995, Jockusch constructed an infinite family of centrally symmetric 3-dimensional simplicial spheres that are cs-2-neighborly. Here we generalize his construction and show that for all d ≥ 4 and n ≥ d, there exists a centrally symmetric (d − 1)-dimensional simplicial sphere with 2n vertices that is cs-[d/2]-neighborly. This result combined with work of Adin and Stanley completely resolves the upper bound problem for centrally symmetric simplicial spheres.

Congratulations to Isabella and Hailun!

Some background to the Novik and Zheng breakthrough

Centrally symmetric bodies: A centrally symmetric (cs) polytope convex body in satisfies implies . Centrally symmetric bodies are the unit balls of normed spaces.

Centrally symmetric simplicial spheres: A triangulation of a -dimensional sphere with a set of vertices is centrally symmetric if there is an involution on that maps a face of to a face of and for every vertex , and is not an edge of . The boundary complex of a cs -polytopes is a cs triangulation of .

Neighborliness. A simplicial complex is -neighborly of every set of vertices of form a face. (The definition was first considered for simplicial -polytopes .) The cyclic -polytope with vertices is -neighborly. (The only (+1)-neighborly simplicial -sphere is the simplex. There are many other -neighborly simplicial -polytopes and -spheres.

cs-Neighborliness. Let be a simplicial complex with an involution on its vertices which acts on (maps faces to faces) and has the property that is not adjacent to (and ). We will call and antipodal. is cs--neighborly if every set of vertices that contains no pair of antipodal vertices is a face of . The only cs--neighborly simplicial sphere is the boundary complex of the cross polytope.

The existence of cs--neighborly spheres. It was an important open question whether cs -neighborly simplicial spheres exist. (The only cs--neighborly spheres is the boundary complex of the cross polytope.) The first example (which is not a cross polytope) was given by Grünbaum in 1969 in his paper “The importance of being straight(?).” In 1995 Jockusch constructed an infinite family cs-2-neighborly centrally symmetric 3-dimensional simplicial spheres. This problem has now been solved by Novik and Zheng.

Neighborly centrally symmetric polytopes. In the 1960s Grünbaum noted the big difference between neighborly centrally symmetric spheres and centrally symmetric polytopes. He proved (This is Theorem 4.1 in his book “Convex polytopes”) that no cs-2-neighborly 4 polytope with 12 vertices exists. This is an example of the important themes of “straightening” or “linearizing” combimatorial objects and of extending theorems from the “straight” or “linear” case to more general combinatorial settings.)

This result by Grünbaum was extended in various directions. Let me mention two major results in the field:

Theorem McMullen and Shephard (1968): A cs d-dimensional polytope with 2(d + 2) vertices cannot be more than cs-⌊(d + 1)/3⌋-neighborly.

Novik (2017) constructed cs-2-neighborly d polytopes with vertices. She used a 2017 breakthrough construction by Gerencsér–Harang of an acute set of size in . (A set S is acute if every three points from S determine an acute triangle.)

Face numbers of centrally-symmetric polytopes and spheres. As the abstract asserts the new construction is related to questions about face numbers of centrally symmetric polytopes, spheres and other cellular objects. In fact, this was the next item in our planned posts on algebraic combinatorics of cellular objects. (The first and only post so far is here.) Here is a recent survey by Isabella Novik A tale on centrally symmetric polytopes and spheres.

Upper bound theorems. Neighborly polytopes and spheres are the equality cases of the upper bound theorem (proved by McMullen for polytopes and by Stanley for spheres). A version of the upper bound inequality for centrally symmetric spheres was proved by Adin and Stanley and the new construction shows that the Adin-Stanley inequality is tight. For more on the upper bound theorem and neighborliness see Section 2 of my 2000 survey Combinatorics with geometric flavor. See also the post How the g-conjecture came about and the post Richard Stanley: How the Proof of the Upper Bound Theorem (for spheres) was Found.