Category Archives: Conferences

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

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

A Historical Picture Taken by Nimrod Megiddo

Last week I took a bus from Tel Aviv to Jerusalem and I saw (from behind) a person that I immediately recognized. It was Nimrod Megiddo, from IBM Almaden, one of the very first  to relate game theory with complexity theory, one of the pioneers of computational geometry, and one of the leaders in optimization and linear programming, the guy who (with Ehud Kalai) was the first to  invited me to an international conference, and a fresh Laureate of the John von Neumann theory Prize.  I did not see Nimrod more than a year after our last coincidental  meeting at the Berkeley Simons Institute, I called over to him and he was happy to see me as I was happy to see him, and we found a place together at the back of the bus and caught up on things.

Nimrod showed me on the bus a picture he found in his house, taken by him at the  1974  game theory workshop in Bad Salzuflen, Germany. With Nimrod’s kind permission I present the picture here: (The copyright © belongs to Nimrod Megiddo who took the picture).

Megiddo

Here are some of the people left to right, (on some I already told you in other posts):

David Schmeidler (only beard visible)
Guillermo Owen
Lloyd Shapley
Sergiu Hart
Yair Tauman (only back shown)
Robert Aumann
Werner Güth (behind Aumann)
Reinhard Selten
Ehud Kalai (just to the right of Selten looking at the camera)
Gerhard Schwedihauer
Elon Kohlberg (only back shown, looking to the left)
William Lucas (in the back, looking at the wall)
Robert Weber (only hair and jacket visible)
Bezalel Peleg (looking to the right)
Joel Moulen (looking to the left)
Thomas Marschak (sunglasses and beard)
Michael Maschler
Joachim Rosenmüller (with glasses behind Maschler)
Kenjiro Nakamura

Happy new 2015!

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