## Test your intuition 24: Which of the following three groups is trivial

Martin Bridson

We have three finitely presented groups

A is generated by two generators a and b and one relation  $a^{-1} \cdot b\cdot a = b^2$

B is generated by three generators a, b, c and three relations $a^{-1} \cdot b\cdot a = b^2$,  $b^{-1}\cdot c\cdot b = c^2,$  $c^{-1}\cdot a\cdot c = a^2$.

C is generated by four generators a, b, c, d and four relations $a^{-1} \cdot b\cdot a = b^2$,  $b^{-1}\cdot c\cdot b = c^2,$  $c^{-1}\cdot d\cdot c = d^2$, and $d^{-1}\cdot a \cdot d = a^2$.

Test your intuition: which of the groups A, B or C is trivial

Update: I did not know the answer (and I feel now better about it).

## School Starts at HUJI

We are now starting the third week of the academic year at HUJI. As usual, things are very hectic, a lot of activities in the mathematics department, in our sister CS department, around in the campus, and in our combinatorics group. A lot is also happening in other universities around. This semester I am teaching a course on “Social Choice and some Topics from Cooperative Game Theory” in our Federmann Center for the Study of Rationality. I will probably create a page for the course in the near future. During the summer we ran an informal multi-university research activity on analysis of Boolean functions where for two months we met every week for a whole day. I will try to report on what we were studying  and we will probably meet during the academic year 2-3 times each semester.

A few of many future events: Later this month we will have here a cozy Polish-Israeli meeting on  topological combinatorics, on December we will celebrate Ilya Rips 65 birthday with a conference on  geometric and combinatorial group theory, and at the last two weeks of January our traditional The 18th yearly midrasha (school) in mathematics that will be devoted to combinatorics with six lecture series and a few additional talks aimed at teaching some of the very latest exciting developments. If you did not register yet to the Midrasha, please go ahead and do so. This can be a very nice opportunity to visit Israel and learn some exciting combinatorics and to meet people. Partial support for travel and local expenses is available.

COMBSEM – weeks I, II, III

Our weekly combinatorics seminar is meeting on Mondays 9-11. Let me tell you a little on what we had in the first two weeks and what is planned for the third.

Week I:  A startling extension of the associahedron

Monday, October 27, 11:00–13:00, at room B221 in Rothberg building
(new CS and engineering building).

Speaker: Jean-Philippe Labbé, HU

Title: A construction of complete multiassociahedric fans

Abstract:
Originally, Coxeter groups emerged as an algebraic abstraction of
groups generated by reflections in a vector space. The relative
generality of their definition allows them to be related to many
combinatorial, geometric and algebraic objects. This talk show cases
recent developments in the study of a family of simplicial spheres
describing multi-triangulations of convex polygons based on
combinatorial aspects of Coxeter groups of type A. This family of
simplicial spheres generalizes the associahedra. A conjecture of
Jonsson (2003) asserts that these simplicial spheres can be realized
geometrically as the boundary complex of a convex polygon, that would
be thus called multiassociahedron. We will describe a
construction method to obtain complete simplicial fans realizing an
infinite non-trivial family of multi-associahedra.  At it turned out,  Jonsson’s conjecture is closely related to a conjecture by Miller and Knudson.
This is joint work with Nantel Bergeron and Cesar Ceballos (Fields
Institute and York Univ.).

Week II: Finally, progress on Withenhausen’s problem in 2 dimension

Speaker: Evan deCorte, HU

Title: Spherical sets avoiding a prescribed set of angles

Abstract: Let X be any subset of the interval [-1,1]. A subset I of
the unit sphere in $R^n$ will be called X-avoiding if <u,v> is not in X
for any u,v in I. The problem of determining the maximum surface
measure of a {0}-avoiding set was first stated in a 1974 note by H.S.
Witsenhausen; there the upper bound of 1/n times the surface measure
of the sphere is derived from a simple averaging argument. A
consequence of the Frankl-Wilson theorem is that this fraction
decreases exponentially, but until now the 1/3 upper bound for the
case n=3 has not moved. We improve this bound to 0.313 using an
approach inspired by Delsarte’s linear programming bounds for codes,
combined with some combinatorial reasoning. In the second half of the
talk, we turn our attention to the following question: Does there
exist an X-avoiding subset of the unit sphere maximizing the surface
measure among all X-avoiding subsets? (Or could there be a supremum
measure which is never attained as a maximum?) Using a combination of
harmonic and functional analysis, we show that a maximizer must exist
when n is at least 3, regardless of X. When n=2, the existence of a
maximizer depends on X; sometimes it exists, sometimes it does not.
This is joint work with Oleg Pikhurko.

Week III (coming up tommorow): Ramsey numbers for cliques vs cubes conquered at last!

Speaker: Gonzalo Fiz Pontiveros, HU

Title:  The Ramsey number of the clique and the hypercube

Abstract:
The Ramsey number $r(K_s,Q_n)$ is the smallest positive integer N
such that every red-blue colouring of the edges of the complete graph
$K_N$ on N vertices contains either a red n-dimensional hypercube,
or a blue clique on s vertices. It was conjectured in 1983 by
Erdos and Burr that $r(K_s,Q_n)=(s-1)(2^{n}-1)+1$ for every
positive integer s and every sufficiently large n. The aim of the
talk is to give an overview of the proof of this result and, if time
allows it, discuss some related problems.

Joint work with S. Griffiths, R.Morris, D.Saxton and J.Skokan.

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

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.

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

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

# 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