Category Archives: Combinatorics

Two Delightful Major Simplifications

simplify

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.

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

ampn

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 m minors non-negative. The cells in the cellular structure of the positroidron correspond to those matrices with the same (+,0) pattern for m by m minors. When m=1 we get a (spherical) simplex. When we project the positroidron using an n by k totally positive matrix we get for m=1 the cyclic polytope, and for general m the  amplituhedron. When we project using general matrices we obtain general polytopes for m=1, and an interesting extension of polytopes proposed by Thomas Lam for general m.   

Alex Postnikov’s recent lectures series in our Midrasha was an opportunity to understand slightly better some remarkable combinatorial objects that drew much attention recently. Continue reading

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 based on two major ingredients. The first is a recent major theory by Issak Mabillard and Uli Wagner which extends fundamental theorems from classical obstruction theory for embeddability to an obstruction theory for r-fold intersection of disjoint faces in maps from simplicial complexes to Euclidean spaces. An extended abstract of this work is Eliminating Tverberg points, I. An analogue of the Whitney trick. The second is a result  by Murad Özaydin’s from his 1987 paper Equivariant maps for the symmetric group, which showed that for the non prime-power case the topological obstruction vanishes.

It was commonly believed that the topological Tverberg conjecture is correct. However, one of the motivations of Mabillard and Wagner for studying elimination of higher order intersection was that this may lead to counterexamples via Özaydin result. Isaak and Uli came close but there was a crucial assumption of large codimension in their theory, which seemed to avoid applying the new theory to this case.  It turned out that a simple combinatorial argument allows to overcome the codimension problem!

Florian’s  combinatorial argument which allows to use Özaydin’s result in Mabillard-Wagner’s theory  is a beautiful example of a powerful combinatorial method with other applications by Pavle Blagojević, Florian Frick and Günter Ziegler.

ow

Both Uli and Florian talked about it here at Oberwolfach on Tuesday. I hope to share some more news items from Oberwolfach and from last week’s Midrasha in future posts.

Midrasha Mathematicae #18: In And Around Combinatorics

 

tahl2-mid

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

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

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.

A lecture by Noga

nogauriirit

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 Alon’s lecture in the meeting. Noga is my genious twin academic brother – we both were graduate students under the supervision of Micha A. Perles in the same years and we both went to MIT as postocs in fall 1983.  The lecture starts with briefly mentioning four results by the birthday boys related to combinatorics and geometry and continues with recent startling results by Alon, Ankur Moitra, and Benny Sudakov. One out of many contributions of Noga over the years is building a large infrastructure of constructions and examples, often very surprising,  in combinatorics, graph theory, information theory,TOC, and related areas. And the new results add to this infrastructure. The slides are very clear. Enjoy!

noga240-1noga240-2240z240e240j240l