Media items on David, Amnon, and Nathan

David Kazhdan, a very famous mathematician from my department with a super-human understanding of mathematics (and more) is recovering from a terrible bike accident. Here is an article about him from “Maariv.” (In Hebrew)

Amnon Shashua, a  computer science professor at the Hebrew University founded Mobileye fifteen years ago. Here is one of many articles about Mobileye. Mobileye helps eliminate car accidents and her sister company Orcam that Amnon also founded develops aids for the visually impaired.

Nathan Keller, now at Bar-Ilan University,  is a former Ph D student of mine working in probabilistic combinatorics and he has a parallel impressive academic career in the area of cryptology. Here is an article about Nathan from Arutz 7 (in Hebrew).   (The picture above shows Nathan with Eli Biham and Elad Barkan after their 2003 success in cracking the popular GSM cellular phone network encryption code.)

Special Quantum PCP and/or Quantum Codes: Simplicial Complexes and Locally Testable CodesDay

room B-220, 2nd floor, Rothberg B Building

On Thursday, the 24th of July we will host a SC-LTC (simplicial complexes and classical and quantum locally testable codes) at the Hebrew university, Rothberg building B room 202 (second floor) in the Givat Ram campus. Please join us, we are hoping for a fruitful and enjoyable day, with lots of interactions. Coffee and refreshments will be provided throughout the day, as well as free “tickets” for lunch on campus
There is no registration fee, but please email dorit.aharonov@gmail.com preferably by next Tuesday if there is a reasonable probability that you attend –  so that we have some estimation regarding the number of people, for food planning

Program:SC-LTC day – simplicial complexes and locally testable classical and quantum codes –Rothberg building B202
9:00 gathering: coffee and refreshments

9:30 Irit Dinur: Locally testable codes, a bird’s eye view

10:15: coffee break

10:45 Tali Kaufman, High dimensional expanders and property testing

11:30 15 minutes break

11:45 Dorit Aharonov, quantum codes and local testability

12:30 lunch break

2:00 Alex Lubotzky: Ramanujan complexes

2:50 coffee break

3:15 Lior Eldar: Open questions about quantum locally testable codes and quantum entanglement

3:45 Guy Kindler: direct sum testing and relations to simplicial complexes ( Based on David, Dinur, Goldenberg, Kindler, and Shinkar, 2014)

4:15-5 free discussion, fruit and coffee

Happy Birthday Ervin, János, Péter, and Zoli!

The four princes in summit 200, ten years ago.

(Left to right) Ervin Győri, Zoltán Füredi, Péter Frankl and János Pach

In 2014, Péter Frankl, Zoltán Füredi, Ervin Győri and János Pach are turning 60 and summit 240 is a conference this week in Budapest to celebrate the birthday of those ever-young combinatorics princes. I know the four guys for about 120 years. I first met Peter and Janos (together I think) in Paris in 1979, then Zoli at MIT in 1985 and  I met Ervin in the mid late 90s in Budapest. Noga Alon have recently made the observation that younger and younger guys are turning 60 these days and there could not be a more appropriate time to realize the deep truth of this observation than this week.

The mathematical work of our eminent birthday boys was and will be amply represented on this blog. So let me give just one mathematical link to János’s videotaped plenary lecture at Erdős Centennial conference. (Click on the picture to view it. Here is again the link just in case.)

And now, here are a few pictures of our birthday boys.

János 72(?)

My Mathematical Dialogue with Jürgen Eckhoff

Jürgen Eckhoff, Ascona 1999

Jürgen Eckhoff is a German mathematician working in the areas of convexity and combinatorics. Our mathematical paths have met a remarkable number of times. We also met quite a few times in person since our first meeting in Oberwolfach in 1982. Here is a description of my mathematical dialogue with Jürgen Eckhoff:

Summary 1) (1980) we found independently two proofs for the same conjecture; 2) (1982) I solved Eckhoff’s Conjecture; 3) Jurgen (1988) solved my conjecture; 4) We made the same conjecture (around 1990) that Andy Frohmader solved in 2007,  and finally  5) (Around 2007) We both found (I with Roy Meshulam, and Jürgen with Klaus Peter Nischke) extensions to Amenta’s Helly type theorems that both imply a topological version.

(A 2009 KTH lecture based on this post or vice versa is announced here.)

Let me start from the end:

5. 2007 – Eckhoff and I  both find related extensions to Amenta’s theorem.

Nina Amenta

Nina Amenta proved a remarkable extension of Helly’s theorem. Let $\cal F$ be a finite family with the following property:

(a) Every member of $\cal F$ is the union of at most r pairwise disjoint compact convex sets.

(b) So is every intersection of members of $\cal F$.

(c) $|{\cal F}| > r(d+1)$.

If every r(d+1) members of $\cal F$ has a point in common, then all members of $\cal F$ have a point in common!

The case r=1 is Helly’s theorem, Grünbaum and Motzkin proposed this theorem as a conjecture and proved the case r=2. David Larman  proved the case r=3.

Roy Meshulam

Roy Meshulam and I studied a topological version of the theorem, namely you assume that every member of F is the union of at most r pairwise disjoint contractible compact sets in $R^d$ and that all these sets together form a good cover – every nonempty intersection is either empty or contractible. And we were able to prove it!

Eckhoff and Klaus Peter Nischke looked for a purely combinatorial version of Amenta’s theorem which is given by the old proofs (for r=2,3) but not by Amenta’s proof. An approach towards such a proof was already proposed by Morris in 1968, but it was not clear how to complete Morris’s work. Eckhoff and Nischke were able to do it! And this also implied the topological version for good covers.

The full results of Eckhoff and Nischke and of Roy and me are independent. Roy and I showed that if the nerve of $\cal G$ is d-Leray then the nerve of $\cal F$ is ((d+1)r-1)-Leray. Eckhoff and showed that if the nerve of $\cal G$ has Helly number d, then the nerve of $\cal F$ has Helly number (d+1)r-1. Amenta’s argument can be used to show that if the nerve of $\cal G$ is d-collapsible then the nerve of F is  ((d+1)r-1)-collapsible.

Here, a simplicial comples K is d-Leray if all homology groups $H_i(L)$ vanishes for every $i \ge d$ and every induced subcomplex L of K.

Roy and I were thinking about a common homological generalization which will include both results but so far could not prove it.

Happy Birthday Richard Stanley!

This week we are celebrating in Cambridge MA , and elsewhere in the world, Richard Stanley’s birthday.  For the last forty years, Richard has been one of the very few leading mathematicians in the area of combinatorics, and he found deep, profound, and fruitful links between combinatorics and other areas of mathematics.  His works enriched and influenced combinatorics as well as other areas of mathematics, and, in my opinion, combinatorics matured greatly as a mathematical discipline thanks to his work.

Trivia Quiz

Correct or incorrect?

(1) Richard drove cross-country at least 8 times (2) In his youth, at a wild party, Richard Stanley found  a proof of FLT consisting of a few mathematical symbols. (3) Richard  jumped at least once from an airplane (4) Richard is actively interested in the study of consciousness (5) Richard found a mathematical way to divide by zero

Seven Early Papers by Richard Stanley That You Must Read.

Richard’s Green book: Combinatorics and Commutative Algebra

Combinatorics and Commutative Algebra

(1) R. P. Stanley, The upper bound conjecture and Cohen-Macaulay rings. Studies in Appl. Math. 54 (1975), no. 2, 135–142. The two seminal papers (1) and (3) (below) showed remarkable and unexpected applications of commutative algebra to combinatorics. In each of these papers a central conjecture in combinatorics was solved in a completely unexpected way which was the basis for a later remarkable theory. Paper (1) is the starting point for the interrelation between commutative algebra and combinatorics of simplicial complexes and their topology. In this work Richard Stanley proved the Motzkin-Klee upper bound conjecture for triangulations of spheres. This conjecture asserts that the maximum number of k-faces for a triangulation of a (d-1)-dimensional sphere with n vertices is attained by the boundary complex of the cyclic d-dimensional polytope with n vertices. Peter McMullen proved this conjecture for simplicial polytopes and Richard Stanley proved it for arbitrary triangulations of spheres. The key point was that a certain ring (the Stanley-Reisner ring) associated with a simplicial polytope has the Cohen-Macaulay property. The connection between combinatorics and commutative algebra is far reaching, and in subsequent works combinatorial problems led to developments in commutative algebra and techniques from the two areas were combined.  A more recent important paper by Richard on applications of commutative algebra for the study of face numbers is: R. P. Stanley, Subdivisions and local h-vectors. J. Amer. Math. Soc. 5  And here is, a few weeks old important development in this theory: Relative Stanley-Reisner theory and Upper Bound Theorems for Minkowski sums, by Karim A. Adiprasito and Raman Sanyal.

The Cohen-Macaulay property, magic squares and lattice points in polytopes

(2) R. P. Stanley, Magic labelings of graphs, symmetric magic squares, systems of parameters, and Cohen-Macaulay rings. Duke Math. J. 43 (1976), no. 3, 511–531. This paper starts with a theorem about enumeration of certain magic squares. Solving a long-standing open problem, Stanley proved that the generating function for the number of k by k integer matrices (k– fixed) with nonnegative entries and row sums and column sums equal to nis rational. This is the starting point of a deep algebraic theory of integral points in polyhedra.

Enters the Hard-Lefshetz Theorem: McMullen’s g-conjecture

(3) R. P. Stanley, The number of faces of a simplicial convex polytope. Adv. in Math. 35 (1980), no. 3, 236–238. The g-conjecture proposes a complete characterization of face numbers of d-dimensional polytopes. One linear equality that holds among face numbers is, of course, the Euler-Poincaré relation. This relation implies additional [d/2] equalities called the Dehn-Sommerville relations. Peter McMullen proposed an additional system of linear and nonlinear inequalities as a complete characterization of face numbers of polytopes. The sufficiency part of this conjecture was proved by Billera and Lee. Richard Stanley’s brilliant proof for McMullen’s inequalities that established the g-conjecture was based on the Hard Lefschetz Theorem from algebraic topology. Starting from a simplicial polytope P (with rational vertices) we associate to it a toric variety T(P). It turned out that the cohomology ring of this variety is closely related to the Stanley-Reisner ring mentioned above. The Hard Lefschetz Theorem implies an algebraic property of the Stanley-Reisner ring from which McMullen inequalities can be deduced by direct combinatorial reasoning. Richard found a number of other combinatorial applications of the Hard Lefschetz theorem (including the solution of the Erdos-Moser conjecture).

Here is the abstract of Lou Billera’s lecture

LOUIS BILLERA (CORNELL)

Even more intriguing, if rather less plausible…

The title is how Peter McMullen described his own conjectured characterization of the f-vectors of simplicial polytopes in his 1971 lecture notes on the upper bound conjecture written with Geoffrey Shephard. Yet by the end of that decade, the so-called g-conjecture would become the g-theorem, and algebraic combinatorics (as practiced at MIT) would have attracted the attention of mainstream mathematics, almost entirely due to the startling proof given by Richard Stanley.

I will briefly describe some of the events leading to this proof and some of its still developing consequences.

Enumeration

Enumeration is Richard’s true mathematical love.   Richard’s monumental books EC1 and EC2 (The picture is of EC1 and a young fan) (4) A baker’s dozen of conjectures concerning plane partitions, in Combinatoire Énumérative (G. Labelle and P. Leroux, eds.), Lecture Notes in Math., no. 1234, Springer-Verlag, Berlin/Heidelberg/New York, 1986, pp. 285-293. 13 beautiful conjectures on counting plane partitions with various forms of symmetry. (5) Generating functions, in Studies in Combinatorics (G.-C. Rota, ed.), Mathematical Association of America, 1978, pp 100-141. For me this was the best introduction to generating functions, clear and inspiring. The entire MAA 1978 Rota’s blue little volume on combinatorics is great. Buy it!

Posets everywhere

(6) Supersolvable latticesAlgebra Universalis 2 (1972), 197-217. This paper provides a profound link between group theory and the study of partially ordered sets. It can be seen as a starting point of Stanley’s own work on the Cohen-Macaulay property and it had much influence on later works on combinatorial properties of lattices of subgroups by Quillen and many others, and also on the study of POSETS (=partially ordered sets) arising from arrangements of hyperplanes. The algebraic notion of supersolvable groups is translated to an important combinatorial notion for partially ordered sets. (There is a more detailed paper which I could not find online: R. P. Stanley, Supersolvable semimodular lattices. Mobius algebras (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1971), pp. 80–142. Univ. Waterloo, Waterloo, Ont., 1971.)

Combinatorics and representation theory

(7) On the number of reduced decompositions of elements of Coxeter groupsEuropean J. Combinatorics 5 (1984), 359-372. This paper gives an important result proved using representation theory. It is one of many results by Stanley on connections between enumerative combinatorics, representation theory, and invariant theory. Again, this paper represents an exciting area of research about the connection of enumerative combinatorics and representation theory that I am less familiar with.  A very inspiring survey paper is: Invariants of finite groups and their applications to combinatoricsBull. Amer. Math. Soc. (new series) 1 (1979), 475-511. Here are abstracts of two lectures from the meeting on some recent developments in combinatorial representation theory and symmetric functions.

GRETA PANOVA (UCLA)

The Kronecker coefficients: an unexpected journey

Kronecker coefficients live at the intersection of representation theory, algebraic combinatorics and, most recently, complexity theory. They count the multiplicities of irreducible representations in the tensor product of two other irreducible representations of the symmetric group. While their journey started 75 years ago, they still haven’t found their explicit positive combinatorial formula, and present a major open problem in algebraic combinatorics. Recently, they were given a new role in the field of Geometric Complexity Theory, initiated by Mulmuley and Sohoni, where certain conjectures on the complexity of computing and deciding positivity of Kronecker coefficients are part of a program to prove the “”P vs NP”” problem.

We will take the Kronecker coefficients to asymptotics land and bound them. As an unexpected consequence of this trip, we find bounds for the difference of consecutive coefficients in the q-binomial coefficients (as polynomial in q), generalizing Sylvester’s unimodality theorem and connecting with results of Richard Stanley. Joint work with Igor Pak.

THOMAS LAM (U MICHIGAN)

Truncations of Stanley symmetric functions and amplituhedron cells

Stanley symmetric functions were invented (by Stanley) with applications to the enumeration of reduced words in the symmetric group in mind. Recently, the “amplituhedron” was introduced in the study of scattering amplitudes in N=4 super Yang Mills. I will talk about a formula for the cohomology class of a (tree) amplituhedron variety as the truncation of an affine Stanley symmetric function.

Two combinatorial applications of the Aleksandrov-Fenchel inequalities;

(7)  Two combinatorial applications of the Aleksandrov-Fenchel inequalitiesJ. Combinatorial Theory (A) 31 (1981), 56-65. In this amazing paper Stanley used inequalities of classical convexity to settle an important conjecture on probability of events in partially ordered sets. A special case of the conjecture was settled earlier by Ron Graham using the FKG inequality. The profound relation between classical convexity inequalities, combinatorial structures, polytopes, and probability theory was further studied by many authors including Stanley himself and there is much more to be done. I see that I ran out of my seven designated slots. Certainly you should read Richard’s combinatorial constructions of polytopes, like Two poset polytopesDiscrete Comput. Geom. 1 (1986), 9-23, and his papers on arrangements. Let me mention a more recent paper of Stanley in this general area:   A polytope related to empirical distributions, plane trees, parking functions, and the associahedron (with J. Pitman)Discrete Comput. Geom.27 (2002), 603-634.

More

(Mostly from RS’s homepage.)

Chess and Mathematics

(12 page  PDF file) An excerpt (version of 1 November 1999) from a book Richard is writing with Noam Elkies.

An unusual method for proving the Riemann hypothesis.

Professor Eubanks in Zetaland

Richard the Catalan

(From RS’s homepage) Excerpt (27 page PDF file) from EC2  on problems related to Catalan numbers (including 66 combinatorial interpretations of these numbers). Solutions to Catalan number problems from the previous link (23 page PDF file). Catalan addendum (Postscript or PDF) (version of 25 May 2013; 96 pages). An addendum of new problems (and solutions) related to Catalan numbers. Current number of combinatorial interpretations of Cn207. The material on Catalan numbers is being collected into a monograph, to be published by Cambridge University Press in late 2014 or early 2015.

Influence, Threshold, and Noise

My dear friend Itai Benjamini told me that he won’t be able to make it to my Tuesday talk on influence, threshold, and noise, and asked if I already have  the slides. So it occurred to me that perhaps I can practice the lecture on you, my readers, not just with the slides (here they are) but also roughly what I plan to say, some additional info, and some pedagogical hesitations. Of course, remarks can be very helpful.

I can also briefly report that there are plenty of exciting things happening around that I would love to report about – hopefully later in my travel-free summer. One more thing: while chatting with Yuval Rabani and Daniel Spielman I realized that there are various exciting things happening in algorithms (and not reported so much in blogs). Much progress has been made on basic questions: TSP, Bin Packing, flows & bipartite matching, market equilibria, and k-servers, to mention a few, and also new directions and methods. I am happy to announce that Yuval kindly agreed to write here an algorithmic column from time to time, and Daniel is considering contributing a guest post as well.

The second AMS-IMU meeting

Since the early 70s, I have been a devoted participants in our annual meetings of the Israeli Mathematical Union (IMU), and this year we will have the second joint meeting with the American Mathematical Society (AMS). Here is the program. There are many exciting lectures. Let me mention that Eran Nevo, this year Erdős’ prize winner, will give a lecture about the g-conjecture. Congratulations, Eran! Among the 22 exciting special sessions there are a few related to combinatorics, and even one organized by me on Wednsday and Thursday.

 Combinatorics Contact person: Gil Kalai, gil.kalai@gmail.com TAU, Dan David building, Room 103 Wed, 10:50-11:30 Van H. Vu (Yale University) Real roots of random polynomials (abstract) Wed, 11:40-12:20 Oriol Serra (Universitat Politecnica de Catalunya, Barcelona) Arithmetic Removal Lemmas (abstract) Wed, 12:30-13:10 Tali Kaufman (Bar-Ilan University) Bounded degree high dimensional expanders (abstract) Wed, 16:00-16:40 Rom Pinchasi (Technion) On the union of arithmetic progressions (abstract) Wed, 16:50-17:30 Isabella Novik (University of Washington, Seattle) Face numbers of balanced spheres, manifolds, and pseudomanifolds (abstract) Wed, 17:40-18:20 Edward Scheinerman (Johns Hopkins University, Baltimore) On Vertex, Edge, and Vertex-Edge Random Graphs (abstract) Thu, 9:20-10:00 Yael Tauman Kalai (MSR, New England) The Evolution of Proofs in Computer Science (abstract) Thu, 10:10-10:50 Irit Dinur (Weitzman Institute) Lifting locally consistent solutions to global solutions (abstract) Thu, 11:00-11:40 Benny Sudakov (ETH, Zurich) The minimum number of nonnegative edges in hypergraphs (abstract)

And now for my own lecture.