An Improved Bound for Weak Epsilon-Nets in the Plane, by Nathan Rubin, is on the arXive

The paper An Improved Bound for Weak Epsilon-Nets in the Plane, by Nathan Rubin is now on the arxive. we mentioned  the result in this post, and the problem in this post (my very first) over Tao’s blog What’s New.

Abstract: We show that for any finite set P of points in the plane and ϵ>0 there exist O(1/\epsilon^{3/2+\gamma}) points in \mathbb R^2, for arbitrary small γ>0, that pierce every convex set K with |KP|ϵ|P|.

This is the first improvement of the bound of O(1/\epsilon^2)  that was obtained in 1992 by Alon, Bárány, Füredi and Kleitman for general point sets in the plane.

Posted in Combinatorics, Geometry | Tagged , | Leave a comment

ICM2018 First Report

I just came back from Rio from a great congress. Many great talks and many exciting meetings with old and new friends.  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 great lecture  by Peter Kronheimer and Tomasz Mrowka on Knots, three-manifolds and instantons.  But in the end I did not live-blog at all. Let me mention that in the talk by Kronheimer and Mrowka (as in others) a two-speaker talk worked beautifully. It could be a good similar idea to even share a single Fields medal between two (or more) coauthors.

My lecture

Here are the slides for my lecture Noise Stability, Noise Sensitivity and the Quantum Computer Puzzle.


Plans for a Combinatorial Reception at Saint Petersburg ICM 2022.

There were many national receptions at the ICM (I missed a few but made it to the Abel reception and Japan’s reception). This led to the idea of having a reception by a mathematical discipline. We are thinking of a combinatorial event in ICM2022 as follows:

Time: Tuesday evening – the second week of ICM 2022

Location: A park in Saint Petersburg (TBA)

Activity (tentative): Light food and drinks will be available (to buy). Music with a DJ and dancing.

Invitees (tentative): The event will be open for all interested ICM2022 participants.

T-shirts (very tentative, other suggestions welcome)

background colors: red, blue, white and rainbow

Combinatorics at ICM 2018

ICM 2018 could be considered as an excellent conference in combinatorics on its own. There were eleven top-of-the-line speakers (one joint with probability) in wide areas of combinatorics who gave very good talks;  a separate session of much combinatorial content on theoretical  computer science;  many lectures in other sessions (alas, a few conflicting) with interest to combinatorialists;  and, in addition, many of the plenary talks had a strong combinatorial content or connections.  Like for ICM2010 (Post 1 Post 2) I do plan to write more impressions from ICM2018 at a later time. Meanwhile, a few pictures (more, later).

A Few Pictures from ICM-2018 lectures






Posted in Combinatorics, Conferences, ICM2018, Updates | Tagged | Leave a comment

ICM 2018 at Rio, ICM Trivia Questions, the Sao Paulo General Assembly Meeting, and Other Excitements

ICM-trivia questions

You can test yourself in the questions below and then look at the Wikipedea article for the answers.

Mondial – scale excitements are here again!

Not since the Mondial’s final match between France and Croatia,  has an excitement of this magnitude been witnessed here. On Wednesday August 1,  at 14:30 Jerusalem time, mathematics fans will fill bars, restaurants and the beaches, and view on large screens the exciting opening ceremonies of ICM 2018. Well, perhaps not quite like that, but you can all watch the opening ceremony (8:30 Rio Time, August 1, 2018) in this link . (For the actual talks in real time you need to go to Rio, but I was told that  videotaped lectures will be available shortly afterwards.)  I am very proud that essentially I never knew in advance the identity of prize winners (except twice but I had a good excuse both times).

I asked quite a few people for advice about my talk and Tammy Ziegler mentioned to me that she heard many excellent plenary talks and that Etienne Ghys’ talk stood out among them all.  Let me share with you the link to Ghys’ 2006 lecture – session four.

My own lecture is scheduled for the last day of the meeting, Thursday August 9, 8:30-9:30.

Saint Petersburg will host ICM 2022

I dont know the answers to other exciting questions like “will Tim Gowers’s blog from Rio 2018” as he did in ICM 2010 and ICM 2014? Here is, for example,  Tim’s beautiful post on Arthur’s plenary lecture.  This post mentioned France’s bid for ICM2022, and indeed the choice was between two great cities Paris and Saint Petersburg. Earlier this evening the ICM2018 Facebook posted the following:

This was followed 20 minutes later by this post

This, and other important matters are being decided in the IMU general assembly in Sao Paulo as we speak.


Posted in ICM2018, Updates | Leave a comment

Building Bridges II, and Rio ICM 2018

In this post I will talk about Building Bridges II – last week conference in Budapest, about my talk and Lex Schrijver’s talk at the conference, about two old videotaped lectures in Microsoft Research (and a prize carrying competition), and about preparation for ICM 2018 at Rio (and a request for suggestions and advice).

Building Bridges II

Just returned from Budapest from Building Bridges II – a conference celebrating Laci Lovasz’ 70th birthday. Let me share with you the (slightly edited) slides of my talk: Dismantling Bridges and Building New Ones :The argument against quantum computers, near-term predictions, and the laws of noise. (Also, based on experience, this is the safe way to share these slides with me in the future.) Here is the program with videos for most lectures.

Dismantling bridges and building new ones: The argument against quantum computers

The argument from my lecture is briefly this: Computationally superior quantum computing (aka “quantum supremacy”) requires good-quality quantum error-correction, but, on the other hand, good quality quantum error-correction is harder than quantum supremacy. So, both these tasks are doomed to fail.  (The first statement relies on results by Guy Kindler and me.)

This argument is not just against the long-term goals of quantum computation, but also against the very short term goals of building stable qubits and demonstrating quantum supremacy. This argument breaks for classical computation since, while classical computation still requires error-correction, unlike the quantum case, some forms of classical error-correction are supported by very low-level computation.



Bridges and other pictures from the lecture

Lex Schrijver’s lecture

There were many great talks and let me mention one other talk. Lex Schrijver gave a wonderful lecture on \Theta and \vartheta. Here are the mathematical slides featuring two striking formulas for Shannon capacity and one striking formula for Lovasz’ theta function that I did not know about. One very recent formula for \Theta by Jeroen Zuiddam, one quite old formula for \Theta by Haemers,  and one 2013 formula for \vartheta of certain circular graphs by Bachoc, Pecher, and Thiery.  Here is Lex’ videotaped lecture.

From left to right: Lex Schrijver, Laci Lovász, Martin Grötschel, Lex Schrijver

Old videotaped lectures at MSR

Going back to my quantum lecture, among four close friends that have heard me talking about this subject for many years, two have recently told me that they finally understand what I am saying while the other two  said that they don’t understand the argument. (And I cannot assume that these four friends forms a representative sample of the rest of the world, so surely I have some way to go 🙂 .) Two out of the four (one on each side) and also 6-7 other members of the Budapest audience, attended a very preliminary lecture I gave about the topic in  in Microsoft Research back in August 2005 entitled “Is there an (interesting?/realistic?/universal?) model for noise which reduces quantum computation to classical computation?” While the lecture itself is somewhat obsolete by now, you may enjoy Jennifer Chayes’s entertaining introduction which is related to my entertaining opening of this earlier MSR lecture on Social Choice and Threshold Phenomena. Both lectures give great picture of the very distinguished audience members in younger days. (See some pictures below, but it looks much better on video.)

Prize carrying competition: Identify members in the audience of these videoes and drop a comment.

ICM 2018 at Rio

Update: Notices AMS just published ICM 2018 LECTURE SAMPLER with descriptions of five plenary lectures from the congress  by Sanjeev Arora, Catherine Goldstein, Sylvia Serfaty, Gregory F. Lawler and me.

Early next month I go to Rio for ICM 2018 which is surely going to be an exciting event. I am already quite thrilled and a little nervous about it.  I may try to blog about the second half and I am sure some capable bloggers will blog about the beginning of the congress which is bound to be exciting. My paper for the proceedings  is entitled “Three puzzles on mathematics, computations, and games“.   (The link is to the arXive version which is not fully updated. Also, the proceeding’s version will have full references.) The paper discusses the subtle connections between theory and reality in the context of mathematics and computation, and  the three topics presented are, linear programming,  noise stability of voting rules,  and quantum computers.

In the lecture  I plan to mainly talk about the theory of noise sensitivity and stability in the context of voting rules and percolation (starting with my work with Benjamini and Schramm), in the context of quantum computing systems  (my work with Guy Kindler), and about my potentially most important yet  controversial application: the argument against quantum computers.

I am still hesitating about some aspects of the lecture: power point or beamer? Should I emphasize the theory and theorems or rather the conceptual matters and interpretations? Should I talk mainly about quantum computers (like in Budapest) or also about less controversial aspects of noise stability and sensitivity?

Last-minutes suggestions, tips, requests or demands about my upcoming ICM lecture (which I plan to finalize in a week or so) are welcome, here or in private.



Getting inspired in Budapest 1: Laci and me in matching sweathers. Is it a coincidence? asked a dear Facebook friend which reminds me that we still have to discuss coincidences as promised long ago.



Getting inspired in Budapest 2: with Endre Szemeredi and Terry Tao.


From a lecture of Scott Aaronson at the Simons Institute: Ironically the main application of quantum supremacy is to disprove my argument against quantum supremacy.


Pictures from MSR 2004 lecture on social choice and threshold phenonena

The  MSR 2005 lecture on quantum computers 


Posted in Combinatorics, Conferences, ICM2018, Updates | Tagged | 1 Comment

Test Your Intuition 35: What is the Limiting Distance?

(Just heard it today from Sergiu Hart.)

At time t=0, point A is at the origin (0,0) and point B is distance 1 appart at (0,1). A moves to the right (on the x-axis) with velocity 1  and B moves with velocity 1 towards A.  What will be the distance between A and B when t goes to infinity?

Posted in Test your intuition | Tagged , | 16 Comments

Beyond the g-conjecture – algebraic combinatorics of cellular spaces I

The g-conjecture for spheres is surely the one single conjecture I worked on more than on any other, and also here on the blog we had a sequence of posts about it by Eran Nevo (I,II,III,IV). Here is a great survey article  on the g-conjecture by Ed Swartz 35 Years and Counting and slides of a great lecture by Lou Billera “Even more intriguing, if rather less plausible…”.

June Huh talked about the conjecture on Numberphile attracting 183,893 views and counting. With hundreds of thousands new people interested in the g-conjecture and some highly capable teams of researchers who were interested even before the video, it is safer to say that the solution of the conjecture is imminent 🙂 and this is going to be exciting! So I want to say a few things  about the “G-program”, questions that go beyond the g-conjecture. (OK, I realize I need to split it into  parts and also that each of the items deserves a separate post in the future.)

I wrote a post to suplement Eran Nevo’s posts on how the g-conjecture came about, and here is a very brief summary:

Simplicial polytopes: Leading to the g-theorem we can start with Euler’s theorem, and its high dimensional extensions for general polytopes.  Next follow the Dehn-Sommerville relations for simplicial polytopes. Here are some main landmarks toward the g-conjecture and its solution for simplicial polytopes.

  1. The upper bound theorem (UBT, conjectured by Motzkin, 1957, proved by Peter McMullen 1970),
  2. The lower bound theorem (LBT, conjectured by Grunbaum in the 60s, proved by Barnette 1970),
  3. In 1970, the generalized lower bound conjecture (GLBC) was conjectured by McMullen and Walkup, and the g-conjecture was proposed by McMullen.
  4.  In 1979, the sufficiency part of the g-conjecture was proved by Billera and Lee.
  5.  Also in 1979, the necessity part of the g-conjecture was proved by Stanley based on the hard Lefschetz theorem for toric varieties.
  6.  In 1993 Peter McMullen found a direct geometric proof for the case of simplicial polytopes.
  7. The GLBC (now, GLBT) consists of the linear inequalities  of the g-conjecture and an additional part about cases of equality. The equality part was proved in 2012 by Murai and Nevo (see this post).

Triangulated spheres: All of the above are conjectured to hold for simplicial spheres (and even to homological spheres in the most inclusive sense). Barnette’s proof for the LBT applies to triangulated spheres. The UBT was proved for spheres by Stanley (1975) pioneering the connection with commutative algebra. The g-conjecture for triangulated spheres is still open, and this is what we refer to these days as the “g-conjecture”.

Algebraic tools:  For the connection with commutative algebra and algebraic geometry pioneered by Stanley, see this post. The crucial linear algebraic property behind the g-conjecture is a linear algebraic statement called the Lefschetz property that is a  consequence of the Hard Lefschetz Theorem (when it applies).  McMullen’s 1993 proof validates the Lefschetz property in greater generality (for arbitrary simplicial polytopes rather than rational simplicial polytopes) via an inductive argument that relies on “Pachner moves”. Certain Hodge-Riemann inequalities also played an important  role in McMullen’s proof.  Hodge-Riemann’s inequalities play a crucial role also in the recent solution of Rota’s conjecture by Adiprasito, Huh and Katz. (See this post and this beautiful Quanta Magazine article by Kevin Hartnett.)

In this extra footage for his Numberphile video (viewes by 10,000) June mentions the hard Lefschetz theorem.


Eran Nevo (left)  and Karim Adiprasito 

Going Beyond the g-conjecture: The “G-Program”

Let K be a class of cellular $(d-1)$-dimensional spheres.

We want to define d-parameters h_0(K),h_1(K)\dots h_{d}(K) forming the h-vector of K, that satisfies

(1) latex h_i(K)=h_{d-i}(K)$,

(2) 1=h_0(K) \le h_1 (K)\le \dots h_[d/2] (K). In other words if we let g_i=h_1-h_{i-1} then g_i \ge 0. (The g_i are the g-numbers giving the conjecture its name.)

(3) Some interesting non-linear inequalities in the spirit of those for the original conjecture.

If this program is not general enough we would like to consider arbitrary manifolds without boundary or even pseudomanifolds without boundary, to make some adaptation to allow boundary, and even  to allow the “cells” to be rather exotic. We also want to understand the equality cases for the inequalities and how the h-vectors reflect the combinatorics, topology, and algebra of the cellular space K.

Some classes of cellular spheres: The class of simplicial spheres (and polytopes) contains the classes of flag spheres (and polytopes) and completely balanced spheres (and polytopes). The class of regular CW spheres with the intersection property, (including general polytopes) contains the classes of cubical spheres (and polytopes) and centrally symmetric spheres (and polytopes). Regular CW spheres without the intersection property include those coming from Bruhat intervals of Coxeter groups.  (The class of zonotopes is also very important but its connections to the present story are more subtle.)

From the algebraic geometry side, simplices correspond to complex projectice spaces, the h-vectors for simplicial polytopes correspond to Betti numbers that measure how more complicated a general smooth (toric) variety is. For general (rational) polytopes, you get more complexity in terms of complicated singularities, and for objects like intervals in Bruhat orders you have even more complicated singularities. The varieties exist only for small fragments of the pictures and beyond that you need to do some sort of “algebraic geometry without varieties”.

A) The original g-conjecture: simplicial polytopes and simplicial spheres

Again, let me refer the reader to the four posts by Eran Nevo (I,II,III,IV). I will repeat the definition of h-vectors and g-vectors at the end of the post.

Problem 1: Prove the g-conjecture for triangulated sphere.

Again, the most promising avenue towards a proof is by proving the Lefschetz property for face rings associated with triangulated spheres.

Problem 2: Understand the cases of equality for the Macualay (non-linear) inequalities?

Problem 3: Show that the gap in the inequalities tends to infinity for every sequence of simplicial polytopes tending to a smooth body. Formulate and prove an extension to spheres.

In the polytope case this problem was settled. This has been proved (for polytopes, see this paper and this post) by Karim Adiprasito, Eran Nevo,  and José Alejandro Samper for the linear inequalities (see picture below). The result, referred to as the “geometric LBT” asserts that for a sequence of simplicial polytopes P_n tending to a smooth body, g_i(P_n) \to \infty.  More recently, Karim Adiprasito managed to prove it for the nonlinear inequalities. For triangulated spheres, finding the relevant notion of limits for triangulations would be a place to start.

The Lefschetz property (when it holds) allows to associate to every simplicial sphere S, a (shifted) order of monomials  M(S) with g_i monomials of degree i, i=1,2,\dots,[d/2] of degree [d/2]. There is also a construction (Kalai, 1988) that associates a triangulated sphere S(M) (called “squeezed sphere”) with every such M. Satoshi Murai proved that M(S(M))=M.

Problem 4: Study M(S)

B) General polytopes: The toric h-vector and g-vector

Intersection homology allows the definition of h- and g- polynomials for general polytopes. Those are linear combinations of flag numbers.  The post Euler’s formula, Fibonacci, the Bayer-Billera theorem, and Fine’s cd-index is very relevant.

Again, I will repeat a definition of h-vectors and g-vectors at the end of the post. HLT for intersection homology shows the nonnegativity of the g-polynomials for rational polytopes. Kalle Karu (relying on works by Barthel, Brasselet, Fieseler and Kaup and by Bressler and Luntsand and on McMullen’s 1998 proof) proved it for general polytopes!

Problem 5: Show that the toric g-numbers are nonnegative for every strongly regular CW-sphere.  (In particular for all polyhedral spheres.)

Recall that  a regular CW complex is a CW-complex where the closure of an open cell is homeomorphic to a close ball.  Regular CW spheres such that the intersection of two faces is a face are also called strongly regular CW complexes.

A big open problem which is open even for polytopes is

Problem 6: Show that the toric g-numbers form an M-vector.

Problem 6 is of great interest also for rational polytopes. The difficulty is that intersection homology does not admit a ring structure. One approach is to introduce some additional ring structure while another approach is to try to derive the M-inequalities from weaker algebraic or combinatorial conditions.

Problem 7: Understand the cases of equality for the linear inequalities and the non linear inequalities.

Recent advances by Adiprasito and Nevo in their paper QGLBT for polytopes toward the equality case for the toric GLBC. They also extended the geometric LBT to general polytopes.

Problem 8 (Jonathan Fine): Extend the toric g-numbers to a Fibonacci number of sharp nonnegative parameters, based, perhaps, on a Fibonnaci number of homology groups.

Interesting and rather mysterious duality relations were discovered for g-numbers. They were found to be  related to Koszul duality and to Mirror symmetry. See this recent post. \gamma (P) of that post is g_2(P).

Problem 9 : Understand further the connections between toric g-numbers and related invariants of polytopes and their dual.

Closely related issues are: flag vectors and the Bilerra-Bayer theorem (see this post), nonnegative flag inequalities, the cd-index, FLAGTOOL, and Braden-MacPherson theorem. An excellent 2006 paper on toric h- and g- numbers and related combinatorics and algebraic-geometry is by Tom Braden:  Remarks on the combinatorial intersection cohomology of fans.

Problem 10: Understand (all) linear inequalities among flag numbers of d-polytopes and polyhedral d-spheres.

Warning: I used Whitehead notion “strongly regular CW complexes”, and “regular CW complexes with the lattice property” and “regular CW-complexes with the intersection property” for the same mathematical object. Sorry.

C) Regular CW-spheres and Kazhdan-Lusztig polynomials

What happens when you give up also the lattice property?  For Bruhat intervals of affine Coxeter groups the Kazhdan Luztig polynomial can be seen as subtle extension of the toric g-vectors adding additional layers of complexity. Of coursem historically Kazhdan-Lustig polynomials came before the toric g-vectors. (This time I will not repeat the definition and refer the readers to the original paper by Kazhdan and Lustig, this paper by Dyer and   this paper by BrentiCaselli, and  Marietti.) It is known that for Bruhat intervals with the lattice property the KL-polynomial coincide with the toric g-vector. Can one define h-vectors for more general regular CW spheres?

Problem (fantasy) 12: Extend the Kazhdan-Luztig polynomials (and show positivity of the coefficients) to all or to a large class of regular CW spheres.

This is a good fantasy with a caveat: It is not even known that KL-polynomials depend just on the regular CW sphere described by the Bruhat interval. This is a well known conjecture on its own.

Problem 11: Prove that Kazhdan-Lustig polynomials are invariants of the regular CW-sphere described by the Bruhat interval.

A more famous conjecture was to prove that the coefficients of KL-polynomials are non negative for all Bruhat intervals and not only in cases where one can apply intersection homology of Schubert varieties associated with Weil groups. (This is  analogous to moving from rational polytopes to general polytopes.) In a major 2012 breakthrough, this has  been proved by Ben Elias and Geordie Williamson following a program initiated by Wolfgang Soergel.

There is vast literature on KL-polynomials further extensions and combinatorial aspects. The combinatorics of regular, but not strongly regular CW complexes is again related to the cd-index and let me also mention that there is interesting combinatorics (and a good opportunity for the G-program and fantasy 12) for simplicial posets, namely when you insist on lower intervals to be Boolean but give up the lattice property.

D) Cubical polytopes and spheres: Adin’s h-vectors

A cubical polytope (sphere) is a polytope all whose faces are combinatorial cubes. Cubical complexes are important and mysterious objects. (They play a crucial role in some recent developments in 3D topology, see here.) Ron Adin defined h-numbers and formulated a “GLBC ineqequalities  for cubical polytopes (and spheres). Again, I will repeat Adin’s definition of h-vectors and g-vectors at the end of the post.

Problem 13: Prove Adin’s conjecture for cubical polytopes and spheres.

A recent paper by Adin, Kalmanovich, and Nevo On the cone of f -vectors of cubical polytopes shows that if Adin’s conjecture is valid, it describes the full cone spanned by linear inequalities among  face number of cubical d-polytopes.

Problem 14: Explore an UBT  for cubical polytopes and non-linear inequality for Adin’s numbers.

Problem 15: Extend (in the toric spirit) Adin’s invariant to polytopes and spheres with the property that every two-dimensional face has at least four edges (or just an even number of edges).


Coming next on the G-program:

  • E) Centrally-symmetric polytopes and spheres;
  • F) Flag polytopes and spheres – the Charney-Davis conjecture and the \gamma-conjecture;
  • G) Completely balanced polytopes and spheres;
  • H) Polytope pairs and polytopes with one non-simplex facet;
  • I) The Batchi-Datta conjecture;
  • J) Sharper versions of the generalized lower bound inequalities and further applications of the Lefschetz property.
  • K) Stanley’s local theory
  • L) Simplicial posets and ASL.
  • M) Minkowski sums of polytopes;
  • N) Section of a given polytope;
  • O) Integer points in polytopes and associated polynomials
  • P) Grunbaum’s conjecture and the GUBT (a related old post); (Let me mention that Karim Adiprasito reported recently on progress on the Grunbaum’s conjecture which is related to the g-conjecture.)
  • Q) The Welzl-Wagner framework and early continuous analogs;
  • R) triangulations of manifolds and pseudomanifolds.

I am sure that I missed, overlooked, forgot, or wasn’t aware of several things that I should mention. Please comment here or alert me about them. Also most of the problems I described are on the basic combinatorics level of the theory and Karim promised to contribute some problems on the algebraic level for a later post in this series.

STANLEYLAND-enumerative algebraic combinatorics

Some definitions

General polytopes: Toric h and g

Consider general d-polytopes. For a set S \subset {0,1,2,…,d-1}, S={ i_1,i_2,\dots,i_k} , i_1<i_2< \dots, define the flag number f_S as the number of chains of faces F_1 \subset F_2 \subset \dots F_k, where \dim F_j=i_j. If P is a d dimensional polytope and Q is an e dimensional polytope, their direct sum P \oplus Q is obtained by embedding P and Q in two orthogonal subspaces such that the origin is an interior point of both P and Q, and taking the convex hull. The free join P*Q is the convex hull of P and Q when they are embedded in two skew affine spaces of dimensions d and e in a (d+e+1)-dimenional space.

For the original recursive definition of toric h-vectors see Stanley’s 1987 paper Generalized h-vectors, intersection cohomology of toric varieties, and related results. A simple axiomatic definition of the toric h-vectors (taken from my 1988 paper A new basis of polytopes) is the following: We consider two polynomials h[P](x) and $g[P](x)$, with the properties

(A1) h[P](x)=\sum_{0\leq i\leq d}h_i(K)x^{d-i}, and g[P](x)=\sum_{0\leq i\leq [d/2]}g_i(K)x^{d-i}, where g_i=h_i-h_{i-1}.

(A2) h[P](x)=g[P](x) =1 if P is a point.

(A3) The coefficients $h_i$ of h[P](x) are linear combinations of flag numbers.

(A4) h[P \oplus Q](x)=h[P](x)h[Q](x).

(A5) g[P * Q](x)=g[P](x)g[Q](x).

(A1)-(A5) determine uniquely the polynomials h and g. In the simplicial case  all flag numbers are determined by ordinary face numbers and this gives the definition described below.

Cubical polytopes: Adin’s short h-vector and (long) h-vector

Adin’s short h-vector is defined as follows:

h^{sc}[Q](t)=\sum_{i=0}^{d-1} h_i^{sc}(Q)t^j=\sum_{j=0}^{d-1}f_j(Q)(2t)^j(1-t)^{d-1-j}.

Adin’s (long) h-vector is defined by h_0^c=2^d, and h_i^{sc}=h_i^c+h_{i+1}^c, for 0 \le i \le d-1.

The short and long g-vectors are defined by taking differences as in the simplicial case.
g_i^{sc}=h_i^{sc}-h_{i-1}^{sc} for 1\le i\le [(d-1)/2] ;
g_0^c=h_o^c=2^{d-1}. g_i^{c}=h_i^{c}-h_{i-1}^{c} for
1\le i\le [d/2].


The simplicial case: h-vectors  g-vectors, and the g-conjecture

The fvector (face vector) of  a cellular complex K is f(K)=(f_{-1},f_0,f_1,...) where f_{i} is the number of i-dimensional faces of K. For example, if K is the (d-1)-simplex then f_{i-1}(K)=\binom{d}{i}. Let K be a (d-1)-dimensional simplicial complex. the hvector of K is  defined by

\sum_{0\leq i\leq d}h_i(K)x^{d-i}= \sum_{0\leq i\leq d}f_{i-1}(K)(x-1)^{d-i}.


Let g_0(K):=h_0(K)=1, g_i(K):=h_i(K)-h_{i-1}(K) for 1\leq i\leq \lfloor d/2\rfloor. g(K):=(g_0(K),...,g_{\lfloor d/2\rfloor}(K)) is called the g-vector of K. The Dehn-Sommerville relations state that when K is a sphere h_i(K)=h_{d-i}(K) for every 0\leq i\leq d. (This result can be proved combinatorially, for the larger family of Eulerian posets, and, for rational simplicial polytopes  it reflects  Poincare duality for the associated toric variety.)

We say that a vector h is an M-vector (M for Macaulay) if it is the f-vector of a multicomples, i.e. of a collection of multisets (elements can repeat!) closed under inclusion. For example, h=(1,1,1) is an M-vector, as is demonstrated by the multicomplex \{1=x^0,x,x^2\}, written in monomial notation – the exponent tells how many copies of x to take. Macaulay gave a numerical characterization of such vectors. (The proof uses compression – see this post for a general description of the method.)

The g-conjecture:

The following are equivalent:

(i) The vector (f_0,f_1,\dots , f_{d-1}) is the f-vector of a simplicial d-polytope

(ii) The vector (f_0,f_1,\dots , f_{d-1}) is the f-vector of a triangulated (d-1)-sphere.


(a) h_i=h_{d-i} for every i

(b)  g(K) is an M-vector.

Last observation: explained to the general public, the most confusing aspect of the story is when you draw a triangle and refer to it as a “sphere”.

A description of the Adiprasito, Nevo,  and Samper paper.

Our chair Elon Lindenstrauss promised to ease the financial burdon caused by my habit of paying for Karim Adiprasito coffee’s  once after every breakthrough, so I started to collect the receipts.

Posted in Combinatorics, Convex polytopes, Geometry | Tagged , , , , , , , , , , , , , , , , , , | 6 Comments

An Interview with Yisrael (Robert) Aumann

I was privileged to join Menachem Yaari and Sergiu Hart in interviewing Yisrael Aumann.  The interview is in Hebrew. It is an initiative of the Israel Academy of Sciences and the Humanities.

For our non Hebrew speakers here is in English an interview with Aumann by Sergiu Hart from 2005, and here is a paper  that I wrote in 2006  Science, beliefs and knowledge: a personal reflection on Robert J. Aumann’s approach.


Aumann explained to us some details of his Ph D thesis on knot theory,

Can game theory help resolving human conflicts and the suffering and waste caused by them?

Entomologist observe ants but dont tell them what to do.

Posted in Academics, Combinatorics, Games, Geometry, Rationality | Tagged , , | 1 Comment

Igor Pak is Giving the 2018 Erdős Lectures in Discrete Mathematics and Theoretical Computer Science

Update: The lectures this week are cancelled.  They will be given at a later date.

Next week Igor Pak will give the 2018 Erdős Lectures


  • Monday Jun 18 2018

    Combinatorics — Erdos lecture: Igor Pak (UCLA) “Counting linear extensions”

    11:00am to 12:30pm


    IIAS, Eilat hall, Feldman bldg (top floor), 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.
  • Wednesday Jun20, 2018

    CS Theory — Erdős Lecture: Igor Pak (UCLA) “Counting Young tableaux”

    Igor Pak (UCLA)
    10:30am to 12:00pm


    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.

  • Thursday, Jun21, 2018

    Colloquium: Erdos lecture – Igor Pak (UCLA) “Counting integer points in polytopes”

    2:30pm to 3:30pm


    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.?
Posted in Combinatorics, Computer Science and Optimization, Geometry, Updates | Tagged | Leave a comment

Vera T. Sòs, Doctor Philisophiae Honoris Causa, Hebrew University of Jerusalem

Videotaped by Ehud Friedgut.

Posted in Combinatorics, Updates, Women in science | Tagged | Leave a comment

Sailing into High Dimensions

On June 20 at 13:30 I talk here at HUJI about Sailing into high dimensions. (Thanks to Smadar Bergman for the poster.)

Posted in Combinatorics, Geometry, Updates | Tagged | 2 Comments