Updates and plans III.

Update on the great Noga’s Formulas competition. (Link to the original post, many cash prizes are still for grab!)

This is the third “Updates and plans post”. The  first one was from 2008 and the  second one from 2011.

Updates: Combinatorics and more

A lot is happening!  I plan  to devote special posts to some of these developments.

The Heron-Rota-Welsh conjecture was solved by Adiprasito, Huh and Katz

    

Karim Adiprasito (with a fan), June Huh, and Eric Katz (click to enlarge!)

The Heron-Rota-Welsh conjecture regarding the log-concavity of coefficients of the characteristic polynomials of matroids is now  proved  in full generality by Karim Adiprasito, June Huh, and Eric Katz! (Along with several other related conjectures.) A few years ago Huh proved the conjecture for matroids over the reals, and with Katz they extended it to representable matroids over any field. Those results used tools from algebraic geometry. (See this post and this one.) Some months ago Adiprasito and Sanyal gave a proof, based on Alexanderov-Fenchel inequalities and measure concentration,  for $c$-arrangements. The general approach of Adiprasito, Huh and Katz of doing “algebraic geometry” in more general combinatorial contexts is very promising. Here is a link to a vidotaped lecture Hodge theory for combinatorial geometries by June Huh.

Thresholds and bounds on erasure codes by Kumar and Pfister and by Kudekar, Mondelli, Şaşoğlu, and Urbanke

(Thanks to Elchanan Mossel and Avi Wigderson for telling me about it.)

 Reed-Muller Codes Achieve Capacity on Erasure Channels by Santhosh Kumar, Henry D. Pfister

(and thanks to Kodlu’s comment)  Reed-Muller Codes Achieve Capacity on the Binary Erasure Channel under MAP Decoding, by Shrinivas Kudekar, Marco Mondelli, Eren Şaşoğlu, Rüdiger Urbanke

Abstract (for the first paper; for the second see the comment below):  This paper introduces a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes, this method requires only that the codes are highly symmetric. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge to a number between 0 and 1, and the permutation group of each code is doubly transitive. This also provides a rare example in information theory where symmetry alone implies near-optimal performance.
An important consequence of this result is that a sequence of Reed-Muller codes with increasing blocklength achieves capacity if its code rate converges to a number between 0 and 1. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to affine-invariant codes and, thus, to all extended primitive narrow-sense BCH codes. The primary tools used in the proof are the sharp threshold property for monotone Boolean functions and the area theorem for extrinsic information transfer functions.

For me, a pleasant surprise was to learn about connections between threshold behavior and coding theory that I was not aware of, and here specifically, using results with Bourgain on influences under specific groups of permutations.

Update: Here is a very nice blog post by Boaz Barak.

Explicit extractors and Ramsey numbers by Chattopadhyay and Zuckerman

(Thanks to Guy Kindler and Avi Wigderson.)

Explicit Two-Source Extractors and Resilient Functions, by Eshan Chattopadhyay and David Zuckerman

Abstract: We explicitly construct an extractor for two independent sources on bits, each with min-entropy at least for a large enough constant . Our extractor outputs one bit and has error . The best previous extractor, by Bourgain [B2], required each source to have min-entropy .

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on bits that is resilient to coalitions of size , for any . In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on bits, where some unknown bits are chosen almost -wise independently, and the remaining bits are chosen by an adversary as an arbitrary function of the bits. The best previous construction, by Viola \cite{Viola14}, achieved .

Our other main contribution is a reduction showing how such a resilient function gives a two-source extractor. This relies heavily on the new non-malleable extractor of Chattopadhyay, Goyal and Li [CGL15].

Our explicit two-source extractor directly implies an explicit construction of a -Ramsey graph over $N$ vertices, improving bounds obtained by Barak et al. [BRSW12] and matching independent work by Cohen [Coh15b].

Here are comments by Oded Goldreich. For me, a pleasant surprise regarding the construction  is that it uses, in addition to an ingenious combination of ingenious recent results (by  Li,  Cohen, Goyal, the authors, and others) about extractors, also  influences of sets of Boolean functions and, in particular, the important construction of Ajtai and Linial. (that I mentioned here several times). Recently with Bourgain and Kahn we studies influences of large sets giving examples related to the Ajtai-Linial example. Update: Another pleasant surprise was to learn (from Avi W.) that among the ingredients used in this new work is Feige’s collective coin flipping method with a very small number of rounds, which was used by Li miraculously in the extractor  engineering.

The Garsia-Stanley’s decomposition conjecture was refuted by Duval, Goeckner, Klivans, and Martin

A non-partitionable Cohen-Macaulay simplicial complex by Art M. Duval, Bennet Goeckner, Caroline J. Klivans, and Jeremy L. Martin.

Duval, Goeckner, Klivans, and Martin gave an explicit and rather small counterexample to  a conjecture of Garsia and Stanley that every Cohen-Macaulay simplicial complex is decomposable, namely its set of faces can be decomposed into Boolean intervals where are facets (maximal faces).

A Whitney Trick for Tverberg-Type Problems by Mabillard and Wagner

The much awaited paper by Mabillard and Wagner is now on the arxive. See this post on topological Tverberg’s theorem.

Eliminating Higher-Multiplicity Intersections, I. A Whitney Trick for Tverberg-Type Problems, by  Isaac Mabillard and Uli Wagner

Abstract: Motivated by topological Tverberg-type problems and by classical results about embeddings (maps without double points), we study the question whether a finite simplicial complex K can be mapped into R^d without triple, quadruple, or, more generally, r-fold points. Specifically, we are interested in maps f from K to that have no r-Tverberg points, i.e., no r-fold points with preimages in r pairwise disjoint simplices of K, and we seek necessary and sufficient conditions for the existence of such maps.
We present a higher-multiplicity analogue of the completeness of the Van Kampen obstruction for embeddability in twice the dimension. Specifically, we show that under suitable restrictions on the dimensions, a well-known Deleted Product Criterion (DPC) is not only necessary but also sufficient for the existence of maps without r-Tverberg points. Our main technical tool is a higher-multiplicity version of the classical Whitney trick.
An important guiding idea for our work was that sufficiency of the DPC, together with an old result of Ozaydin on the existence of equivariant maps, might yield an approach to disproving the remaining open cases of the long-standing topological Tverberg conjecture. Unfortunately, our proof of the sufficiency of the DPC requires a “codimension 3” proviso, which is not satisfied for when K is the N-simplex.
Recently, Frick found an extremely elegant way to overcome this last “codimension 3” obstacle and to construct counterexamples to the topological Tverberg conjecture for d at least 3r+1 (r not a prime power). Here, we present a different construction that yields counterexamples for d at least 3r (r not a prime power).

Behavior of Möbius functions (and other multiplicative functions) in short intervals by Matomaki and Radziwill

(Thanks to Tami Ziegler) We followed over here here sparsely and laymanly a few developments in analytic number theory (mainly related to gaps in primes and Möbius randomness).  It is a pleasure to mention another breakthrough, largely orthogonal to earlier ones by Kaisa Matomaki and Maksym Radziwill.  (Here is a link to the paper and to related blog posts by Terry Tao (1), (2) (reporting also on subsequent works by Matomaki, Radzwill, and Tao) NEW (3) (4)).

Update (Sept 18, 2015): Terry Tao have just uploaded a paper to the arxive where he solves the Erdos Discrepancy problem! The number theory works by Tao with Matomaki and Radzwill play important role in the proof. See this blog post on Tao’s blog with links to two new relevant papers, and this post by Tim Gowers.

Belated updates : Past and future events

My fest

On mid-June my former students organized a lovely conference celebrating my 60th birthday which I enjoyed greatly. I do plan to devote a post to the lectures and the event. Meanwhile, here are a few pictures.

                    

Travels

In the last year or so I made only very short trips. Here is a quick report on some from the last months.

BCC2015

This was the second time I participated in a British combinatorial conference, after BCC1979 that I participated as a student. My lecture and paper for the proceedings deal with questions around Borsuk’s problem. Here is the BCC paper Some old and new problems in combinatorial geometry I: Around Borsuk’s problem.  The proceeding is as always very recommended and let me mention, in particular, Conlon, Fox and Sudakov’s survey on Graph Ramsey theory. One of the participants, Anthony Hilton, took part in each and every earlier BCC. Another, Peter Cameron (blog) also gave an impressive singing with guitar performance.

Bourbaki seminaire: Designs after Keevash

I gave an expose on Keevash’s work about designs. My experience with giving this seminar is quite similar to the experience of other mathematicians. It was an opportunity to learn quite a few new things. Here is a draft of the written exposition Design exists (after Peter Keevash). . (And here are the slides) Remarks are most welcome.  The event was very exciting and J-P Serre actively participated in the first half of the day. I plan to write more about it once the paper is finalized.

LFT100  and  celebrating (small part of) Matousek’s work

Laszlo Fejer Toth 100th birthday conference was in Budapest. I gave a talk (click for the slides) on  works of Jiri Matousek. It was great to meet many friends from Hungary and other places, some of which I did not meet for many years, including Asia Ivic-Weiss, Wlodek and Greg Kuperberg, Frank Morgan, Sasha Barvinok, and many others. I plan to report at a later time on some things Sasha Barvinok have told me.

More birthday conferences

My colleagues Abraham Neyman (Merale) and Sergiu Hart celebrated with a back-to-back conferences devoted to Game theory. Egon Schulte and Caroly Bezdek celebrated together a 60th birthday conference. Congratulations to all.

Guest posts by Thilo Weinert

On infinite combinatorics are coming. We have some further promises for guest posts and even guest columns.

Polymath plans

I plan a new polymath project. Details will follow.

Between two cities

We live now in Tel-Aviv and I commute 2-3 times a week to Jerusalem.  Jerusalem is, of course,  a most exciting and beautiful city and a great place to live (especially in the summer), and I also love Tel-Aviv, its rhythm and atmosphere,  and the beach, of course. My three children and grandchild are TelAvivians. One interesting aspect of the change is the move from  a ground floor with a yard to a high floor with view.

  

 (Dec 1,2015)

Checking the 2008 and 2011 plans: (In red – unfulfilled plans, in Green fulfilled plans).

2008 Plans and updates

Polytopes. We had several posts on convex polytopes.  I next plan to discuss the diameter problem for polytopal graphs (the Hirsch conjecture) and related questions on the simplex algorithm. (In fact, we already started.)

Telling a simple polytope from its graph. The one proof I presented most often in lectures is my proof of the Blind-Mani theorem that asserts that simple polytopes are determined by their graphs. I will try to blog this proof, tell you some open problems around it, and write about a startling theorem of Eric Friedman who found a polynomial-time algorithm.

Influences and Fourier. We talked about influence but not about a major technique which emerged in their study: Fourier Analysis of Boolean functions.” So we will discuss Boolean functions and their spectrum, and revisit influences and look at noise-sensitivity. Muli Safra will give a post on the Goldreich Levin theorem and related stuff.

Pre-polymath. So far our open discussion “Is mathematics a science” attracted a single (nice) comment, and the poem translation contest is still waiting for quality translations. Perhaps we can try an open discussion of a single theorem/problem and see how it goes. (We had two series of posts on diameter of polytopes, the later as polymath3.) 

Translations to arabic? I was just told that along with Landsburg’s book itself, my book review might be translated to Arabic. Sababa! (Never heard about it again.)

Quantum and complexity. I will tell you about my ideas regarding detrimental noise for quantum computations, but only after trying to describe something about the beautiful, deep, and surprising subject of quantum computation and quantum information. I will not do it before having at least one post about classical computation complexity.

2011  Tentative Plans and Belated Updates II

Polymath 3, 1,4,5: There are more spin-offs of the old polymath projects I plan to write about, (Done) in particular on some polymath5 ideas possibly on Gowers’ blog .

Around Borsuk’s conjecture: A series of 2-3 posts about problems related to Borsuk’s conjecture are already half-written. (Done)

Stories about Avi Wigderson and me. The purposes of taxi-and-other stories and mathematics-to-the-rescue stories was as a tool to waste immediately any reputation which I may gain on this blog (e.g., the embarrassing yet educational pills story followed immediately the first comment by Tim Gowers on this blog). The Layish story, which was indirectly referred to in the very first post will mark a new stage in the reputation-waste agenda.  (Along with a few other stories involving me and Avi W.) (Too early for that, I suppose.) Also we are negotiating with Michal Linial for more of her wonderful stories. (still negotiating)

Update (Sept 2017): The Layish story have now been told.

Huntington library pictorial: This is certainly one of my most ambitious planned posts, and this explains why it takes so much time to write.  It addresses a long-standing problem which becomes more acute with time:

How to show pictures in a non-boring way.

The planned post will be a pictorial description of a legendary tour from fall 2009, guided by Benny Sudakov, of the Huntington Library in Pasadena.

Update: Well, while having semi-novels ideas on how to present the pictures, It was not clear that I can make it non-boring.

Proofs: There are proofs that I like to present (like this one), and I plan to present here a few more proofs:  A proof of KKL’s theorem that is mentioned here; Alon-Kleitman’s proof of the Hadwiger-Debrunner conjecture; and a famous proof by Perles which uses lice.

Contingency tables. Sasha Barvinok gave an illuminating talk at Yale in October 2008 about contingency tables, and this is a very nice story with many facets.  It started with a paper of Diaconis and Efron, which was followed, to a mathematician’s envy, by several papers criticizing their proposal, and a rejoiner. It is fortunate that I did not post about it at the time, since a lot has happened afterwards.  The same talk and visit led to a fruitful collaboration between Sasha and J.A. Hartigan. I still did not post about it but I plan to.

Posets:  I still owe a post about partially ordered sets (POSETS) in the extremal combinatorics series (I,II,III,IV,VI). Update (February 2019): done!

f-vectors and homology: There was a series of posts about the -conjecture and it seems like a good time to write about the relation between face numbers and topology (and mainly homology).