Category Archives: Updates

Updates and plans III.

nfh

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

GilKarim  JuneHuh  Katz4

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

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 n bits, each with min-entropy at least \log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{-\Omega(1)}. The best previous extractor, by Bourgain [B2], required each source to have min-entropy .499n.

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

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 2^{(\log \log N)^{O(1)}}-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 [S_i,F_i] where F_i 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 R^d 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)).

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.

DRG_1400 Douglas Guthrie Photos DRG_1468 Douglas Guthrie PhotosDRG_1567 Douglas Guthrie Photos DRG_1605 Douglas Guthrie PhotosDRG_1692 Douglas Guthrie Photos DRG_1719 Douglas Guthrie PhotosDRG_1839 Douglas Guthrie Photos DRG_1724 Douglas Guthrie PhotosDRG_1871 Douglas Guthrie Photos DRG_1775 Douglas Guthrie Photos  DRG_1910 Douglas Guthrie Photos DRG_1837 Douglas Guthrie Photos  DRG_1906 Douglas Guthrie Photos DRG_1988 Douglas Guthrie Photos DRG_2049 Douglas Guthrie Photos DRG_2114 Douglas Guthrie Photos DRG_2134 Douglas Guthrie Photos DRG_2224 Douglas Guthrie Photos  DRG_1586 Douglas Guthrie Photos DRG_1809 Douglas Guthrie PhotosGil3  DRG_1863 Douglas Guthrie Photos

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.

WV1  WV2

view

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

2008 Plans and updates

Continue reading

NogaFest, NogaFormulas, and Amazing Cash Prizes

Ladies and gentlemen,  a conference celebrating Noga Alon’s 60th birthday is coming on January. It will take place at Tel Aviv University on January 17-21. Here is the event webpage. Don’t miss the event !

nogafest Cash Prizes!

The poster includes 15 formulas representing some of Noga’s works. Can you identify them?

The first commentator  to identify a formula will win a prize of 10 Israeli Shekels (ILS) that can be claimed on Noga’s Fest itself, (or else, in person, next time we meet after the meeting.) Cash prizes claimed in person on the meeting  will be doubled! Cash prizes for the oldest and newest formulas are tripled! There is a limit of one answer/prize per person/ per week. Answers need to include the formula itself, tell what the formula is, and give crucial details about it.

More cash prizes!!

For each of these formulas, once identified, the comment giving the latest place where the formula   is reproduced, (in a later paper or book not coauthored by any of the original discoverers) will be eligible also to 5 ILS prize. The same doubling and tripling rules as above apply. Here there is no limit on answers per person.

And even more cash prizes !!!

There will be 5 additional prizes of  20 ILS for formulas by Noga, that did not make it to the poster. Same doubling and tripling rules apply.

And Even More! Win a Travel Grant to the conference

Among all participants who are  students or post docs, one grant for a round trip to the meeting  will be given.

Rules

People involved in preparing the poster are not eligible.

The competition opens now!!!

And here are more details on the meeting itself. (The meeting also celebrates a decade anniversary for Zeilberger’s Opinion 71.) Continue reading

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!

Angry Birds Update

Angry birds peace treaty by Eretz Nehederet

Arqade

A few years ago I became interested in the question of whather new versions of the computer game “Angry Birds” gradually makes it easier to get high scores. Devoted to the idea of Internet research activity I decided to explore this question on “ARQADE” a Q/A site for video games. I was especially encouraged by the success of an earlier question that was posted there by Andreas Bonini: Is Angry Birds deterministic? As you can see Bonini’s question got 239 upvotes making it the second most popular quastion in the site’s history. (The answer with 322 upvotes may well be the most popular answer!) abd Is Angry Birds deterministic? (Click on pictures to enlarge.) arqaFP

Arqade’s top questions

abdc

Some comments to the answer regarding Angry Birds. 

The question if Angry Birds is deterministic is the second most decorated question on Arqade, and its answers were extremely popular as well. (Other decorated questions include: How can I tell if a corpse is safe to eat? How can I kill adorable animals? and  My head keeps falling off. What can I do?.) As you can see from the comments taken from the site referring to science was warmly accepted!

My question

I decided to ask a similar question about new versions and hoped for a similar success. Continue reading

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.