Let be a graph. The Ramsey number is the smallest such that whenever you color the edges of the complete graph with vertices with two colors blue and red, you can either find a blue copy or a red copy of .
Ramsey’s famous theorem asserts that if is a complete graph on vertices then is finite. Ir follows that is finite for every graph and understanding the dependence of on 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 -degenerate if it can be reduced to the empty graph by successively deleting vertices of degree at most . 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 , there exists a constant such that every -degenerate graph on vertices satisfies 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!
It is a pleasure to announce my own birthday conference which will take place in Jerusalem on June 15-16 2015.
Here is the meeting’s homepage!
The organizers asked me also to mention that some support for accommodation in Jerusalem for the duration of the conference is available.
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!) Is Angry Birds deterministic? (Click on pictures to enlarge.)
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!
I decided to ask a similar question about new versions and hoped for a similar success. Continue reading
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.
With Ilan, my four month old grandson