Category Archives: Updates

Choongbum Lee proved the Burr-Erdős conjecture

Let H be a graph. The Ramsey number R(H) is the smallest n such that whenever you color the edges of the complete graph with n vertices with two colors blue and red, you can either find a blue copy or a red copy of H.

Ramsey’s famous theorem asserts that if H is a complete graph on m vertices then R(H) is finite.   Ir follows that R(H) is finite for every graph H and understanding the dependence of R(H) on H is a very important question. Of course there are very basic extensions: to many colors, to different requirements for different colors, and to hypergraphs.

A graph is d-degenerate if it can be reduced to the empty graph by successively deleting vertices of degree at most d. Thus, trees are 1-degenerate (and 1-degenerate graphs are forests), and planar graphs are 5-degenerate. For graphs to be degenerate is equivalent to the condition that the number of edges is at most linear times the number of vertices uniformly for all subgraphs.

In 1973, Burr and Erdős  conjectured that that for every natural number d, there exists a constant c = c(d) such that every d-degenerate graph H on n vertices satisfies r(H)\le cn.  This is a very different behavior than that of complete graphs where the dependence on the number of vertices is exponential. In 1983 Chvátal, Rödl, Szemerédi, and Trotter proved the conjecture when the maximum degree is bounded. Over the years further restricted cases of the conjectures were proved some weaker estimates were demonstrated. These developments were instrumental in the developments of some very basic tools in extremal and probabilistic combinatorics. Lee’s paper Ramsey numbers of degenerate graphs proved the conjecture!

Angry Birds Update

Angry birds peace treaty by Eretz Nehederet


A few years ago I became interested in the question of whather new versions of the computer game “Angry Birds” gradually makes it easier to get high scores. Devoted to the idea of Internet research activity I decided to explore this question on “ARQADE” a Q/A site for video games. I was especially encouraged by the success of an earlier question that was posted there by Andreas Bonini: Is Angry Birds deterministic? As you can see Bonini’s question got 239 upvotes making it the second most popular quastion in the site’s history. (The answer with 322 upvotes may well be the most popular answer!) abd Is Angry Birds deterministic? (Click on pictures to enlarge.) arqaFP

Arqade’s top questions


Some comments to the answer regarding Angry Birds. 

The question if Angry Birds is deterministic is the second most decorated question on Arqade, and its answers were extremely popular as well. (Other decorated questions include: How can I tell if a corpse is safe to eat? How can I kill adorable animals? and  My head keeps falling off. What can I do?.) As you can see from the comments taken from the site referring to science was warmly accepted!

My question

I decided to ask a similar question about new versions and hoped for a similar success. Continue reading

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.

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

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

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

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

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

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