Category Archives: Combinatorics

Choongbum Lee proved the Burr-Erdős conjecture

Let H be a graph. The Ramsey number R(H) is the smallest n such that whenever you color the edges of the complete graph with n vertices with two colors blue and red, you can either find a blue copy or a red copy of H.

Ramsey’s famous theorem asserts that if H is a complete graph on m vertices then R(H) is finite.   Ir follows that R(H) is finite for every graph H and understanding the dependence of R(H) on H 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 d-degenerate if it can be reduced to the empty graph by successively deleting vertices of degree at most d. 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 d, there exists a constant c = c(d) such that every d-degenerate graph H on n vertices satisfies r(H)\le cn.  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!

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 Lost letter and P=NP. Let me mention one of the applications: refuting a 1999 conjecture by Benjamini, Schramm and me.

Update: Li-Yang Tang explained matters in an excellent comment below. Starting with: “In brief, we believe that an average-case depth hierarchy theorem rules out the possibility of a converse to Hastad-Boppana-LMN when viewed as a statement about the total influence of *constant*-depth circuits. However, while the Inf(f) <= (O(\log(S)))^{d-1} bound is often applied in the setting where d is constant,  it in fact holds for all values of d. It would interesting to explore the implications of our result in regimes where d is allowed to be super-constant.

Let me add that the bounded depth case is an important case (that I referred to here), that there might be some issues failing the conjecture for non-constant depth “for the wrong reasons”,  and that I see good prospect that RST’s work and techniques will refute BKS conjecture in full also for non-bounded depth.

Update:  Rossman, Servedio, and Tan refuted some important variations of our conjecture, while other variations remain open. My description was not so accurate and in hindsight I could also explained the background and motivation better. So rather than keep updating this post, I will write a new one in a few weeks. 


Theorem: If f is described by a bounded depth circuit of size s and depth d then I(f) the total influence of f,  is at most (\log s)^{d-1}.

The total influence I(f) of f is defined as follows: for an input x write I(x) for the number of neighbors y of x with f(y) \ne f(x). I(f) = \mathbb EI(x).

The history of this result as I  remember it is that: it is based on a crucial way on  Hastad Switching lemma going back to Hastad 1986 thesis, and for monotone functions one can use an even earlier 1984 result by Boppana.  It was first proved  (with exponent “d”) in 1993 by Linial-Mansour and  Nisan, as  a consequence of their theorem on the decay of Fourier coefficients for AC0 functions, (also based on the switching lemma). With the correct exponent d-1 it is derived from the switching lemma in a short clean argument in a 97 paper by Ravi Boppana; and finally it was extended to a sharpening of LMN result about the spectral decay by Hastad (2001).

Sipser MIT photo

Mike Sipser

Inverse Boppana-Hastad-LMN

Conjecture: (Benjanmini, Kala, and Schramm, 1999): Every Boolean function  f  is “close” to some depth-d size s circuit with (\log s)^{d-1} not much larger than I(f).

Of course, the exponent (d-1) is strongest possible but replacing it with some constant times d  is also of interest. (Also the monotone case already capture much interest.)

As we will see the conjecture is false even if the exponent d-1 is replaced by a constant times d. I do not know what is the optimal function u(d) if any for which you can replace the exponent d-1 by u(d).

Update: Following some comments by Boaz Barak I am not sure that indeed the new examples and results regarding them leads to disproof of our conjecture. The remarkable part of RST’s paper is that the RST example cannot be approximated by a circuit of smaller depth – even by one. (This has various important applications.) In order to disprove our conjecture one need to show that the influence of the example is smaller than what Boppana’s inequality ((log size)^{depth-1} ) gives. This is not proved in the paper (but it may be true). 

The RST’s result does say that if the influence is (say) logn (where n is the number of variables,) and the function depends on a small number of variables then it need not be correlated with a function in AC0.  

Anyway I will keep you posted.  

in 2007 O’Donnell and Wimmer showed that our inverse conjecture is false as stated. They took a Boolean function which is a tribe function on half the variables and “anti-tribes” on the rest. This still left the possibility that the exponent d-1 could be replaced by d or that “close” could be replaced by a weaker conclusion on substantial correlation.

Rossman,  Servedio, and a genuinely new reason for small influence!Their example, named after Mike Sipser,  is based on the AND-OR tree – a Boolean formula with alternating AND and OR levels and carefully designed parameters.  The crucial part is to show that you cannot approximate this function by lower depth circuits. The theorem proved by RST  is amazingly strong and does not allow reducing the depth even by one! The novel technique for proving it of random projections is very exciting.

It is still possible (I think) that such inverse theorems hold when the individual influences of all variables is below polylog(n)/n where n is the number of variables. Let me pose it as a conjecture:

Conjecture: Every Boolean function  f  with n variables and individual influences below polylog (n)/n is close to a function g in AC0   of size s depth d where (log s)^d is polylog (n).

And here is a post on TCSexchange with a question about “monotone  vs positive” for the class P. Similar questions for AC0 and TC0 were asked in this post.

New Isoperimetric Results for Testing Monotonicity

photo (11)

Muli, Dor and Subash, Jerusalem May 21 2015.

Talagrand1 Margulis2

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 Monotonicity Testing and Boolean Isoperimetric type Theorems. This remarkable paper gives a definite answer to one of the main open problems on property testing, proves some wonderful new isoperimetric inequalities, and shed some light on the still mysterous property of monotonicity.

Property testing is an exciting area which lies between mathematics and the theory of computing. (Closely related to PCP and to some modern aspects of error-correcting codes.) Here is a post about it in Terry Tao’s blog.

Suppose that you have an unknown graph G and you want to distinguish between two possibilities

1) The graph G contains a triangles

2) We can remove an 1%  of the edges of G so that no triangle will remain.

It turns out that by looking at a bounded number of edges drawn at random we can either demonstrate that G contains a triangle or demonstrate that with high probability the second possibility holds! Moreover, this is a deep mathematical result.

Property testing resembles a little election polls (and, more generally statistical hypothesis testing): We can estimate the outcomes of the election with good accuracy and high probability by probing the votes of a bounded number of voters.

Testing monotonicity

Given a Boolean function f, what is the smallest number of queries needed to be able to say

1) The function f is not monotone:

2) With high probability f is at most  ε-far from monotone, namely, it can be made monotone by flipping the value of at most \epsilon2^n values.

We will denote by ε(f) the normalized Hamming distance distance of a Boolean function f to the set of monotone functions.

A brief incomplete history of monotone testing

1) Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky. Testing monotonicity. Combinatorica, 20(3):301–337, 2000.

This paper considered the tester: Choose x and y at random such that y > x test if f(y) < f(x).

Using the basic edge isoperminetric inequality it was proved that n queries suffice.

It tooks 15 years a new tester and a new isoperimetric inequality to break this record and show that n^{7/8} polylog (n) queries suffice.

2)  Deeparnab Chakrabarty and C. Seshadhri. A o(n) monotonicity tester for boolean functions over the hypercube. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 411–418, 2013.

An improvement to n^{5/6} polylog (n) was achieved here

3)  Xi Chen, Rocco Servedio, and Li-Yang Tan. New algorithms and lower bounds for monotonicity testing. In Annual Symposium on Foundations of Computer Science, FOCS ’14, 2014.

The paper by Khot, Minzer and Safra reduces this to the optimal (apart from powers of logn)  \sqrt n polylog (n).They use yet a new tester and a new isoperimetric inequality.

I did not talk about adaptive version of the problem about lower bounds and about the dependence on \epsilon.  Khot, Minzer and Safra also give (up to powers of log) optimal dependence on \epsilon.

Isoperimetric results: Margulis, Talagrand, and beyond

Margulis’s Theorem:  Let f be a Boolean function on \Omega_n={0,1}^n. Let $\latex \mu$ be the uniform probability measure on $\Omega_n$.  For x \in \Omega_n define

I(x)=|\{y \in \Omega_n,f(x)=1,d(x,y)=1, f(y) \ne f(x)\}|. 

Now, the edge boundary (or total influence) of f is defined by

I(f)-\mathbb E I(x) it is also denoted by B_e(f).

The vertex boundary of f is defined by  \Gamma (f)=\mu(\{x \in \Omega_n: I(x) \ne 0\})

The classic edge-isoperimetric result asserts that

(1)  I(f) \ge 2 var (f),

Here var(f), is the variance of f.

Margulis theorem asserts that for some constant C:

(2) I(f)\cdot \Gamma(f)\ge C (var (f))^2.

In fact Margulis proved the result in greater generality for Bernoulli probability measures defined by \mu_p(x)=p^k(1-p)^{n-k} where k=x_1+x_2+\dots +x_n.

Talagrand’s theorem

Talagrand’s theorem:

(3) \mathbb E(\sqrt{I(x)})\ge C'var(f).

Again Talagrand’s theorem extends to the Bernoulli case. Talagrand’s theorem implies Margulis’ theorem by a simple application of the Cauchy-Swarz inequality. Continue reading

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


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.


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.