Author Archives: Gil Kalai

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.

@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

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

trinity-youtique-logo

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

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

Gil Kalai:

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

Originally posted on 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 1,245 more words

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

Test your intuition 24: Which of the following three groups is trivial

1office08

Martin Bridson

We have three finitely presented groups

A is generated by two generators a and b and one relation  a^{-1} \cdot b\cdot a = b^2

B is generated by three generators a, b, c and three relations a^{-1} \cdot b\cdot a = b^2,  b^{-1}\cdot c\cdot b = c^2,  c^{-1}\cdot a\cdot c = a^2.

C is generated by four generators a, b, c, d and four relations a^{-1} \cdot b\cdot a = b^2,  b^{-1}\cdot c\cdot b = c^2,  c^{-1}\cdot d\cdot c = d^2, and d^{-1}\cdot a \cdot d = a^2.

Test your intuition: which of the groups A, B or C is trivial

Please do not answer this poll if you already knew the answer

This poll is to learn how many people already knew the answer before. Please please answer.

As always comments are welcome!

Update: I did not know the answer (and I feel now better about it).