**With Ilan, my four month old grandson**

**A quick schematic road-map to these new geometric objects. The positroidron can be seen as a cellular structure on the nonnegative Grassmanian – the part of the real Grassmanian G(m,n) which corresponds to m by n matrices with all m by m minors non-negative. The cells in the cellular structure of the positroidron correspond to those matrices with the same (+,0) pattern for m by m minors. When m=1 we get a (spherical) simplex. When we project the positroidron using an n by k totally positive matrix we get for m=1 the cyclic polytope, and for general m the amplituhedron. When we project using general matrices we obtain general polytopes for m=1, and an interesting extension of polytopes proposed by Thomas Lam for general m.**

Alex Postnikov’s recent lectures series in our Midrasha was an opportunity to understand slightly better some remarkable combinatorial objects that drew much attention recently. Continue reading

The topological Tverberg conjecture (discussed in this post), a holy grail of topological combinatorics, was refuted! The three-page paper “Counterexamples to the topological Tverberg conjecture” by Florian Frick gives a brilliant proof that the conjecture is false.

The proof is based on two major ingredients. The first is a recent major theory by Issak Mabillard and Uli Wagner which extends fundamental theorems from classical obstruction theory for embeddability to an obstruction theory for r-fold intersection of disjoint faces in maps from simplicial complexes to Euclidean spaces. An extended abstract of this work is Eliminating Tverberg points, I. An analogue of the Whitney trick. The second is a result by Murad Özaydin’s from his 1987 paper Equivariant maps for the symmetric group, which showed that for the non prime-power case the topological obstruction vanishes.

It was commonly believed that the topological Tverberg conjecture is correct. However, one of the motivations of Mabillard and Wagner for studying elimination of higher order intersection was that this may lead to counterexamples via Özaydin result. Isaak and Uli came close but there was a crucial assumption of large codimension in their theory, which seemed to avoid applying the new theory to this case. It turned out that a simple combinatorial argument allows to overcome the codimension problem!

Florian’s combinatorial argument which allows to use Özaydin’s result in Mabillard-Wagner’s theory is a beautiful example of a powerful combinatorial method with other applications by Pavle Blagojević, Florian Frick and Günter Ziegler.

Both Uli and Florian talked about it here at Oberwolfach on Tuesday. I hope to share some more news items from Oberwolfach and from last week’s Midrasha in future posts.

Update (May, 2016): The combinatorial method of Blagojević, Frick and Ziegler was earlier and independently discovered by Gromov.

Posted in Combinatorics, Conferences, Convexity, Updates
Tagged Florian Frick, Issac Mabillard, Uli Wagner
2 Comments

**Tahl Nowik**

**Update 3 (January 30): **The midrasha ended today.** Update 2 (January 28): **additional videos are linked**; Update 1 (January 23):** Today we end the first week of the school. David Streurer and Peter Keevash completed their series of lectures and Alex Postnikov started his series.

___

Today is the third day of our winter school. In this page I will gradually give links to to various lectures and background materials. I am going to update the page through the two weeks of the Midrasha. Here is the web page of the midrasha, and here is the program. **I will also present the posters for those who want me to: simply take a picture (or more than one) of the poster and send me. And also – links to additional materials, pictures, or anything else: just email me, or add a comment to this post.**

Posted in Combinatorics, Conferences, Updates
1 Comment

Last week I took a bus from Tel Aviv to Jerusalem and I saw (from behind) a person that I immediately recognized. It was Nimrod Megiddo, from IBM Almaden, one of the very first to relate game theory with complexity theory, one of the pioneers of computational geometry, and one of the leaders in optimization and linear programming, the guy who (with Ehud Kalai) was the first to invited me to an international conference, and a fresh Laureate of the John von Neumann theory Prize. I did not see Nimrod more than a year after our last coincidental meeting at the Berkeley Simons Institute, I called over to him and he was happy to see me as I was happy to see him, and we found a place together at the back of the bus and caught up on things.

Nimrod showed me on the bus a picture he found in his house, taken by him at the 1974 game theory workshop in Bad Salzuflen, Germany. With Nimrod’s kind permission I present the picture here: (The copyright © belongs to Nimrod Megiddo who took the picture).

Here are some of the people left to right, (on some I already told you in other posts):

David Schmeidler (only beard visible)

Guillermo Owen

Lloyd Shapley

Sergiu Hart

Yair Tauman (only back shown)

Robert Aumann

Werner Güth (behind Aumann)

Reinhard Selten

Ehud Kalai (just to the right of Selten looking at the camera)

Gerhard Schwedihauer

Elon Kohlberg (only back shown, looking to the left)

William Lucas (in the back, looking at the wall)

Robert Weber (only hair and jacket visible)

Bezalel Peleg (looking to the right)

Joel Moulen (looking to the left)

Thomas Marschak (sunglasses and beard)

Michael Maschler

Joachim Rosenmüller (with glasses behind Maschler)

Kenjiro Nakamura

**Happy new 2015!**

Scott Aaronson wrote a new post on the Shtetl Optimized** reflecting on the previous thread (that I referred to in my post on Amy’s triumph), and on reactions to this thread. The highlight is a list of nine of Scott’s core beliefs. This is a remarkable document and I urge everybody to read it. Yes, Scott’s core beliefs come across as feminist! Let me quote one of them.

7. I believe that no one should be ashamed of inborn sexual desires: not straight men, not straight women, not gays, not lesbians, not even pedophiles (though in the last case, there might really be no moral solution other than a lifetime of unfulfilled longing). Indeed, I’ve always felt a special kinship with gays and lesbians, preciselybecausethe sense of having to hide from the world, of being hissed at for a sexual makeup that you never chose, is one that I can relate to on a visceral level. This is one reason why I’ve staunchly supported gay marriage since adolescence, when it was still radical. It’s also why the tragedy of Alan Turing, of his court-ordered chemical castration and subsequent suicide, was one of the formative influences of my life.

**!! (***)**

In the sacred tradition of arguing with Scott I raised some issues with #5 and 4# on Scott’s blog. Two of Scott’s points are on the subject of (young) people’s suffering by feeling unwanted, sexually invisible, or ashamed to express their desires.

I was pleased to see that those feminist matters that Scott and I disagree about, like the nature of prostitution, the role of feminist views in men’s (or nerdy men’s) suffering, and also Scott’s take on poverty, did not make it to Scott’s core beliefs.

Happy new year, everybody!

* The word triumph is used here (again) in a soft (non-macho) way characteristic to the successes of feminism. Voting rights for women did not exclude voting rights for men, and Scott’s triumph does not mean a defeat for any others; on the contrary.

** “Shtetl-optimized” is the name of Scott Aaronson’s blog.

*** In my opinion, when a person has an uncontrollable urge or strong temptation or desire to commit a crime towards another individual (or even to inflict much damage on another person when it is not criminal, or to commit other crimes), shame and guilt feelings can be instrumental in controlling such urges.

It was not until the 144th comment by a participants named Amy on Scott’s Aaronson recent Shtetl-optimized** post devoted to a certain case of sexual harassment at M. I. T. that the discussion turned into something quite special. Amy’s great comment respectfully disagreeing with the original post and most of the 100+ earlier comments gave a wide while personal feminist perspective on women in STEM (STEM stands for science, technology, engineering, mathematics). This followed by a moving comment #171 by Scott describing a decade of suffering from his early teens. Scott, while largely sympathetic with the feminist cause, sees certain aspects of modern feminism as major contributors to his ordeal.

Then came a few hundred comments by quite a few participants on a large number of issues including romantic/sexual relations in universities, rape, prostitution, poverty, gaps between individuals’ morality and actions, and much more. Many of the comments argued with Amy and a few even attacked her. Some comments supported Amy and some proposed their own views. Many of the comments were good and thoughtful and many gave interesting food for thought. Some people described interesting personal matters. As both Scott and Amy left school early to study in the university, I also contributed my own personal story about it (and Scott even criticized my teenage approach to life! 🙂 ). Amy, over 80+ thoughtful comments, responded in detail, and her (moderate) feminist attitude (as well as Amy herself) stood out as realistic, humane, and terribly smart.

* The word triumph is used here in a soft (non-macho) way characteristic to the successes of feminism. Voting rights for women did not exclude voting rights for men, and Amy’s triumph does not mean a defeat for any others; on the contrary.

** “Shtetl-optimized” is the name of Scott Aaronson’s blog.

Posted in Controversies and debates, Women in science
Tagged Amy, feminism, Shtetl-optimized
23 Comments

**Ilya Rips and me during Ilyafest last week** (picture Itai Benjamini)

Last week we had here a celebration for Ilya Rips’ birthday. Ilya is an extraordinary mathematician with immense influence on algebra and topology. There were several startling ongoing mathematical projects that he is involved with that were discussed. One is a very ambitious project with Alexei Kanel-Belov is to get a “small cancellation theory” for rings and this has already fantastic consequences. Another is a work with Yoav Segev and Katrin Tent, on sharply 2- transitive groups, that answered a major old question with connections to groups, rings, and geometry. **Happy birthday, Ilya!**

Reviel Netz (רויאל נץ) gave a seminar lecture in the department about infinity in Archimedes’ mathematical thoughts that developed into an interesting conversation. The lecture took place a day after Netz’s second poetry book (in Hebrew) appeared.

Two weeks with extensive illuminating lecture series. Do not miss!

On our Monday combinatorics seminar, we had, since my last report, three excellent lectures. And next Monday we are having Avi Wigderson.

**Dec 1**

Speaker: **Sonia Balagopalan,** HU

Title: **A 16-vertex triangulation of the 4-dimensional real projective space **

When can we properly color the vertices of a graph with a few colors? This is a notoriously difficult problem. Things get a little better if we consider simultaneously a graph together with all its induced subgraphs. Recall that an induced subgraph of a graph *G* is a subgraph formed by a subset of the vertices of *G* together with all edges of *G* spanned on these vertices. An induced cycle of length larger than three is called a *hole, *and an induced subgraph which is a complement of a cycle of length larger than 3 is called an* anti-hole*. As usual, is the chromatic number of *G* and is the clique number of *G* (the maximum number of vertices that form a complete subgraph. Clearly, for every graph *G*

.

**Question 1:** Describe the class of graphs closed under induced subgraphs, with the property that for every .

A graph *G* is called **perfect **if for every induced subgraph *H* of *G*. So Question 1 asks for a description of perfect graphs. The study of perfect graphs is among the most important areas of graph theory, and much progress was made along the years.

Interval graphs, chordal graphs, comparability graphs of POSETS , … are perfect.

Two major theorems about perfect graphs, both conjectured by Claude Berge are:

**The perfect graph theorem (Lovasz, 1972): **The complement of a perfect graph is perfect

**The strong perfect graph theorem (Chudnovsky, Robertson, Seymour and Thomas, 2002): **A graph is perfect if and only if it does not contain an odd hole and an odd anti-hole.

There are triangle-free graphs with arbitrary large chromatic numbers. An important construction by Mycielski goes as follows: Given a triangle graph *G* with *n* vertices create a new graph *G’* as follows: add *n* new vertices and a vertex w. Now add w to each and for every i and j for which and are adjacent add also an edge between and (and thus also between and .)

**Question 2**: Describe classes of graphs closed under induced subgraphs with bounded chromatic numbers.

Here are three theorems in this direction. The first answers affirmatively a conjecture by Kalai and Meshulam. The second and third prove conjectures by Gyarfas.

**The Trinity graph theorem (Bonamy, Charbit and Thomasse, 2013): **Graphs without induced cycles of length divisible by three have bounded chromatic numbers.

(The paper: Graphs with large chromatic number induce *3k*-cycles.)

**Theorem (Scott and Seymour, 2014):** Triangle-free graphs without odd induced cycles have bounded chromatic number.

(The paper: Coloring graphs with no odd holes.)

%d bloggers like this: