You have a box with n red balls and n blue balls. You take out balls one by one at random until left only with balls of the same color. How many balls will be left (as a function of n)?

1) Roughly  εn for some ε>0.

2) Roughly $\sqrt n$?

3) Roughly log n?

4) Roughly a constant?

Here is the collective intuition regarding this problem

## Itai Ashlagi, Yashodhan Kanoria, and Jacob Leshno: What a Difference an Additional Man makes?

We are considering the stable marriage theorem. Suppose that 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?

Boris Pittel proved that on average a man will be matched to the woman in place log n on his list. (Place one is his most preferred woman.) A woman will be matched on average to a man ranked n/log n on her list.

We asked in the post “Test your intuition (19)”  what is the situation if there is one additional man, and men are still proposing. This question is based on a conversation with Jacob Leshno who told me about a remarkable paper Unbalanced random matching markets by Itai Ashlagi, Yash Kanoria, and Jacob Leshno. Continue reading

## 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.

## The Mystery Piano-Player at the Mittag-Leffler Institute

In a previous post I told you about my Mittag-Leffler 2005 experience, and challenged you, readers, to discover the identity of a mysterious piano player. Coming from Yale, I was jet-lagged, an experience which already worked for me once in 1991 when I visited the
Mittah-Leffler institute and  was exploring subexponential variants of the simplex algorithm. In 2005, I came every day to my office at a very early hour in the morning and started working on quantum fault-tolerance.  And very early in the morning somebody was already at the piano. Who was playing the piano for me in the Mittag-Leffler Institute?

Hearing the piano and realizing who my private pianist was on these early mornings reminded me of a very cheerful song that we used to sing in my wife’s family gatherings. The song was introduced by uncle Shimon, husband of my-mother-in-law’s sister Rachel, and he took the lead role.

Shimon start singing: “And what are we going to eat at this feast?”
and we all joined: “A whale and a wild ox, we are going to eat, a whale and a wild ox!”

Wild ox and whale are not kosher (Update: so I, naively, thought), but comprise of the menu of the righteous people in heaven. This was indeed a very cheerful death-defiant song that went on like this:

“And what are we going to drink at this feast?” and we all replied: “Reserve wine, we will drink, reserve wine we will drink, and a whale and wild ox we will eat at this feast!”

And it continued:

“And who is going to taech us the words of the Torah?
Moses our rabbi! Yes, Moses our rabbi is going to teach us the words of the Torah, reserve wine we will drink, and a whale and wild ox we will eat at this feast.

And who is going to tell us words of wisdom at this feast? King Solomon! Yes King Solomon will tell us words of wisdom; Moses our rabbi is going to teach us the words of the Torah, reserve wine we will drink, and a whale and wild ox we will eat at this feast.

And who is going to dance for us, at this feast?
Deborah the prophet! Yes, Deborah the prophet is going to dance for us! King Solomon will tell us words of wisdom; Moses our rabbi is going to teach us the words of the Torah, reserve wine we will drink, and a whale and wild ox we will eat at this feast!

And who is going to play music for us at this feast? King David is going to play music for us at this feast!  Deborah the prophet is going to dance for us! King Solomon will tell us words of wisdom; Moses our rabbi is going to teach us the words of the Torah, reserve wine we will drink, and a whale and wild ox we will eat at this feast!”

Here it is in Hebrew:

ומה נאכל בארוחה זו? שור הבר לוויתן! שור הבר לוויתן נאכל בארוחה זו

ומה נשתה הארוחה זו? יין המשומר! יין המשומר נשתה , שור הבר לוויתן נאכל, בארוחה זו

ומי יאמר לנו דברי תורה בארוחה זו? משה רבנו! משה רבנו יאמר לנו דברי תורה, יין המשומר נשתה , שור הבר לוויתן נאכל, בארוחה זו

ומי יגיד לנו דברי חכמה בארוחה זו? שלמה המלך! שלמה המלך יגיד לנו דברי חכמה, משה רבנו יאמר לנו דברי תורה, יין המשומר נשתה , שור הבר לוויתן נאכל, בארוחה זו

ומי ינגן לנו בארוחה זו? דוד המלך! דוד המלך ינגן לנו, דבורה הנביאה תרקד לנו, שלמה המלך יגיד לנו דברי חכמה, משה רבנו יאמר לנו דברי תורה, יין המשומר נשתה , שור הבר לוויתן נאכל, בארוחה זו

ומי ישמח איתנו בארוחה זו? כל המסובין! כל המסובין ישמחו איתנו, דוד המלך ינגן לנו,  דבורה הנביאה תרקד לנו, שלמה המלך יגיד לנו דברי חכמה, משה רבנו יאמר לנו דברי תורה, יין המשומר נשתה , שור הבר לוויתן נאכל, בארוחה זו

The person who was playing the piano at six o’clock in the morning at the Mittag-Leffler institute was not King David, but rather

Posted in Music, Poetry | Tagged | 7 Comments

## QSTART

Physics, Computer Science, Mathematics, and Foundations’
views on quantum information

Inauguration conference for the Quantum Information Science Center (QISC),
Hebrew university of Jerusalem

Update: The news of our conference have made it to a big-league blog.

Update (July 2013): QStart was a very nice event- there were many interesting talks, and the speakers made the effort to have lectures accessible to the wide audience while discussing the cutting edge and at times technical matters.Streaming video of the talks is now available.

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

### 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.

## Test Your Intuition (18): How many balls will be left when only one color remains?

(Thanks to Itai Benjamini and Ronen Eldan.) Test (quickly) your intuition:  You have a box with n red balls and n blue balls. You take out balls one by one at random until left only with balls of the same colour. How many balls will be left (as a function of n)?

1) Roughly  εn for some ε>0.

2) Roughly $\sqrt n$?

3) Roughly log n?

4) Roughly a constant?

## Another Forgotten Bet: Is Don Zagier About to Owe Me 1000 Shekels For The Proof of the ABC Conjecture?

Like everybody else I heard with great interest the news about the attempted solution of the ABC conjecture by Shinichi Mochizuki. (See, e.g.,  herehere, here, and here.) I did not think that this has much to with me until I discovered yesterday in my room the following remarkable document from 1999.

A bet

If the ABC conjecture is proved Professor Zagier will pay G. Kalai 1000 (one thousand)  Isreali Shekels. Professor Zagier received 1 shekel in advance from G. Kalai.

Signed August 31, 1999, Tel Aviv

Don Zagier

ABC conjecture: $a+b+c=0_{(a,b)=1}\Rightarrow\prod_{p |abc}p\gg_{\epsilon}c^{1-\epsilon}$

Witnesses:  Noga Alon  Laszló Lovász

***

Amazing! I almost forgot about the whole thing, but now all left to say is:

# Go  Shinichi  Go!

Posted in Number theory, Rationality | | 8 Comments

## Erdős’ Birthday

Paul 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!

Posted in Combinatorics | Tagged | 3 Comments

## My Quantum Debate with Aram III

This is the third and last post giving a timeline and some non technical highlights from my debate with Aram Harrow.

### Where were we

After Aram Harrow and I got in touch in June 2011, and decided to have a blog debate towards the end of 2011, the first post in our debate describing my point of view was launched on January, 2012 and was followed by three posts by Aram. The discussion was intensive and interesting.  Here is a link to my 2011 paper that initiated the debate and to a recent post-debate presentation at MIT.

## Back to the debate: Conjecture C is shot down!

In addition to his three posts, Aram and Steve Flammia wrote a paper refuting one of my Conjectures (Conjecture C).  We decided to devote a post to this conjecture.

# Quantum refutations and reproofs

### Post 5, May 12, 2012. One of Gil Kalai’s conjectures refuted but refurbished

Niels Henrik Abel was the patron saint this time

The first version of the post started with this heartbreaking eulogy for Conjecture C. At the end most of it was cut away. But the part about Aram’s grandchildren was left in the post.

## Eulogy for Conjecture C

(Gil; old version:) When Aram wrote to me, inn June 2011, and expressed willingness to publicly discuss my paper, my first reaction was to decline and propose having just private discussions. Even without knowing Aram’s superb track record in debates, I knew that I put my beloved conjectures on the line. Some of them, perhaps even all of them, will not last. Later, last December, I changed my mind and Aram and I started planning our debate. My conjectures and I were fully aware of the risks. And it was Conjecture C that did not make it.

### A few words about Conjecture C

Conjecture C, while rooted in quantum computers skepticism, was a uniter and not a divider! It expressed our united aim to find a dividing line between the pre- and post- universal quantum computer eras.

### Aram’s grandchildren and the world before quantum computers

When Aram’s grandchildren will ask him: “
Grandpa, how was the world before quantum computers?” he could have replied: “I hardly remember, but thanks to Gil we have some conjectures recording the old days, and then he will state to the grandchildren Conjectures 1-4 and the clear dividing line in terms of Conjecture C, and the grandchildren will burst in laughter about the old days of difficult entanglements.” Continue reading