Midrasha Mathematicae #18: In And Around Combinatorics



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

Posted in Combinatorics, Conferences, Updates | 1 Comment

Quantum computing: achievable reality or unrealistic dream

QC-michel-view QC-gilview

Michel Dyakonov’s View on QC                                     My view (based on Michel’s drawing*)



Alexander Vlasov’s view (based on Michel and Konstantin’s drawing)

It has been a while since I devoted a post to quantum computation. Meanwhile, we had a cozy, almost private, easy-going, and very interesting discussion thread on my previous, March 2014 post (that featured my Simons Institute videotaped lectures (I,II).)

What can we learn from a failure of quantum computers?

Last week we had a workshop on “Quantum computing: achievable reality or unrealistic dream.” This was a joint venture of the  American Physics Society and the Racah Institute of Physics here at HUJI, organized by Professor Miron Ya. Amusia, and it featured me and Nadav Katz as the main speakers. Here are the slides of my lecture: What can we learn from a failure of quantum computers.


Noise Sensitivity and BosonSampling

Earlier, I gave a lecture in our CS colloquium about a recent work with Guy Kindler on noise sensitivity of BosonSampling. We show that for a constant level of noise, noisy BosonSampling can be approximated by bounded-depth computation, and that the correlation between the noisy outcome and the noiseless outcome tends to zero if the noise level is ω(1/n) where n is the number of bosons.  Here is the paper Gaussian noise sensitivity and BosonSampling, the videotaped lecture  Complexity and sensitivity of noisy BosonSampling, and the slides of the lecture.

Contagious error sources would need time travel to prevent quantum computation

On the positive side, Greg Kuperberg and I wrote a paper  Contagious error sources would need time travel to prevent quantum computation  showing that for a large class of correlated noise, (teleportation-based) quantum fault-tolerance works! Greg and I have had a decade-long email discussion (over 2000 emails) regarding quantum computers, and this work grew from our 2009 discussion (about my “smoothed Lindblad evolution” model), and heavily relies on  ideas of Manny Knill.

Nadav Katz: Quantum information science – the state of the art

Some years ago, two brilliant experimentalists, Hagai Eisenberg and Nadav Katz,  joined  the already strong, mainly theoretical, quantum information group here at HUJI.  Nadav Katz gave the second lecture in the workshop, and here are the slides of Nadav’s  lecture: Quantum information science – the state of the art.


Experimental progress toward stable encoded qubits

Also very much on the positive side, Nadav mentioned a remarkable recent progress by the Martini’s group showing certain encoded states based on 9 physical qubits which are order-of-magnitude (factor 8.4, to be precise,) more stable than the “raw” qubits used for creating them !!

Here is a link to the paper:  State preservation by repetitive error detection in a superconducting quantum circuit, by J. Kelly, R. Barends, A. G. Fowler, A. Megrant, E. Jeffrey, T. C. White, D. Sank, J. Y. Mutus, B. Campbell, Yu Chen, Z. Chen, B. Chiaro, A. Dunsworth, I.-C. Hoi, C. Neill, P. J. J. O’Malley, C. Quintana, P. Roushan, A. Vainsencher, J. Wenner, A. N. Cleland, and John M. Martinis.

Update:  Further comments on a Shtetl-optimized post (especially a comment by Graeme Smith,) help to place the new achievement of the Martinis group within the seven smilestones toward quantum computers from a 2012 Science paper by Schoelkopf and Devoret, originated by David DiVincenzo’s 2000 paper “The physical implementation of quantum computation“. (You can watch these milestone here also .)

The new achievement of having a very robust realization of certain encoded states can be seen as achieving the 3.5 milestone.   The difference between the 3.5th milestone and the 4th milestone plays a central role in the seventh post of my 2012-debate with Aram Harrow in connection with a conjecture I made in the first post (“Conjecture 1″). Aram made the point that classical error-correction can lead to very stable encoded qubits in certain states (which is essentially the 3.5 milestone). I gave a formal description of the conjecture, which essentially asserts that the 4th milestone, namely insisting that encoded qubits allows arbitrary superpositions, cannot be reached.  As I said many times (see, for example, the discussion in my 2012 Simons Institute videotaped lecture 2), a convincing demonstration of the 4th milestone, namely  implementation of quantum error-correction with encoded qubits which are substantially more stable than the raw qubits (and allow arbitrary superposition for the encoded qubit) will disprove my conjectures. Such stable encoded qubits are  expected from implementations of distance-5 surface code. So we are 0.5 milestones away :)

I will be impressed to see even a realization of distance-3 (or distance-5) surface code that will give good quality encoded qubits, even if the encoded qubits will have a quality which is somewhat worse than that of the raw qubits used for the encoding. These experiments, including those that were already carried out, also give various other opportunities to test my conjectures.

Peter Shor’s challenge #1 and my predictions from the failure of quantum computation

My lecture on predictions from the failure of QC is based on two lengthy recent comments (first, second) regarding predictions from the failure of quantum computers. On April 2014, Peter Shor challenged me with the following: Continue reading

Posted in Quantum | Tagged , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , | 7 Comments

A Historical Picture Taken by Nimrod Megiddo

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!

Posted in Conferences, Economics, Games | Tagged , | Leave a comment

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.

*** 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.

Posted in Updates, Women in science | Tagged , | 6 Comments

Amy Triumphs* at the Shtetl

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 , , | 23 Comments



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.


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

Posted in Updates | Tagged , | Leave a 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 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, \chi (G) is the chromatic number of G and \omega (G) is the clique number of G (the maximum number of vertices that form a complete subgraph. Clearly, for every graph G

\chi(G) \ge \omega (G).

Perfect graphs

Question 1: Describe the class \cal G  of graphs closed under induced subgraphs, with the property that \chi(G)=\omega (G) for every G\in{\cal G}.

A graph G is called perfect if  \chi(H)=\omega (H) 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.

Mycielski Graphs

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 v_1,v_2, \dots, v_n create a new graph  G’ as follows: add n new vertices u_1, u_2\dots u_n and a vertex w. Now add w to each u_i and for every i and j for which v_i and v_j are adjacent add also an edge between v_i and u_j (and thus also between u_i and v_j.)

Classes of Graphs with bounded chromatic numbers

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.

Trinity Graphs

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.)


Steps toward Gyarfas conjecture

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

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

Continue reading

Posted in Combinatorics | Tagged | 1 Comment

From Peter Cameron’s Blog: The symmetric group 3: Automorphisms

Here is, with Peter’s kind permission, a rebloging of Peter’s post on the automorphism group of S_n. Other very nice accounts are by the Secret blogging seminar;  John Baez,; A paper by Howard, Millson, Snowden, and Vakil; and most famously the legendary Chapter 6 (!) from the book by Cameron and Van-Lint (I dont have an electronic version for it).

My TYI 25 question about it arose from Sonia Balagopalan’s lecture in our combinatorics seminar on the 16 vertex triangulation of 4-dimensional projective space. (Here is the link to her paper.)

Peter Cameron's Blog

No account of the symmetric group can be complete without mentioning the remarkable fact that the symmetric group of degree n (finite or infinite) has an outer automorphism if and only if n=6.

Here are the definitions. An automorphism of a group G is a permutation p of the group which preserves products, that is, (xy)p=(xp)(yp) for all x,y (where, as a card-carrying algebraist, I write the function on the right of its argument). The automorphisms of G themselves form a group, and the inner automorphisms (the conjugation maps x?g-1xg) form a normal subgroup; the factor group is the outer automorphism group of G. Abusing terminology, we say that G has outer automorphisms if the outer automorphism group is not the trivial group, that is, not all automorphisms are inner.

Now the symmetric group S

View original post 1,245 more words

Posted in Uncategorized | 2 Comments

Coloring Simple Polytopes and Triangulations


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 edges sharing a vertex are colored by different colors.

Abby Thompson asked the following question:

Question: Suppose that G is the graph of a simple d-polytope with n vertices. Suppose also that n is even (this is automatic if d is odd). Can we always properly color the edges of G with d colors?

Vising theorem reminded

Vising’s theorem asserts that a graph with maximum degree D can be edge-colored by D+1 colors. This is one of the most fundamental theorems in graph theory. (One of my ambitions for the blog is to interactively teach the proof based on a guided way toward a proof, based on Diestel’s book, that I tried in a graph theory course some years ago.) Class-one graphs are those graphs with edge chromatic number equal to the maximum degree. Those graphs that required one more color are called class-two graphs.

Moving to triangulations

Thompson asked also a more general question:

Question: Let G be a dual graph of a triangulation of the (d-1)-dimensional sphere. Suppose that G has an even number of vertices.  Is G d-edge colorable?

Grunbaum’s question and counterexample

Branko Grunbaum proposed a beautiful generalization for the 4CT: He conjectured that the dual graph of a triangulation of every two-dimensional manifold is 3-edge colorable. This conjecture was refuted in 2009 by Martin Kochol.

Triangulations in higher dimensions

A third question, even more general, posed by Thompson is: Let G be a dual graph of a triangulation of a (d-1)-dimensional manifold, d ≥ 4. Suppose that G has an even number of vertices.  Is G d-edge colorable?

Hamiltonian cycles

Coloring graph is notoriously difficult but finding a Hamiltonian cycle is even more difficult.

Tait’s conjecture and Barnette’s conjectures

Peter Tait conjectured in 1884 that every 3-connected cubic planar graph is Hamiltonian. His conjecture was disproved by William Tutte in 1946. A cubic Hamiltonian graph must be of class I and therefore Tait’s conjecture implies the 4CT. David Barnette proposed two ways to save Tait’s conjecture: one for adding the condition that all faces have an even number of edges or, equivalently that the graph is bipartite, and another, by moving up in the dimension.

Barnette’s conjecture I: Planar 3-connected cubic bipartite graphs are Hamiltonian.

Barnette’s conjecture II: Graphs of simple d-polytopes d ≥ 4 are Hamiltonian.

Barnette’s hamiltonicity conjecture in high dimension does not imply a positive answer to Thompson’s quaestion. We can still ask for the following common strengthening:  does the graph of a simple d-polytope, d 4, with an even number of vertices contain [d/2] edge-disjoint Hamiltonian cycles?

There are few more things to mention: Peter Tait made also three beautiful conjectures about knots. They were all proved, but it took a century more or less. When we move to high dimensions there are other notions of coloring and other generalizations of “Hamiltonian cycles.” You can Test Your Imagination and try to think about such notions!

Update (Dec 7): Following rupeixu’s comment I asked a question over: generalizations-of-the-four-color-theorem.

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

TYI 25: The Automorphism Group of the Symmetric Group

True or False: The group of automorphisms of the symmetric group S_n, n ≥ 3 is S_n itself.


Posted in Algebra and Number Theory, Test your intuition | Tagged , | 7 Comments