Two Delightful Major Simplifications

Arguably mathematics is getting harder, although some people claim that also in the old times parts of it were hard and known only to a few experts before major simplifications had changed  matters. Let me report here about two recent remarkable simplifications of major theorems. I am thankful to Nati Linial who told me about the first and to Itai Benjamini and Gady Kozma who told me about the second. Enjoy!

Random regular graphs are nearly Ramanujan: Charles Bordenave gives a new proof of Friedman’s second eigenvalue Theorem and its extension to random lifts

Here is the paper.

Abstract: It was conjectured by Alon and proved by Friedman that a random d-regular graph has nearly the largest possible spectral gap, more precisely, the largest absolute value of the non-trivial eigenvalues of its adjacency matrix is at most 2\sqrt{d-1} +o(1) with probability tending to one as the size of the graph tends to infinity. We give a new proof of this statement. We also study related questions on random n-lifts of graphs and improve a recent result by Friedman and Kohler.

A simple proof for the theorem of Aizenman and Barsky and of Menshikov. Hugo Duminil-Copin and Vincent Tassion give  a new proof of the sharpness of the phase transition for Bernoulli percolation on \mathbb Z^d

Here is the paper

Abstract: We provide a new proof of the sharpness of the phase transition for nearest-neighbour Bernoulli percolation. More precisely, we show that

– for p<p_c, the probability that the origin is connected by an open path to distance $n$ decays exponentially fast in $n$.

– for p>p_c, the probability that the origin belongs to an infinite cluster satisfies the mean-field lower bound \theta(p)\ge\tfrac{p-p_c}{p(1-p_c)}.

This note presents the argument of this paper by the same authors, which is valid for long-range Bernoulli percolation (and for the Ising model) on arbitrary transitive graphs in the simpler framework of nearest-neighbour Bernoulli percolation on \mathbb Z^d.

Election Day

Today is the general election day in Israel, the third since starting this blog (I-2009,and II-2013). This is an exciting day. For me election is about participation much more than it is about influence and I try not to miss it. This time, for the first time,  I publicly supported one political party “the Zionist camp” headed by Herzog and Livni. The last four posts written in Hebrew are related to my position. (The fourth one has a poll which expresses also some academic curiosity, and I plan one more post with a similar follow-up  but post-election poll. But then we go back to combinatorics and more)

The blog also has now a new appearance and the header is a picture from 1999 with Jirka Matousek, a great mathematician and a great person who enlightened our community and our lives in many ways and who passed away at a terribly young age last Tuesday.

זה הזמן לשינוי

זו הפעם החמש-עשרה שבה אצביע והפעם השלישית שאנו נמצאים לפני בחירות מאז שהתחלתי בכתיבת הבלוג. בעבר לא הבעתי בפומבי את הבחירה האישית שלי. עבורי יום הבחירות הוא יום חג, ההכרעות בין  תפיסות עולם ואינטרסים מנוגדים אינן קלות, ויש דרכים שונות, אותן אני מכבד, לשפוט את  המציאות ואת  המתמודדים

 זו הפעם הראשונה שאני נותן ביטוי פומבי לבחירתי

 כתמיד כל ממשלה שתוקם לאחר הבחירות תצטרך להתמודד עם קשיים, איומים
ואולי אף עם מלחמות, אבל הפעם, ללא שינוי בהנהגת המדינה, אני רואה אפשרות קשה להתדרדרות של ערכי יסוד של החברה שלנו ביחד עם התדרדרות והשחתה של מערכות המדינה והחברה

זה הזמן לשינוי

אני תומך בבחירות ברשימת המחנה הציוני

 

 

שינוי1

שינוי2

 

 

From Oberwolfach: The Topological Tverberg Conjecture is False

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.

ow

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.

Midrasha Mathematicae #18: In And Around Combinatorics

 

tahl2-mid

Tahl Nowik

photo (4) 17.8.14 midrasha poster 2015 poster

michal-mid mid-irit mid-david nati-mid mid-peter nica-mid   alex-mid2 midjoel mid-sam tami-mid zohar-mid tahl-mid

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.

Lecture series and lectures

Irit Dinur: Direct products of games and graphs

mid-irit Continue reading

Scott Triumphs* at the Shtetl

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, precisely because the 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.

@HUJI

gil+ilya

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

Ilya Rips Birthday Conference

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!

2.10.14 Geometric & Combinatorial poster

Achimedes on infinity

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.

netz2

The combinatorics school (midrasha) is coming.

17.8.14 midrasha poster 2015

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

At Combsem

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 

Continue reading

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.

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.