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

1office08

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

Please do not answer this poll if you already knew the answer

This poll is to learn how many people already knew the answer before. Please please answer.

As always comments are welcome!

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

nogauriirit

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!

noga240-1noga240-2240z240e240j240l

 

 

 

 

Ehud Friedgut: Blissful ignorance and the Kahneman-Tversky paradox

AmosDannyGili

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

tversky kaneman

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.

Continue reading

In And Around Combinatorics: The 18th Midrasha Mathematicae. Jerusalem, JANUARY 18-31

17.8.14 midrasha poster 2015 (1)

 

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

hands1

to this position

hands2

without simply rotating your hand.

Here are two video-demonstrations by some HUJI top people

parallel trasposrt

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.

Media Item from “Haaretz” Today: “For the first time ever…”

SKOREA-SCIENCE-MATHEMATICS-AWARD  אי־אף־פי

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. 

הארץ

haaretz