Category Archives: Combinatorics

More Reasons for Small Influence

Readers of the big-league ToC blogs have already heard about the breakthrough paper An average-case depth hierarchy theorem for Boolean circuits by Benjamin Rossman, Rocco Servedio, and Li-Yang Tan. Here are blog reports on Computational complexity, on the Shtetl Optimized, and of Godel … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Open problems, Probability | 12 Comments

My Fest

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 … Continue reading

Posted in Combinatorics, Conferences, Updates | 4 Comments

New Isoperimetric Results for Testing Monotonicity

Muli, Dor and Subash, Jerusalem May 21 2015.   Michel Talagrand            Gregory Margulis Property testing In this post I will tell you about a new paper by Subhash Khot, Dor Minzer and Muli Safra  entitled: On … Continue reading

Posted in Combinatorics, Computer Science and Optimization | 1 Comment

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 … Continue reading

Posted in Combinatorics, Probability, Updates | Tagged , , , , , | Leave a comment

The Simplex, the Cyclic polytope, the Positroidron, the Amplituhedron, and Beyond

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 … Continue reading

Posted in Algebra and Number Theory, Combinatorics, Convex polytopes, Physics | Tagged , , , , , , | 1 Comment

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 … Continue reading

Posted in Combinatorics, Conferences, Convexity, Updates | Tagged , , | 2 Comments

Midrasha Mathematicae #18: In And Around Combinatorics

  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 … Continue reading

Posted in Combinatorics, Conferences, Updates | 1 Comment

When Do a Few Colors Suffice?

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 … Continue reading

Posted in Combinatorics | Tagged | 1 Comment

Coloring Simple Polytopes and Triangulations

Coloring Edge-coloring of simple polytopes One of the equivalent formulation of the four-color theorem asserts that: Theorem (4CT) : Every cubic bridgeless planar graph is 3-edge colorable So we can color the edges by three colors such that every two … Continue reading

Posted in Combinatorics, Open problems | Tagged , | 10 Comments

A lecture by Noga

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 … Continue reading

Posted in Combinatorics, Conferences | Tagged , , , , , , | Leave a comment