## A lecture by Noga

Noga with Uri Feige among various other heroes

A few weeks ago I devoted a post to the 240-summit conference for Péter Frankl, Zoltán Füredi, Ervin Győri and János Pach, and today I will bring you the slides of Noga Alon’s lecture in the meeting. Noga is my genious twin academic brother – we both were graduate students under the supervision of Micha A. Perles in the same years and we both went to MIT as postocs in fall 1983.  The lecture starts with briefly mentioning four results by the birthday boys related to combinatorics and geometry and continues with recent startling results by Alon, Ankur Moitra, and Benny Sudakov. One out of many contributions of Noga over the years is building a large infrastructure of constructions and examples, often very surprising,  in combinatorics, graph theory, information theory,TOC, and related areas. And the new results add to this infrastructure. The slides are very clear. Enjoy!

## Ehud Friedgut: Blissful ignorance and the Kahneman-Tversky paradox

Tversky, Kahneman, and Gili Bar-Hillel (WikiPedia). Taken by Maya Bar-Hillel at Stanford, summer 1979.

The following post was kindly contributed by Ehud Friedgut.

During the past week I’ve been reading, and greatly enjoying Daniel Kahneman’s brilliant book “Thinking fast and Slow”.

One of the most intriguing passages in the book is the description of an experiment designed by Kahneman and Tversky which exemplifies a judgmental flaw exhibited by many people, which supposedly indicates an irrational, or inconsistent behavior. I will describe their experiment shortly.
I still remember the first time I heard of this experiment, it was related to me over lunch in Princeton by Noga Alon. Returning to this problem, 15 years later, I still, as in my initial exposure to the problem, made the “inconsistent” choice made by the vast majority of the subjects of the study. In this post I wish to argue that, in fact, there is nothing wrong with this choice.

Before relating their experiment, let me suggest one of my own. Imagine, if you will, that you suffer from gangrene in one of your toes. The doctor informs you that there is a 20% chance that it is “type A” gangrene, in which case you can expect spontaneous healing. There is a 75% chance that it is type B, in which case you will have to amputate it, and a 5% chance that it is type C. In the last case there is a shot you can be given that will save your toe, but it will cost you 2000$. What would you do? I would probably not take the shot. My guiding principle here is that I hate feeling stupid, and that there’s a pretty good chance that if I take the shot I’ll walk around for the rest of my life, not only minus one toe and 2000$, but also feeling foolish for making a desperate shot in the dark.
Now, say I declined the shot, and I return after a week, and the doctor sees that the condition has worsened and that he will have to amputate the toe. He asks me if I wish (say for no cost) that he send the amputated toe for a biopsy, to see if it was type B or C. Here my gut reaction, and I’m sure yours too, is a resounding no. But even when thinking it over more carefully I still think I would prefer not to know. The question is which is better:
Option 1) I have a 75/80 probability of having a clean conscience, and a 5/80 chance of knowing clearly for the rest of my life that I’m lacking a toe because I’m what’s known in Yiddish as an uber-chuchem (smart aleck).
Option 2) Blissful ignorance: for the rest of my life I enjoy the benefit of doubt, and know that there’s only a 5/80 chance that the missing toe was caused by my stinginess.
I prefer option 2. I’m guessing that most people would also choose this option. I’m also guessing that Kahenman and Tversky would not label this as an irrational or even an unreasonable choice. I’m almost positive they wouldn’t claim that both options are equivalent.

Now, back to the KT experiment. You are offered to participate in a two stage game. In the first stage 75% of the participants are eliminated at random. At the second stage, if you make it, you have two choices: a 100% chance of winning 30$or an 80% chance of winning 45$. But you have to decide before stage one takes place.
What would you choose?
I’ll tell you what I, and the majority of the subjects of the study do. We choose the 30$. Here’s my reasoning: 30$ is pretty nice, I can go for a nice lunch, 45$would upgrade it, sure, but I would feel really bad if I ended up with nothing because I was greedy. Let’s stick to the sure thing. Now a different experiment: you have to choose between 20% chance of gaining 45$, or a 25% chance of gaining 30$. What do you choose? Once again, I chose what the majority chose: I would now opt for the 45$. My reasoning? 20% sounds pretty close to 25% to me, the small difference is worthwhile for a 50% gain in the prize.

O.k., I;m sure you all see the paradox. The two games are identical. In both you choose between a 20% chance of 45$and a 25% chance of 30$. My reference to “a sure thing” represented a miscomprehension, common to most subjects, who ignored the first stage in the first game. Right?

No, wrong. I think the two games are really different, just as the two options related to the gangrene biopsy were different.
It is perfectly reasonable that when imagining the first game you assume that you are told whether you proceed to the second stage or not, and only if you proceed you are then told, if you chose the 80% option, whether you were lucky.
In contrast, in the second game, it is reasonable to assume that no matter what your choice was, you are just told whether you won or not.
Of course, both games can be generated by the same random process, with the same outcome (choose a random integer between 1 and 100, and observe whether it’s in [1,75], [76,95] or [96,100] ), but that doesn’t mean that when you chose the 45$option and lose you always go home with the same feeling. In game 1 if you chose the risky route you have a 75% probability of losing and knowing that your loss has nothing to do with your choice, and a 5% chance of kicking yourself for being greedy. In game 2 you have a 80% chance of losing, but enjoying the benefit of doubt, knowing that there’s only a 5/80 chance that the loss is your fault. Of course, my imagination regarding the design of the games is my responsibility, it’s not given explicitly by the original wording, but it certainly is implicit there. I maintain that there is nothing irrational about trying to avoid feeling regret for your choices, and that I would really stick to the “paradoxical” combination of choices even in real life, after fully analyzing the probability space in question. For those of you reading this blog who don’t know me, I’m a professor of mathematics, and much of my research has to do with discrete probability. That doesn’t mean that I’m not a fool, but at least it gives me the benefit of doubt, right? ======================================================== O.k., now, here’s part two of my post – after finishing the book. Posted in Guest blogger, Rationality | | 8 Comments ## In And Around Combinatorics: The 18th Midrasha Mathematicae. Jerusalem, JANUARY 18-31 The 18th yearly school in mathematics is devoted this year to combinatorics. It will feature lecture series by Irit Dinur, Joel Hass, Peter Keevash, Alexandru Nica, Alexander Postnikov, Wojciech Samotij, and David Streurer and additional activities. As usual grants for local and travel expences are possible. ## Mathematical Gymnastics For the long days of ICM 2014 lectures, and long flights to and from Seoul, some mathematical gymnastics is needed. And this is precisely what Omer Angel taught us in his recent visit. Combining gymnastic with a demonstration of parallel transport and deep insights on human physiology! You want to move from this position to this position without simply rotating your hand. Here are two video-demonstrations by some HUJI top people Click on the picture to see the video. (The drill is a sequence of five moves and the video skipped the first.) Some other mathematical gymnastics is demonstrated in the post the ultimate riddle. And for a futurist mathematical application to sport (soccer) see this post. Posted in Sport | | 2 Comments ## Media Item from “Haaretz” Today: “For the first time ever…” Maryam Mirzakhani received the medal from South Korea’s president Park Geun-hye. Here is an article from today’s Israeli newspaper Haaretz. It is based on this article by the Guardian (Thanks, Manor!). See also this post on Laba’s accidental mathematician and John Baez’ Google+ post. The ICM 2014 started today in Seoul. The International congress taking place once every four years is an exciting event, celebrated by thousands of mathematicians in Seoul and many others all over the world. The opening ceremonies came with the announcement of Artur Avila, Manjul Bhargava, Martin Hairer, and Maryam Mirzakhani as 2014 Fields medalist, Subhash Khot won the Nevanlinna prize, Stanley Osher won the Gauss prize and Phillip Griffiths is the Chern medalist, and Adrián Paenza won the Leelavati Prize. Heartly congratulations to Artur, Manjul, Martin, Maryam, Subhash, Stanley, Phillip, and Adrián! This is also the first for Brazil, Austria, Canada, and Iran! More on the Fields medalists works can be found on Terry Tao’s blog. (New) And here is a live bloging (with pictures) on ICM2014 day 1 from Gowers’s blog. And also here from the ICM site on the work of all prize recipients. And from Quanta Magazine: (More) More on Osher, Griffiths, and Khot on terry Tao’s blog, on Khot on Scott Aaronson’s blog and on a description of the laudations on Gowers blog. ## Jim Geelen, Bert Gerards, and Geoﬀ Whittle Solved Rota’s Conjecture on Matroids Gian Carlo Rota ## Rota’s conjecture I just saw in the Notices of the AMS a paper by Geelen, Gerards, and Whittle where they announce and give a high level description of their recent proof of Rota’s conjecture. The 1970 conjecture asserts that for every finite field, the class of matroids representable over the field can be described by a finite list of forbidden minors. This was proved by William Tutte in 1938 for binary matroids (namely those representable over the field of two elements). For binary matroids Tutte found a single forbidden minor. The ternary case was settled by by Bixby and by Seymour in the late 70s (four forbidden minors). Geelen, Gerards and Kapoor proved recently that there are seven forbidden minors over a field of four elements. The notices paper gives an excellent self-contained introduction to the conjecture. This is a project that started in 1999 and it will probably take a couple more years to complete writing the proof. It relies on ideas from the Robertson-Seymour forbidden minor theorem for graphs. Congratulations to Jim, Bert, and Geoff! Well, looking around I saw that this was announced in August 22’s post in a very nice group blog devoted by matroids- Matroid Union, with contributions by Dillon Mayhew, Stefan van Zwam, Peter Nelson, and Irene Pivotto. August 22? you may ask, yes! August 22, 2013. I missed the news by almost a year. It was reported also here and here and here, and here, and here, and here! This is a good opportunity to mention two additional conjectures by Gian-Carlo Rota. But let me ask you, dear readers, before that a little question. ## Rota’s unimodality conjecture and June Huh’s work Rota’s unimodality conjecture predicts that the coefficients of the characteristic polynomial of a matroid form a log-concave sequence. This implies that the coefficients are unimodal. A special case of the conjecture is an earlier famous conjecture (by Read) asserting that the coefficients of the chromatic polynomial of a graph are unimodal (and log-concave). This conjecture about matroids was made also around the same time by Heron and Welsh. June Huh proved Reads’ unimodality conjecture for graphs and the more general Heron-Rota-Welsh conjecture for representable matroids for characteristic 0. Later Huh and Eric Katz proved the case of representable matroids for arbitrary characteristics. I already mentioned these startling results earlier and we may come back to them later. Huh’s path to mathematics was quite amazing. He wanted to be a science-writer and accomponied Hironaka on whom he planned to write. Hironaka introduced him to mathematics in general and to algebraic geometry and this led June to study mathematics and a few years later to use deep connections between algebraic geometry and combinatorics to prove the conjecture. ## Rota’s basis conjecture Rota’s basis conjecture from the late 80’s appears to remain wide open. The problem first appeared in print in a paper by Rosa Huang and Rota. Here is a post about it also from “the matroid union.” It is the first problem in Rota’s article entitled “Ten Mathematics problems I will never solve“. Having access only to page one of the paper I can only guess what the other nine problems might be. Rota’s portrait by Fan Chung Graham Posted in Combinatorics, Open problems, Updates | | 6 Comments ## 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.) Posted in Uncategorized | 2 Comments ## Next Week in Jerusalem: Special Day on Quantum PCP, Quantum Codes, Simplicial Complexes and Locally Testable Codes # Special Quantum PCP and/or Quantum Codes: Simplicial Complexes and Locally Testable CodesDay ### 24 Jul 2014 – 09:30 to 17:00 ### 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(?) Posted in Conferences, Happy birthday | 3 Comments ## 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.

### 1. 1981 – we give different proofs for the Perles-Katchalski Conjecture

Posted in Combinatorics, Convex polytopes, Open problems | | 1 Comment