I was very sad to hear that Jean Bourgain, among the greatest mathematicians of our time, and a dear friend, passed away. I first met Jean about forty years ago and later we have become friends and collaborators. In the 80s and 90s Jean used to visit Israel quite often and had close collaboration with the Banach space Israeli community, and with the Ergodic theory community, and with the Harmonic analysis community, and the PDE community, and later also with the combinatorics, probability, algebra, number theory, and theoretical computer science communities. I always admired his immense mathematical powers and his deep devotion to mathematics.
My 2016 lecture “Questions for Jean Bourgain” about questions that I (and some colleagues) asked Jean Bourgain over the years, mainly in the areas of combinatorics and combinatorial aspects of convexity.
Abstract: Consider a simplicial complex that allows for an embedding into . How many faces of dimension or higher can it have? How dense can they be?
This basic question goes back to Descartes. Using it and other fundamental combinatorial
problems, we will introduce a version of the Kähler package beyond positivity,
allowing us to prove the Lefschetz theorem for toric varieties even when the ample
cone is empty. A particular focus lies on replacing the Hodge-Riemann relations by a
non-degeneracy relation at torus-invariant subspaces, allowing us to state and prove a
generalization of the theorems of Hall and Laman in the setting of toric varieties. Of
the many applications, we highlight two main applications, one because it is the most
well-known, the other because it provided the most guiding light.
(1) We fully characterize the possible face numbers of simplicial spheres, resolving the
so called g-conjecture of McMullen in full generality and generalizing Stanley’s
earlier proof for simplicial polytopes.
(2) We prove that for a simplicial complex K that embeds into , the number of d-dimensional simplices exceeds the number of (d − 1)-dimensional simplices by a factor of at most d + 2. This generalizes a result of Descartes, and resolves the Grünbaum-Kalai-Sarkaria conjecture.
_______
(GK:) A few further comments. Probably the g-conjecture for spheres is the single problem I knock my head against the most. It is great to see it settled and it is even greater to see it settled by my friend and colleague Karim Adiprasito.
To the three ingredients of the standard conjectures (See also the previous post), Poincare duality (PD), Hard Lefschetz (HL) and Hodge-Riemann (HR), Karim adds the Hall-Laman relations. Very roughly, the Hall-Laman relations substitute (HR) and apply genericity (rather than definiteness) toward (HL).
(We still need a good acronym for Hall-Laman, maybe (AHL).)
One very nice feature of Karim’s proof is that vertex decomposable spheres play a special role in the path toward the proof. Those were introduced by Provan and Billera in the context of the Hirsch conjecture.
This is my fourth report from ICM2018. (I plan one more.) As I already mentioned, Combinatorics was very nicely represented at ICM2018. The combinatorics session itself was great, and there were quite a few other sessions and other lectures related to combinatorics. I also met quite a few combinatorialists. As I mentioned in my ICM 2010 post, one thing that I enjoyed was to unexpectedly meet some old friends and this also happened in Rio (maybe a little less compared to Hyderabad as I learned to expect the unexpected). I also had an irrational expectation to unexpectedly meet the same people that I met unexpectedly in India. It was a pleasure meeting Tadeusz Januszkiewicz again but I was irrationally disappointed not to bump again into Oriol Serra and Anna Llado whom I had met by surprise in Hyderabad.
The Monday afternoon combinatorics session featured three lectures that knocked my socks off. The talks were great and I was in a perfect position to enjoy them as I knew something about the problems and some related results and yet each lecture surprised me. The three talks were Combinatorial applications of the Hodge–Riemann relationsby June Huh, The method of hypergraph containers by József Balogh & Robert Morris, Asymptotic enumeration of graphs with given degree sequence by Nicholas Wormald. Bella Bollobas chaired the session and gave a very nice and thoughtful introduction to each of the four speakers.
June Huh, and the Lefschetz package in combinatorics
June Huh: The standard conjectures are both ubiquitous and fundamental
June Huh talked about a mysterious package of conjectures (PD), (HL) and (HR), referred to as the standard conjectures, for certain algebras associated with geometric and combinatorial objects. PD stands for the Poincare Duality, and it asserts that certain vector spaces and are dual. HD stands for Hard Lefschetz and it asserts that certain linear maps from to have the property that their composition from all the way to is an injection. (HR) stands for Hodge Riemann relations. (PD) and (HD) imply that a certain bilinear form is nondegenerate and (HR) is a stronger statement that this form is definite!
June started with some startling applications of the Hard-Lefschetz theorem in combinatorics pioneered by Stanley. He then mentioned a startling new application with Wang: Consider points spanning a -dimensional space. Let be the number of flats of dimension spanned by the point. Motzkin conjectured in 1936 and proved over the reals that . The planar case follows from the classic Erdos deBruijn theorem. Hu and Wang used {HL} to prove , which was conjectured by Dowling and Wilson.
Next came applications of (HR), starting with Huh’s proof of the log concavity of coefficients of chromatic polynomials for graphs (Read conjecture ) and the far-reaching extension by Adiprasito-Huh-Kats to general matroids (Rota’s conjecture). We mentioned the Adiprasito-Huh-Katz solution of the Rota-Heron conjecture in the previous post and in this one.
The container theorem for hypergraphs is one of the most important tools in extremal combinatorics with many applications also to random graphs and hypergraphs, additive combinatorics, discrete geometry, and more.
Rob Morris explained the container theorem for triangle-free graphs. It asserts that there is a collection of graphs on with the following three properties:
(1) Every graph in the collection contains triangles,
(2) The number of graphs in the collection is ,
(3) Each triangle free graph is contained in a graph in the collection.
Rob explained the origins of this theorem, how it follows from a container theorem for 3-uniform hypergraphs, and how the later extends to the very general and important container theorem for -uniform hypergraphs that was achieved in 2012 independently by Saxton and Thomason (Here is the link to their paper), and by Balogh, Morris, and Samotij (Here is a link to their paper).
Jozsef Balogh described two consequences of the container theorem to additive combinatorics and to discrete geometry. Let me describe the result in discrete geometry by Balogh and Solymosi. The (4,3) problem ask for the size $\alpha (n)$ of the largest subset of points in general position (no three on a line) that can always be found in a planar configuration of points with the property that no four points lie on a line. The container method is used to show (surprisingly!) that .
How many -regular graphs are there? This is a very central problem in combinatorics and Nick Wormald was quite interested in its solution ever since his Ph. D. The talk describes the early history of the problem, the early works by Wormald and McKay from the 90s, the recent breakthrough by Antia Liebenau and Nick Wormald, the techniques involved in the old and new proofs and some related results.
A good place to start is with Read’s 1958 formula for the number of 3-regular graphs with n labelled vertices
Following an important model of Bollobas for creating regular graphs, general formulas were developed for low degrees, By McKay, McKay and Wormald, and others that depend on the probability of a random graph in Bollobas’ model to be simple. (See pictures below). Some results were proven also for the high degree regime and McKay and Wormald gave in 1990 and 1997 unified conjectural formulas for the number of -regular graphs for a wide range of parameters. Moreover these conjectures extend to a large range of vectors of degree sequences.
I thank Nati Linial, Dan Spielman and Karim Adiprasito for sharing the news with me.
The Mihail-Vazirani conjecture for matroids and Feder-Mihail’s theorem
Consider a collection of vectors. A basis is a subset of of linearly independent vectors that span the subspace spanned by . We can define a graph whose vertices are all bases and two bases are adjacent if their symmetric difference has two elements. Mihail and Vazirani conjectured that for every set of vertices in this graph the number of edges between to its complement is at least .
If consists of the elements of the standard basis in and their negatives then the graph we obtain is the graph of the discrete dimensional discrete cube and the assertion of the Mihail-Vazirani conjecture is well known.
The Mihail-Vazirani conjecture was formulated (and has now been proved) for arbitrary matroids. Think about a matroid as a collection of subsets (the independent sets of the matroid) of some ground set that closed under taking subsets (hence a simplicial complex) with the following property: For every , the induced simplicial complex on denoted by is pure. In other words, for every , all maximal independent subsets of have the same cardinality.
In a pioneering 1992 paper Tomás Feder and Milena Mihail proved the conjecture for balanced matroids.
Mihail and Vazirani conjecture for 0-1 polytopes.
An even more general conjecture by Mihail and Vazirani is still open. It asserts that for every 0-1 polytope, for every set of vertices, the number of edges between to its complement is at least .
Let me mention another paper by a subset of the authors on related questions, another paper by Brändén and Huh, who independently proved the strong log-concavity of several of the polynomials appeared in the ALOV paper, and are be several forthcoming papers by these two groups.
Here is the abstract: We design an FPRAS to count the number of bases of any matroid given by an independent set oracle, and to estimate the partition function of the random cluster model of any matroid in the regime where 0<q<1. Consequently, we can sample random spanning forests in a graph and (approximately) compute the reliability polynomial of any matroid. We also prove the thirty year old conjecture of Mihail and Vazirani that the bases exchange graph of any matroid has expansion at least 1. One of our key observations is a close connection between pure simplicial complexes and multiaffine homogeneous polynomials. Specifically, if X is a pure simplicial complex with positive weights on its maximal faces, we can associate with X a multiaffine homogeneous polynomial such that the eigenvalues of the localized random walks on X correspond to the eigenvalues of the Hessian of derivatives of .
Spectral negative dependence and Hodge-Riemann
A key paragraph regarding the method is the following:
“Our approach has a close connection to the original plan of Feder and Mihail (1992) who used the negative correlation property of balanced matroids to show that the bases exchange walk mixes rapidly. Unfortunately, most interesting matroids do not satisfy negative correlation. But it was observed [AKH18; HW16; AOV18] that all matroids satisfy a spectral negative dependence property.” AKH18 (a typo, it should be AHK18) is the solution for the Rota-Heron conjecture by Adiprasito, Huh and Katz that relies on the Hodge-Riemann property for matroids that we mentioned in this post. (I still feel in debt for a more detailed blog post about Adiprasito, Huh and Katz’ breakthrough!).”
I think that high dimensional expanders and random walks on them also plays a role in the new development.
Next week Igor Pak will give the 2018 Erdős Lectures (delayed from June)
Here is the poster
Combinatorics — Erdos lecture: Igor Pak (UCLA) “Counting linear extensions”
Monday December 10 11:00-13:00
Location: IIAS Hall 130, Feldman building, Givat Ram
I will survey various known and recent results on counting the number of linear extensions of finite posets. I will emphasize the asymptotic and complexity aspects for special families, where the problem is especially elegant yet remains #P-complete.
CS Theory — Erdős Lecture: Igor Pak (UCLA) “Counting Young tableaux”
Wednesday, Dec. 12, 2018, 10:30am to 12:00pm
Location: Rothberg (CS building) B-220
The number of standard Young tableaux of skew shape is a mesmerizing special case of the number of linear extensions of posets, that is important for applications in representation theory and algebraic geometry. In this case there is a determinant formula, but finding their asymptotics is a difficult challenge. I will survey some of the many beautiful result on the subject, explain some surprising product formulas, connections to Selberg integral, lozenge tilings and certain particle systems.
Colloquium: Erdos lecture – Igor Pak (UCLA) “Counting integer points in polytopes”
Thursday, Dec 13, 2018 2:30pm to 3:30pm
Location: Manchester Building (Hall 2), Hebrew University Jerusalem
Given a convex polytope P, what is the number of integer points in P? This problem is of great interest in combinatorics and discrete geometry, with many important applications ranging from integer programming to statistics. From a computational point of view it is hopeless in any dimensions, as the knapsack problem is a special case. Perhaps surprisingly, in bounded dimension the problem becomes tractable. How far can one go? Can one count points in projections of P, finite intersections of such projections, etc.?
The study of Probabilistically Checkable Proofs, starting with the discovery of the PCP Theorem, is a cornerstone of modern computer science, with impact on complexity theory, algorithms, and cryptography. Born as a purely theoretical notion, mostly used to prove hardness of approximation results, PCPs are now becoming a widely deployed tool in blockchain platforms. The workshop will touch the past, the state of the art, and future of PCPs. Topics will include: hardness of approximation, PCPs in cryptography and blockchains, no-signaling PCPs, PCPs in P, and Boolean function analysis.
Confirmed speakers:
Boaz Barak, Shafi Goldwasser, Eli Ben Sasson, Gil Kalai, Yael Kalai, Guy Kindler, Elchanan Mossel, Christos Papadimitriou, Aviad Rubinstein, Ran Raz, Ronitt Rubinfeld, Oded Schwartz, Irit Dinur, Andrew Yao, and Avi Wigderson.
Organizers:
Nir Bitansky, Esty Kelman, Subhash Khot, Dor Minzer, and Muli Safra
Let me mention two talks with very promising news by friends of the blog, Karim Adiprasito and Noam Lifshitz. As always, with the beginning of the academic year there are a lot of exciting activities, things are rather hectic around, and I hear a lot of exciting things (both news and things I was supposed to know long ago). I am quite sure that we will return to the topics of the two lectures in later posts and I also welcome discussing them in the comment section. (A few related older posts for Karim’s talk and seminar: F ≤ 4E; Beyond the g-conjecture. and for Noam’s seminar: Influence, Threshold and Noise; Boolean functions: Influence, threshold and noise; .)
Karim Adiprasito’s colloquium talks and course
HUJI Thu, 25/10/2018 – 14:30 to 15:30; TAU 29/10/2018 12:15-13:15
Combinatorics, topology and the standard conjectures beyond positivity
Abstract: Consider a simplicial complex that allows for an embedding into . How many faces of dimension or higher can it have? How dense can they be? This basic question goes back to Descartes. Using it and other rather fundamental combinatorial problems, I will motivate and introduce a version of Grothendieck’s “standard conjectures” beyond positivity (which will be explored in detail in the Sunday Seminar). All notions used will be explained in the talk (I will make an effort to be very elementary)
Sunday’s seminar refer to a HUJI Kazhdan seminar given by Karim on this topic. (3-5 Ross building’s seminar room.) This is a good opportunity to congratulate Karim Adiprasito and June Huh on receiving the New Horizon Prize, and congratulations also to Vincent Lafforgue who received the breakthrough prize and to all the other winners!
Sharp thresholds for sparse functions with applications to extremal combinatorics. (based on a joint work by Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer.)
Abstract:
The sharp threshold phenomenon is a central topic of research in the analysis of Boolean functions. Here, one aims to give sufficient conditions for a monotone Boolean function f to satisfy, where , and is the probability that on an input with independent coordinates, each taking the value 1 with probability p.
The dense regime, where , is somewhat understood due to seminal works by Bourgain, Friedgut, Hatami, and Kalai. On the other hand, the sparse regime where was out of reach of the available methods. However, the potential power of the sparse regime was suggested by Kahn and Kalai already in 2006.
In this talk we show that if a monotone Boolean function f with satisfies some mild pseudo-randomness conditions then it exhibits a sharp threshold in the interval , with . More specifically, our mild pseudo-randomness hypothesis is that the p-biased measure of f does not bump up to Θ(1) whenever we restrict f to a sub-cube of constant co-dimension, and our conclusion is that we can find such that .
At its core, this theorem stems from a novel hypercontactive theorem for Boolean functions satisfying pseudorandom conditions, which we call `small generalized influences’. This result takes on the role of the usual hypercontractivity theorem, but is significantly more effective in the regime where
We demonstrate the power of our sharp threshold result by reproving the recent breakthrough result of Frankl on the celebrated Erdos matching conjecture, and by proving conjectures of Huang–Loh–Sudakov and Furedi–Jiang for a new wide range of the parameters.
The artist behind Aleph’s corner has now a website offering over 100 T-shirt designs. In addition to a few pictures related to mathematics there are many in a few other categories: “Jazz,” “Urban,” “Nature,” “Signature design,” and “Sea”. Here are a few of my favorites
This post is my third report from ICM 2018. You may remember that I had planned to live-blog on the last four days of the congress but on Monday evening I realized that this was an unrealistic task and decided instead to blog only on a single day – Monday. A little later I realized this was also unrealistic and decided to limit my blogging to a single lecture by Peter Kronheimer and Tomasz Mrowka on Knots, three-manifolds and instantons. But in the end I did not live-blog at all and in this post I will briefly described Tuesday’s morning lectures and give a belated report on Peter and Tomasz’s lecture. I actually arrived in Rio very early on Saturday morning and attended many talks on Saturday, but this was not part of my planned blogging and I was relaxed and did not take lecture notes. Sunday was a day off and I had a great time with friends.
I greatly enjoyed all of Monday’s morning lectures. The first very inspiring lecture by my friend and colleague Rafi (Ronald) Coifman was entitled Harmonic analytic geometry in high dimensions – Empirical models (click for the video). Rafi’s research spans across a wide range of areas many of which he himself created and goes from the very applied (e.g., applications of harmonic analysis to pluming, biology, and finance) to the very pure (e.g., applications of wavelets to classical problems in harmonic analysis). The lecture covered a lot of ground, starting with Fourier’s original ideas and his perception that he had discovered the “language of nature” and continuing with wide applications to structural and multi-scale analysis of high dimensional data, and to the possibility, pushing Fourier’s vision one step further, of automatically learning the laws of physics from data.
Toward the third lecture on the history of mathematics by Catherine Goldstein I thought that I could relax and listen to a historical lecture that does not require much mathematical efforts. To my surprise, it was very demanding for me (but fully worth the effort) to follow the mathematics itself. The historical discussion and insights were great. The title of the lecture was Long-term history and ephemeral configurations (click for the video) and it started with a famous quote of Poincaré: Mathematics is the art of giving the same name to different things (Poincaré gave the examples of “groups” and “uniform convergence”.) At the center of the talk was Charles Hermite and the lecture dealt, among other things, with the very interesting question: Is mathematics a natural science? For Hermite the answer was: Yes! Altogether there were a lot of great insights and great lines. (Pictures from these two lectures at the end of the post.)
Kronheimer and Mrowka: Knots, three-manifolds and instantons
The talk was fantastic, it had great results, the slides were great, the presentation was great, thoughtful, with a lot of food for thought, both for the large audience and (I think) also for experts. A main famous theorem by the speakers is:
Theorem: Knots with vanishing Instanton Floer homology and (therefore) also knots with trivial Khovanov’s homology are unknots.
Khovanov’s homology are invariants of groups that refine the famous Jones polynomials and, of course, two problems naturally arise. First, is it the case that the Jones polynomial itself determines unknots? (This is a famous open problem.) And also does Khovanov’s homology or Floer’s homology distinguish different knots? (Maybe the answer for the second bold question is known to be negative…) The lecture had four parts
Part I (Tomasz): knots, Papakyriakopoulos, and the main theorem.
I was surprised that I had the feeling that I understood everything in the first part. It started with a quick pictorial introduction to what knots are, then looking at the complement of a knot, followed by Dehn’s lemma that was proved by Papakyriakopoulos. (I think but am not sure that Papakyriakopoulos’s proof is still needed for all the stronger results that follow.)
So Papakyriakopoulos’ theorem tells you that the fundamental group of the complement of a non-trivial knot is not Abelian, but could we say something stronger? Peter mentioned that for most, but not all non-trivial small knots the fundamental group maps onto a dihedral group. And the main result is that for all non trivial knots the fundamental group maps onto SO (3). There were two delicate yet important points that were mentioned. The first is that often SO(3) can or should be replaced by its double cover SU(2), and the second is that there is also a crucial condition (that makes the theorem stronger) about the images of “meridians” (small circles around a point on the knot in its complement).
Part II (Peter): Floer’s instanton homology and many mathematical ideas and tools
The second part was about ideas, notions and tools needed for the proof of the main theorem. Naturally it was more difficult and for various things I only just pleasantly got a general impression together with some pointers on notions that I should (finally) learn. Connections, flat connections, Chern-Simons functionals, Young-Mills equations and their solutions called “instantons”, and the Floer’s (instanton) homology, … . As you can see from the fourth slide the list of tools that are actually needed for the proof extends even further and Peter and Tomasz also mentioned connections with Ozsváth and Szabo theory of Heegard Floer homology.
Part III (Tomasz): Khovanov homology, and skein relations
Surprisingly, the third part dealt with notions that were somewhat easier for me than those of the second part. The Khovanov homology is a refinement of another famous knot-invariant the Jones polynomial.
I remember hearing a few talks about Khovanov homology in the early 2000. Dror Bar Nathan showed how they appear very naturally and how it is a straight forward matter to compute them (alas, not efficiently). In a different talk some years later David Kazhdan showed how, taking a different point of view, those invariants depend on a sequence of amazing miracles. In any case, the Khovanov homology groups are finite dimensional and the Jones polynomial are just the alternating sums of their dimensions (or Euler characteristics). Like the Jones polynomial themselves there is also some connection (“skein relations“) between the Khovanov homologies of knots when you apply two simple operations on the knots.
The skein relations for Khovanov homology are given in terms of a long exact sequence, and similar relations hold for the Floer homology. Moreover there is some relation (a spectral sequence) between these two exact sequences which shows that when Khovanov homology is not trivial then Floer (instanton) homology is also non trivial and hence from what we already know about Floer homology the knot is not trivial.
and when part IV came I expected that the discussion will be aimed at real experts in the audience and that I could relax and think about other things. However this was not the case. Below the fold I will tell you about the surprising fourth part, and then proceed to talk about various other really interesting things. Statistics tell me that only about a third of the readers read below the fold but this time I truly recommend it.
Two dear friends, and great geometers, Ricky Pollack and Branko Grünbaum passed away a few weeks ago. Ricky was a close friend that both Mazi my wife and I loved, and we were both fascinated by his wisdom, charm and love of life. Branko was my academic grand father and I met him through his writings many years before I had the privilege and pleasure to meet in person. Here are some pictures of Ricky and Branko. (If you have more, send me and I will add them.)
The legendary mathematical partnership and friendship of Ricky and Eli Goodman is rare in mathematics.
Five generations in Seattle: Branko was the advisor of Micha A Perles (and also of Joram Lindenstrauss, Moshe Rosenfeld, Joseph Zaks and many others). Micha was my advisor (and also of Meir Katchalski, Michael Kallay, Nati Linial Noga Alon and many others). Isabella Novik was my student and here we are with four student of Isabella: Michael Goff, Kurt Luoto, Andy Frohmaderand, and Steven Klee. (From left to right.)
Saugata Basu, Ricky Pollack and Marie-Francois Roy’s book Algorithms in real algebraic geometry.
. How many faces of dimension 
or higher can it have? How dense can they be?
, the number of d-dimensional simplices exceeds the number of (d − 1)-dimensional simplices by a factor of at most d + 2. This generalizes a result of Descartes, and resolves the Grünbaum-Kalai-Sarkaria conjecture.
and 
are dual. HD stands for Hard Lefschetz and it asserts that certain linear maps 
from 
to 
have the property that their composition from 
points spanning a 
-dimensional space. Let 
be the number of flats of dimension 
spanned by the point. Motzkin conjectured in 1936 and proved over the reals that 
. The planar case follows from the classic Erdos deBruijn theorem. Hu and Wang used {HL} to prove 
, ![i \le [d/2]](https://s0.wp.com/latex.php?latex=i+%5Cle+%5Bd%2F2%5D&bg=ffffff&fg=333333&s=0 "i \le [d/2]")
which was conjectured by Dowling and Wilson.
of graphs on 
with the following three properties:
triangles,
,
.
-Helly type theorems see 
of 3-regular graphs with n labelled vertices
.
of 
of vertices in this graph the number of edges between 
is at least 
.
of subsets (the independent sets of the matroid) of some ground set 
, the induced simplicial complex on 
is pure. In other words, for every 
.
such that the eigenvalues of the localized random walks on 
, where 
, and 
is the probability that 
on an input with independent coordinates, each taking the value 1 with probability p.
, is somewhat understood due to seminal works by Bourgain, Friedgut, Hatami, and Kalai. On the other hand, the sparse regime where 
was out of reach of the available methods. However, the potential power of the sparse regime was suggested by Kahn and Kalai already in 2006.![[p,q]](https://s0.wp.com/latex.php?latex=%5Bp%2Cq%5D&bg=ffffff&fg=333333&s=0 "[p,q]")
, with 
. More specifically, our mild pseudo-randomness hypothesis is that the p-biased measure of f does not bump up to Θ(1) whenever we restrict f to a sub-cube of constant co-dimension, and our conclusion is that we can find 
such that 
