New Ramanujan Graphs!

margulis1

margulis2

Margulis’ paper

Ramanujan graphs were constructed independently by Margulis and by Lubotzky, Philips and Sarnak (who also coined the name). The picture above shows Margulis’ paper where the graphs are defined and their girth is studied. (I will come back to the question about girth at the end of the post.) In a subsequent paper Margulis used the girth property in order to construct efficient error-correcting codes. (Later Sipser and Spielman realized how to use the expansion property for this purpose.)

The purpose of this post is to briefly tell you about new Ramanujan graphs exhibited by Adam Marcus, Daniel Spielman, and Nikhil Srivastava. Here is the paper. This construction is remarkable for several reasons: First, it is the first elementary proof for the existence of Ramanujan graphs which also shows, for the first time, that there are k-regular Ramanujan graphs (with many vertices)  when k is not q+1, and q is a prime power. Second, the construction uses a novel “greedy”-method (with further promised fruits) based on identifying classes of polynomials with interlacing real roots, that does not lead (so far) to an algorithm (neither deterministic nor randomized). Third, the construction relies on Nati Linial’s idea of random graph liftings and verify (a special case of) a beautiful conjecture of Yonatan Bilu and Linial.  Continue reading

Andrei

andrei

Andrei Zelevinsky passed away a week ago on April 10, 2013, shortly after turning sixty. Andrei was a great mathematician and a great person. I first met him in a combinatorics conference in Stockholm 1989. This was the first major conference in combinatorics (and perhaps in all of mathematics) with massive participation of mathematicians from the Soviet Union, and it was a meeting point for east and west and for different areas of combinatorics. The conference was organized by Anders Björner who told me that Andrei played an essential role helping to get the Russians to come. One anecdote I remember from the conference was that Isreal Gelfand asked Anders to compare the quality of his English with that of Andrei. “Isreal”, told him Anders politely, “your English is very good, but I must say that Andrei’s English is a touch better.” Gelfand was left speechless for a minute and then asked again: “But then, how is my English compared with Vera’s?” In 1993, Andrei participated in a combinatorics conference that I organized in Jerusalem (see pictures below), and we met on various occasions since then. Andrei wrote a popular blog (mainly) in Russian Avzel’s journal. Beeing referred there once as an “esteemed colleague” (высокочтимым коллегой) and another time as  “Gilushka” demonstrates the width of our relationship.

Let me mention three things from Andrei’s mathematical work.

Andrei is famous for the Bernstein-Zelevinsky theory. Bernstein and Zelevinsky classified the irreducible complex representations of a general linear group over a local field in terms of cuspidal representations. The case of GL(2) was carried out in the famous book by Jacquet-Langlands, and the theory for GL(n) and all reductive groups was a major advance in representation theory.

The second thing I would like to mention is Andrei’s work with Gelfand and Kapranov on genaralized hypergeometric functions. To get some impression on the GKZ theory you may look at the BAMS’ book review of their book written by Fabrizio Catanese. This work is closely related to the study of toric varieties, and it introduced the secondary polytopes. The secondary polytopes is a polytope whose vertices correspond to (certain) triangulations of a polytope P. When P is a polygon then the secondary polytope is the associahedron (also known as the Stasheff polytope).

The third topic is  the amazing cluster algebras.  Andrei Zelevinsky and Sergey Fomin invented cluster algebras which turned out to be an extremely rich mathematical object with deep and important connections to many areas, a few are listed in Andrei’s short introduction (mentioned below): quiver representations, preprojective algebras, Calabi-Yau algebras and categories,  Teichmüller theory, discrete integrable systems, Poisson geometry, and we can add also,  Somos sequences, alternating sign matrices, and, yet again, to associahedra and related classes of polytopes. A good place to start learning about cluster algebras is Andrei’s article from the Notices of the AMS: “What is a cluster algebra.” The cluster algebra portal can also be useful to keep track. And here is a very nice paper with a wide perspective called “integrable combinatorics”  by Phillippe Di Francesco. I should attempt a separate post for cluster algebras.

Andrei was a wonderful person and mathematician and I will miss him.

jerusalem93 Andrei Jerusalem 33

Test Your Intuition (19): The Advantage of the Proposers in the Stable Matching Algorithm

Shapleygale

Stable mariage

The Gale-Shapley stable matching theorem and the algorithm.

GALE-SHAPLEY THEOREM Consider a society of n men and n women and suppose that every man [and every woman] have a preference (linear) relation on the women [men] he [she] knows. Then there is a stable marriage, namely a perfect matching between the men and the women so that there are no men and women which are not matched so that both of them prefer the other on their spouces.

Proof: Consider the following algorithm, on day 1 every man goes to the first woman on his list and every woman select the best man among those who come to her and reject the others. On the second day every rejected men go to the second woman on his list and every woman select one man from all man that comes to her (including the man she selected in the previous day if there was such a man) and rejects all others, and so on. This process will terminate after finitely many days and with a stable marriage! To see that the process terminate note that each day at least one man will come to a new women, or go back home after beeing rejected from every women (n+1 possibilities) and none of these possibilitie will ever repeat itself so after at most n^2+n days things will stabilize. When it terminates we have a stable marriage because suppose women W and men M are not married at the end. If M is married to a women he prefers less then W or to no women at all it means that M visited W and she rejected him so she had a better men than M.  Sababa!
It turns out that the above algorithm where the men are proposing and being rejected is optimal for the men! If a man M is matched to a woman W then there is not a single stable marriage where M can be matched to a woman higher on his list. Similarly this algorithm is worst for the women. But by how much?

Random independent preferences

Question 1:  There are n men and n women. If the preferences are random and men are proposing, what is the likely average women’s rank of their husbands, and what is the likely average men’s rank of their wives.

You can test your intuition, or look at the answer and for a follow up question after the fold.

Continue reading

Erdős’ Birthday

erdos-warsawPaul Erdős was born on March 26, 1913 2013 a hundred years ago. This picture (from Ehud Friedgut’s homepage) was taken in September ’96 in a Chinese restaurant in Warsaw, a few days before Paul Erdős passed away. The other diners are Svante Janson, Tomasz Łuczack and Ehud Friedgut. Erdős’ influence is felt everywhere in combinatorics, mathematics as a whole, and this blog as well. (A few more links: my most decorated MO answer is about Erdős, a recent heated discussion on the “two cultures in mathematics,” a new post on Erdős discrepancy problem on GLL,  and, most important, a link to Erdős centennial conference, in Budapest July 1-5, 2013. Join the celebration!)

Do not hesitate to contribute a comment!

F ≤ 4E

1. E ≤ 3V

Let G be a simple planar graph with V vertices and E edges. It follows from Euler’s theorem that

3V

In fact, we have (when V is at least 3,) that E 3V – 6.

To see this,  denote by F the number of regions or faces determined by G (in other words, the number of connected components in the complement of the embedded graph). Euler’s theorem asserts that

E – V + F = 2

V – E + F = 2

and now note that every face must have at least three edges and every edge is contained in two faces and therefore 2E \ge 3F, so 6=3V – 3E + 3F ≤ 3V – 3E +2E.

2. F  4E

Now let K be a two-dimensional simplicial complex and suppose that K can be embedded in R^4. Denote by E the number of edges of K and by F the number of 2-faces of K.

Here is a really great conjecture:

Conjecture:

4E

A weaker version which is also widely open and very interesting is:

For some absolute constant C,

C E

Remarks: The conjecture extends to higher dimensions. If K is an r-dimensional simplicial complex that can be embedded into R^{2r} then the conjecture is that

f_r(K) \le C_rf_{r-1}(K),

Where C_r is a constant depending on r.  Here f_i(K) is the number of i-dimensional faces of K. A stronger statement is that C_r= r+2. The conjecture also extends to polyhedral complexes and more general form of complexes. In the conjecture ’embed’ refers to a topological embedding.

Lionel Pournin found a combinatorial proof for Sleator-Tarjan-Thurston diameter result

I just saw in Claire Mathieu’s blog  “A CS professor blog” that a simple proof of the Sleator-Tarjan-Thurston’s diameter result for the graph of the associahedron was found by Lionel Pournin! Here are slides of his lecture “The diameters of associahedra” and link to the paper with the same title “The diameters of associahedra.” The original proof was based on hyperbolic volume computations and was quite difficult. (Here is an earlier post on the associahedron and an earlier mention of a connection found by Dehornoy with the Thompson group.)

Happy Birthday Ron Aharoni!

Ron Aharoni, one of Israel’s and the world’s leading combinatorialists celebrated his birthday last month. This is a wonderful opportunity to tell you about a few of the things that Ron did mainly around matching theory.

Menger’s theorem for infinite graphs

Hall’s marriage theorem

Hall marriage theorem (Philip Hall, 1935) gives a necessary and sufficient condition for a perfect matching in bipartite graphs. Suppose that you have a set A of n men and a set B of n women and a list of pairs of men and women that know each other. A perfect matching  is a bijection from A to B which matches every man to a woman he knows.

Hall’s marriage theorem asserts that a necessary and sufficient condition for a perfect matching is that every set S of men knows together at least |S| women.

This is an extremely important theorem and the starting point for a wonderful matching theory. It is a primary example of combinatorial duality. Other theorems of this kind are Menger’s theorem on connectivity in graphs, Dilworth’s theorem (1950) on covering posets with chains, the max-flow min-cut theorem (1956), and quite a few more.

Menger’s theorem

Menger Theorem (Karl Menger, 1927). Let G be a finite  graph and let x and y be two distinct vertices. Then the minimum number of edges whose removal disconnects x and is equal to the maximum number of pairwise edge-disjoint paths from x to y.

Infinite Menger

Ron Aharoni and Eli Berger proved the following theorem (here is a link to the arxived version):

Aharoni and Berger Theorem (2005): Given two sets of vertices, A and B, in a (possibly infinite) digraph, there exists a family P of disjoint A to B paths, and a separating set consisting of the choice of precisely one vertex from each path in P.

Continue reading

The Quantum Debate is Over! (and other Updates)

Quid est noster computationis mundus?

Nine months after is started, (much longer than expected,) and after eight posts on GLL, (much more than planned,)  and almost a thousand comments of overall good quality,   from quite a few participants, my scientific debate with Aram Harrow regarding quantum fault tolerance is essentially over. Some good food for thought, I hope. As always, there is more to be said on the matter itself, on the debate, and on other”meta” matters, but it is also useful to put it now in the background for a while, to continue to think about quantum fault tolerance in the slow pace and solitude, as I am used to, and also to move on in other fronts, which were perhaps neglected a little.

Here are the links to the eight posts: My initial post “Perpetual Motion of The 21st Century?” was followed by three posts by Aram. The first “Flying Machines of the 21st Century?” the second “Nature does not conspire” and the third “The Quantum super-PAC.” We had then two additional posts “Quantum refutations and reproofs” and “Can you hear the shape of a quantum computer?.” Finally we had  two conclusion posts: “Quantum repetition” and “Quantum supremacy or quantum control?

EDP 22-27

We had six new posts on the Erdos Discrepancy Problem over Gowers’s blog (Here is the link to the last one EDP27). Tim contributed a large number of comments and it was interesting to follow his line of thought.  Other participants also contributed a few comments. One nice surprise for me was that the behavior of the hereditary discrepancy for homogeneous arithmetic progression in {1,2,…,n} was  found by Alexander Nikolov and  Kunal Talwar. See this post From discrepancy to privacy and back and the paper. Noga Alon and I showed that it is {\tilde{\Omega}(\sqrt{\log n})} and at most {n^{O(\frac{1}{\log\log n})}}, and to my surprise Alexander and Kunal showed that the upper bound is the correct behavior. The argument relies on connection with differential privacy.

Möbius randomness and computation

After the AC^0-prime number theorem was proved by Ben Green, and the Mobius randomness of all Walsh functions and monotone Boolean function was proved by Jean Bourgain, (See this MO question for details) the next logical step are low degree polynomials over Z/2Z . (The Walsh functions are degree 1 polynomials.) The simplest case offered to me by Bourgain is the case of the Rudin-Shapiro sequence. (But for an ACC(2) result via Razborov-Smolensky theorem we will need to go all the way to polynomial of degree polylog.) I asked it over MathOverflaw. After three months of no activity I offered a bounty of 300 of my own MO-reputations. Subsequently, Terry Tao and Ben Green discussed some avenues and eventually Tao solved the problem (and earned the 300 reputation points). Here is a very recent post on Möbius randomness on Terry Tao’s blog.

Influences on large sets

In my post Nati’s Influence I mentioned two old conjectures (Conjecture 1 dues to Benny Chor and Conjecture 2) about influence of large sets on Boolean functions. During Jeff Kahn’s visit to Israel we managed to disprove them both. The disproof is inspired by an old construction of Ajtai and Linial.

Tel Aviv, New Haven, Jerusalem

Last year we lived for a year in Tel Aviv which was a wonderful experience: especially walking on the beach every day and feeling the different atmosphere of the city. It is so different from my Jerusalem and still the people speak fluent Hebrew. I am now in New Haven. It is getting cold and the fall colors are getting beautiful. And it also feels at home after all these years. And next week I return to my difficult and beautiful  (and beloved) Jerusalem.

Looking Again at Erdős’ Discrepancy Problem

Over Gowers’s blog Tim and I will make an attempt to revisit polymath5. Last Autumn I prepared three posts on the problems and we decided to launch them now. The first post is here. Here is a related MathOverflow question. Discrepancy theory is a wonderful theory and while I am not an expert we had several posts about it here. (This post on Beck-Fiala and related matters; and this news item on Beck’s 3-permutation conjecture.) I am aware of at least one important recent development in the theory that I did not report.  My posts go around the problem and do not attack it directly but I hope people will have a chance to think about the problem again and perhaps also about polymathing again. Meanwhile, polymath7 (over the polymath blog) is in a short recess but I hope a new research thread will start soon.

Tokyo, Kyoto, and Nagoya








Kalai-stanley

Near Nagoya: Firework festival; Kyoto: with Gunter Ziegler; with Takayuki Hibi, Hibi, Marge Bayer, Curtis Green and Richard Stanly; Tokyo: Peter Frankl; crowded crossing. Added later: Mazi and I at the same restaurant taken by Stanley.

I just returned from a trip to Japan to the FPSAC 2012 at Nagoya and a workshop on convex polytopes in Kyoto. As in my first visit to Osaka in 1999 I found Japan stunning, and this time I was able to share the experience with my wife.

Kyoto: The week before FPSAC there was a workshop at RIMS devoted to convex polytopes. Some highlights: A classical result by Venkov and McMullen characterizes polytopes whose translates tile the Euclidean d-space.  Sinai Robins talked about his work with Nick Gravin and Dima Shiryaev about k-tilings (every point is covered k times).  Not a full characterization yet but already some impressive results. Gunter Ziegler talked about his work with Karim Adiprasito disproving an old conjecture by Shephard which asserts that there are only finitely many projectively unique d-polytopes for every dimension d. This is false above dimension 81.  Eran Nevo talked about his solution with Satoshi Murai of the generalized lower bound conjecture and some subsequent works on triangulated manifolds. There were several talks relating Ehrhard polynomials of polytopes with enumerative combinatorics,  and several talks on algebraic geometry, toric varieties, Fano varieties, and mirror symmetry. Here are the slides of my lecture entitled open problems on convex polytopes I’d love to see solved (but some further explanations for some parts are needed). I hope to return to some of the topics of the workshop in a later post.

Nagoya: FPSAC (Formal power series and algebraic combinatorics) is a central annual  combinatorial meeting with special emphasis on enumerative and algebraic combinatorics. This year it was the 24th such event although I could have swear that I took part in an FPSAC in Montreal already in 1985 but apparently this was a conference with a similar flavor and different name. Much is going on in enumerative and algebraic combinatorics. Cluster algebras, miraculously discovered a decade ago by Fomin and Zelevinsky are going strong in combinatorics as well as in other areas. Alternating sign matrices continue to offer amazing problems and answers. There were quite a few lectures on representation theory, symmetric functions, random matrices, and also on relations of enumerative combinatorics with hyperplane arrangements with polytopes and with physics. There were lectures involving massive computations and new computerized method and packages for symbolic computations  were described. Here are the slides of my lecture entitled Discrete isoperimetry: problems, results, applications and methods. The program page now contains slides for most lectures.

What are alternating sign matrices?

I suppose that you all know what a permutation matrix is (an n by n matrix with 0,1 entries and one non zero entry in each row and each column) and alternating sign matrices are amazing generalization of permutation matrices discovered by William Mills, David Robbins, and Howard Rumsey. (See also this article by Bressoud and Propp) They are integral n by n matrices with 0,1 and -1 entries. In every row and every columns  the non zero aliments (and there must be at least one such element)  should alternate between 1 and -1 and start and end with a ‘1’. Alternating sign matrices are in one to one correspondence with monotone triangle. Thos are triangles of integers starting with a row: 1,2,…,n. With the following rules: (a) all rows are strictly increasing; (b) every element in row i is weakly between the two elements above it.

The amazing thing is that the number of alternating sign matrices of order n is precisely

1!4!7!…(3n-2)!/n!(n+1)!…(2n-1)!

This was a conjecture by Mills, Robbins and Rumsey and it took over a decade until it was proved by Doron Zeilberger. Later Greg Kuperberg found a short proof and by now several proofs are known. If you have some information or ideas on alternating sign matrices that you would like to share or some questions about them, or about anything else, please contribute a comment.