Updates (belated) Between New Haven, Jerusalem, and Tel-Aviv

This is a (very much) belated update post from the beginning of March (2016).

New Haven

I spent six weeks in February (2016) in New Haven. It was very nice to get back to Yale after more than two years. Here is a picture from the spectacular Yale’s art museum.

piccaso

Micha Sageev’s construction. I got the gist of it (at last…)

A few years ago I wrote about amazing developments in low dimensional topology. Ian Agol proved the Thurston’s virtual Haken conjecture. The proof relies on earlier major works by Dani Wise and others (see this post) and an important ingredient was Micha Sageev work on cubical complexes arising from 3-manifolds. I remember thinking that as a mathematician in another field it is unrealistic for me to want to understand  these developments in any detail (which is not an obstacle for writing about them), but that one day I want to understand Sageev’s construction. At Yale, Ian Agol gave three lectures on his proof, mentioned a combinatorial form of Sageev construction, and gave me some references. A few days after landing Dani Wise talked at our seminar and he explained to me at lunch how it goes in details. (BTW, a few days before landing Micha Sageev gave a colloquium at HUJI that I missed.) I have some notes,  and it is not so difficult so stay tuned for some details in a future post!. (Update: I will need some refreshing for writing about it. But I can assure you that Micha Sageev’s construction is a beautiful combinatorial  construction that we can understand and perhaps use.)

Unorthodox PNT (and even weak forms of RH).

Hee Oh talked at Yale about various analogs of the prime number theorem (PNT) and in some cases even of weak forms of the Riemann hypothesis for hyperbolic manifolds and for rational maps. This is based on a recent exciting paper by Oh and Dale Winter. Some results for hyperbolic manifolds were known before but moving to dynamics of rational maps is completely new and it follows  a “dictionary” between hyperbolic manifolds and rational maps offered by Dennis Sullivan. It was nice to see in Oh’s lecture unexpected connections between the mathematical objects studied by three Yale mathematicians, Mandelbrot, Margulis, and Minsky. Are these results related to the real Riemann Hypothesis? I don’t know.

Weil conjectures (even for curves): from the very concrete to the very abstract,

Going well over my head I want to tell you about somethings I learned from two lectures. It is about Weil’s conjectures for curves including the  “Riemann hypothesis for curves over finite fields.”   One lecture is by Peter Sarnak and the other by Ravi Vakil. Both lectures were given twice (perhaps a little differently)  in Jerusalem and at Yale few weeks apart. Peter Sarnak mentioned in a talk the very concrete proof by Stepanov to the Rieman hypothesis for curves over finite fields. The proof uses some sort of the polynomial method, and it is this concrete proof  that is useful for a recent work on Markoff triples by Bourgain, Gamburd and Sarnak. Ravi Vakhil mentioned a very very abstract form of the conjecture or, more precisely, of the “rationality” part of it proved in 1960 by Bernard Dwork (yes, Cynthia’s father!). It started from an extremely abstract version offered by  Kapranov in 2000 to which Larsen and Lunts found a counterexample. A certain weaker form of Kapranov’s conjecture that Ravi discussed might still be correct. (A related paper to Ravi’s talk is Discriminants in the Grothendieck ring  by Ravi Vakil and Melanie Matchett Wood.)  These very abstract forms of the conjectues are also extremely appealing and it is especially appealing to see the wide spectrum from the very concrete to the very abstract. It is also nice that both the polynomial method and the quest for rationality (of power series) are present also in combinatorics.

HD expanders, HD combinatorics, and more.

Alex Lubotzky and I gave a  6-weeks course on high dimensional expanders. This was the fourth time we gave a course on the subject and quite a lot have happened since we first taught a similar course some years ago so it was quite interesting to get back to the subject. I certainly plan to devote a few posts to HD-expanders and Ramanujan complexes at some point in the future.

Update: There will be a special semester on high-dimensional combinatorics and the Israeli Institute for Advanced Studies in Jerusalem in the academic year 2017/2018.

At the Simons Center in NYC Rafał Latała gave a beautiful lecture on the solution by Thomas Royen  of the Gaussian correlation conjecture. Here is a review paper by Rafał Latała and Dariusz Matlak.

Update: Here is an article about this proof in Quanta magazine.

Polymath talks

I also gave three lectures at Yale about polymath projects (at that time both Polymath10 and Polymath11 were active), and a special welcome lecture to fresh Ph. D. potential students  POLYMATH and more – Mathematics over the Internet (click for the presentation) about polymath projects and mainly Polymath5, MathOverflow, mathematical aspects of Angry Birds and why they should all choose Yale.

An advantage of being 60.

One of repeated rather unpleasant dreams I had over the years (less so in the last decade)  was that the  Israeli army discovered that I still owe some months of service, and I find myself confusingly and inconveniently back in uniform. A few weeks (+ one year) ago I had a new variant of that dream appropriately scaled to my current age:  MIT discovered that I still owe some months of my postdoctoral service. This was much more pleasant!

Posted in Art, Combinatorics, Computer Science and Optimization, Number theory, Updates | Leave a comment

Oded Goldreich Fest

Update (April 17): Outcomes of the poll for the coolest title are in. (See the end of the post)

Oded Goldreich’s 60 birthday meeting, April 19-20 at the Weitzmann Institute promises to be a great event. Here is the webpage of the event. Many cool talks with cool titles. To celebrate the birthday we run a poll for the coolest title among eight selected titles. Please participate!

Outcomes

Continue reading

Posted in Combinatorics, Computer Science and Optimization, Conferences | Tagged | 1 Comment

The Race to Quantum Technologies and Quantum Computers (Useful Links)

One of my main research directions in the last decade is  quantum information theory and quantum computers. (See this post and this one.) It is therefore a pleasure to report and give many links on the massive efforts carried out these days in these directions and the great enthusiasm and hope these efforts carry.

Europe quantum flagship

European Commission will launch €1 billion quantum technologies flagship; The full quantum manifesto;

An article in the Economist

A general article about quantum technologies and computing  in the Economist.

An article in “Nature”

“Nature” article  Quantum computers ready to leap out of the lab in 2017.  It is mainly on Google, Microsoft, and Monroe’s lab mentioning also IBM, Rigetti and Quantum Circuits (a new startup by the Yale group). A little debate between John Martinis and Robert Schoelkopf about the target of “quantum supremacy.”  Regarding topological quantum computing Leo Kouwenhoven declares that “2017 is the year of braiding,”

For the comment section: “Quantum computers” in various languages

How to say “Quantum computers” in other languages? Hebrew: מחשבים קוונטים pronounced: maghshevim kvantim; Spanish: Computadoras cuánticas (google translate).

Please contribute! For earlier efforts in this spirit see “more or less in various languages” and “When it rains it pours” in various languages. Of course, ordinary comments are welcome as well.

Google/IBM/Microsoft and others: the race for building quantum computers.

The Race to Sell True Quantum Computers Begins Before They Really Exist, (Wired)  Mainly on Google and IBM. IBM Inches Ahead of Google in Race for Quantum Computing Power, MIT Technology Review.  Commercialize quantum technologies in five years (Nature) Continue reading

Posted in Computer Science and Optimization, Physics, Quantum | Tagged , , , , , | 9 Comments

Around the Garsia-Stanley’s Partitioning Conjecture

 

Art Duval, Bennet Goeckner, Carly Klivans, and Jeremy Martin found a counter example to the Garsia-Stanley partitioning conjecture for Cohen-Macaulay complexes. (We mentioned the conjecture here.)  Congratulations Art, Bennet, Carly and Jeremy!  Art, Carly, and Jeremy also wrote an article on the the Partitionability Conjecture in the Notices of the AMS.  (Here is an article about it in the Brown Daily Herald.) Let me tell you about the conjecture and related questions. Here are the last few sentences of the paper.

Even though statements like the Partitionability Conjecture can seem too beautiful to be false, we should remember to keep our minds open about the mathematical unknown—the reality might be quite different, with its own unexpected beauty.

I. Symmetric chain decomposition for the Boolean lattice

I will start with an analogy.

Let P(n) be the family of all subsets of {1,2,…, n}. A family of subsets of {1,2,…, n} is an antichain if no set in the family contains another set in the familySperner’s theorem (see this post) asserts that for every antichain A  of subsets of [n] we have  |A| \le {{n } \choose {n/2}}.

So we have a combinatorial notion: an antichain, and we have a numerical consequence: Sperner’s theorem. Our aim is to give a structure theorem which implies the numerical consequence. A saturated symmetric chain is a chain of n-2k sets of sizes k, k+1, \dots , n-k, for some k.

Symmetric chain decomposition: P(n) can be partitioned into saturated symmetric chains

The partition of P(n) into saturated symmetric chain gives you a combinatorial structure that implies the “numerical” content of Sperner’s theorem. The Garsia-Stanley’s conjecture has a somewhat similar flavor.

Let me note that there are stronger numerical results about antichains such as the LYM inequality (see the same post) and  an interesting question (I think)  is:

Question: Are there decomposition theorems for P(n) that support stronger numerical results about antichains,  such as the LYM inequality?

II. The general framework

The general framework of our discussion is described in the following diagram:

Continue reading

Posted in Combinatorics, Geometry | Tagged , , , , , | Leave a comment

My Answer to TYI- 28

The fifteen remarkable individuals in the previous post are all the recipients of the  SIGACT Distinguished Service Prize since it was established in 1997. The most striking common feature to all of them is, in my view, that they are all men.

Update:  As Lance Fortnow the chair of the selection committee commented below the deadline for this year nomination is April 2, 2017. (Nominations should be sent to Lance to fortnow@cc.gatech.edu and if you need more time nicely ask Lance). Lance wrote that the selection committee welcomes diverse applications.

 

Continue reading

Posted in Computer Science and Optimization, Women in science | Tagged , | 2 Comments

Test your intuition 28: What is the most striking common feature to all these remarkable individuals

Test your intuition: What is the most striking common feature to all these fifteen remarkable individuals

László Babai; Avi Wigderson; Lance Fortnow; Lane Hemaspaandra; Sampath Kannan; Hal Gabow; Richard Karp; Tom Leighton; Rockford J. Ross; Alan Selman; Michael Langston; S. Rao Kosaraju; Fred S. Roberts; Ian Parberry; David S. Johnson

A poll: Please ignore the “answers” and enter your own answer under “other”.

Posted in Computer Science and Optimization, Test your intuition | 1 Comment

R(5,5) ≤ 48

The Ramsey numbers R(s,t)

The Ramsey number R(s, t) is defined to be the smallest n such that every graph of order n contains either a clique of s vertices or an independent set of t vertices. Understanding the values of R(s,t) is among the most important, fruitful, and frustrating questions in combinatorics.

43 ≤ R(5,5) ≤ 48

Vigleik Angeltveit and  Brendan D. McKay proved that the value of the diagonal Ramsey number R(5,5) is at most 48. Here is the paper.

The proof of  is via computer verification, checking approximately two trillion separate cases! Congratulations Brendan and Vigleik! (I heard about it from Greg Kuperberg.)

The best known lower bound of 42 was established  by Exoo in 1989.  The previous best upper bound of 49 was proved by Brendan McKay and Stanislaw P. Radziszowski.

By this 4-days old theorem we now have 43 ≤ R(5, 5) ≤ 48. Brendan and Vigleik write “The actual value of R(5, 5) is widely believed to be 43, because a lot of computer resources have been expended in an unsuccessful attempt to construct a Ramsey (5,5)-graph of order 43.” 

R(4,5) =25

In 1995 Brendan McKay and Stanislaw Radziszowski famously proved that R(4, 5) = 25. Listing all graphs with 24 vertices which admit a coloring without a clique on 5 vertices or an independent set with 4 vertices is a major part of the current proof.

Here is, more or less,  how Greg described the achievement on FB: How many people can you have at a party such that no 5 are all acquainted and no 5 are all strangers? It has been known for nearly 30 years that 42 people is possible, and known for 20 years that 49 is not possible. The momentous news  is that 48 is also not possible.

Greg continuation was a little cryptic to me: According to the paper, most mathematicians with any opinion on the matter agree with Douglas Adams that 42 is the answer. (By convention, the question is phrased in terms of the first impossible value, which is now known to be at least 43 and at most 48, and conjectured to be the former.) In response to my confusion Barry Simon added a ring theoretic aspect:  Gil Kalai Isn’t the answer to “the ring of what” always: “one ring to rule them all” sort of like what “42” always means. 

Posted in Combinatorics, Open problems, Updates | Tagged , | Leave a comment

Test Your Intuition (27) about the Alon-Tarsi Conjecture

On the occasion of Polymath 12 devoted to the Rota basis conjecture let me remind you about the Alon-Tarsi conjecture and test your intuition concerning a strong form of the conjecture.

The sign of a Latin square is the product of signs of rows (considered as permutations) and the signs of columns. A Latin square is even if its sign is 1, and odd if its sign is -1. It is easy to see that when n is odd the numbers of even and odd Latin squares are the same.

The Alon-Tarsi Conjecture: When n is even the number of even Latin square is different from the number of odd Latin square.

This conjecture was proved when n=p+1 and p is prime by Drisko and when n=p-1 and p is prime by Glynn. The first open case is n=26.

A stronger conjecture that is supported by known data is that when n is even there are actually more even Latin squares than odd Latin squares. (This table is taken from the Wolfarm mathworld page on the conjecture.)

Test your intuition: Are there more even Latin squares than odd Latin squares when n is even?

A poll

Unlike previous “test your intuition” questions the answer is not known.

The Alon Tarsi-Theorem

The Alon-Tarsi conjecture arose in the context of coloring graphs from lists. Alon and Tarsi proved a general theorem regarding coloring graphs when every vertex has a list of colors and the conjecture comes from applying the general theorem to Dinits’ conjecture that can be regarded as a statement about list coloring of the complete bipartite graph K_{n,n}. In 1994 Galvin proved the Dinitz conjecture by direct combinatorial proof. See this post. Gian-Carlo Rota and Rosa Huang proved that the Alon-Tarsi conjecture implies the Rota basis conjecture (over \mathbb R) when n is even.

Let G be a graph on n vertices \{1,2,\dots, n\}. Associate to every vertex i a variable x_i. Consider the graph polynomial P_G(x_1,\dots ,x_n)=\prod \{(x_i-x_j) i<j, \{i,j\} \in E(G)\}. Alon and Tarsi considered the coefficient of the monomial \prod_{i=1}^d x_i^{d_i}. If this coefficient is non-zero then they showed that for every lists of colors, d_i+1 colors for vertex i, there is a legal coloring of the vertices from the lists! Alon and Tarsi went on to describe  combinatorially the coefficient as the difference between numbers of even and odd Euler orientations.

Let me mention the paper by Jeannette Janssen  The Dinitz problem solved for rectangles that contains a proof based on Alon-Tarsi theorem of a rectangle case of Dinitz conjecture. It is very interesting if the polynomial used by Janssen can be used to prove a “rectangular” (thus a bit weaker) version of the Rota’s basis conjecture. A similar slightly weaker form of the conclusion of Rota’s basis  conjecture is conjectured by Ron Aharoni and Eli Berger in much much greater generality.

Posted in Combinatorics, Open problems, Test your intuition | Tagged , | Leave a comment

Thilo Weinert: Transfinite Ramsey Numbers

This is first of three posts kindly written by Thilo Weinert

Recently Gil asked me whether I would like to contribute to his blog and I am happy to do so. I enjoy both finite and infinite combinatorics and it seems that these fields drifted apart in recent decades. The latter is a comment not possibly substantiated by personal experience yet rather by my perception of the number and kinds of papers published. I believe that there is no mathematical reason for this separation but that it came about for reasons of the sociology of mathematics—maybe one should create a chair for this subject somewhere sometimes. Anyhow, I would like to write a few words about an area where finite and infinite combinatorics come together, the partition calculus for ordinal numbers.

The Partition Calculus, contemporarily classified as 03E02 under Mathematical Logic/Set Theory was initiated in 1956 with the article A partition calculus in set theory, published by Paul Erdos and Richard Rado in the Bulletin of the American Mathematical Society. \kappa \rightarrow (\lambda, \mu)^\nu asserts that for every set N of \nu-sized subsets of a set K of size \kappa there is an L \subset K of size \lambda such that all subsets of L of size \nu are in N or an M \subset K of size \mu such that no subset of M of size \nu is in N. Many mathematicians are concerned with the case where \kappa, \lambda, \mu, \nu are finite. As in the finite realm the notions of cardinal number and ordinal number coincide, it is there unnecessary to differentiate between these notions of size. Furthermore, via the Well-Ordering-Theorem, the Axiom of Choice implies that for cardinalities \kappa,\lambda,\mu the statement \kappa\rightarrow(\lambda,\mu)^\nu is equivalent to \bar{\kappa}\rightarrow(\bar{\lambda}, \bar{\mu})^\nu where \bar{\zeta} denotes the smallest ordinal number of cardinality \zeta. It also implies that there is no \kappa such that \kappa\rightarrow(\omega, \omega)^\omega. Hence, believing the Axiom of Choice, one may limit ones study to the cases in which \kappa,\lambda,\mu are order-types and \nu is a natural number. Although there are interesting open questions in contexts where the Axiom of Choice fails and also in contexts where not all of \kappa,\lambda,\mu are ordinal numbers, I will for now exclude these from the discussion. That is, what I would like to talk about is the subject of transfinite Ramsey Numbers, \kappa=r_\nu(\lambda,\mu) is to say that \kappa\rightarrow(\lambda, \mu)^\nu but \zeta\rightarrow(\lambda,\mu)^\nu for no \zeta<\kappa.

First I would like to discuss the lower storeys of the transfinite. It is known that generally for a countable ordinal \lambda and a natural number \mu the Ramsey number r_2(\lambda, \mu) is countable (If no subscript appears it is understood to be 2). When \lambda is a finite multiple of \omega or \omega^2, the number’s calculation is similar in character to the case where \lambda is a natural number though it tends to be slightly more involved. For example r_2(\omega\ell, m)=\omega r(I_\ell, L_m) where r(I_\ell, L_m) is the least number n without a digraph on n vertices without an independent \ell-tuple and without an induced transitive subtournament on m vertices. The r(I_2, L_n)'s are the Tournament Ramsey Numbers which have been investigated slightly more intensely in [1], [2] and exact values are known for \ell \leqslant 6. The last paper on these problems was published in 1997 by Jean Larson and William Mitchell in the very first issue of the Annals of Combinatorics. A degree argument yields r(I_\ell,L_3)\leq\ell^2 which gives a good idea about the growth rate of r(I_\ell, L_3) as counterexamples to numbers being finite Ramsey numbers easily carry over. Furthermore they found a digraph on thirteen vertices without a transitive triple or independent quadruple thus establishing r(I_\ell, L_3) \in \{14, 15, 16\}.

Recently I started to discuss these problems with Ferdinand Ihringer and Deepak Rajendraprasad. The latter found a digraph with the two aforementioned properties but on fourteen vertices and shortly thereafter they could establish by a triangle-count that there is no such digraph on 15 vertices. So we know now that r(I_4, L_3) = 15. Generally these problems should provide a nice playground for people in the business of solving Ramsey-type problems with the help of computers, cf. [3].

The situation is slightly more complicated in the case of finite multiples of \omega^2 as a degree argument only yields a cubic upper bound for r(I_\ell,A_3) which is a number defined such that r(\omega^2\ell,m)=\omega^2r(I_\ell,A_m) for all natural numbers \ell and m. This is elaborated on in detail in [4].

Recently Jacob Hilton has considered problems of this kind involving additional topological structure alone (cf. [5]) and together with Andr\'{e}s Caicedo (cf. [6]).

In the next post I am going to elaborate on results and open questions
regarding Ramsey numbers for larger countable ordinals.

[1] Kenneth Brooks Reid, Jr. and Ernest Tilden Parker. Disproof of a conjecture of
Erdos and Moser on tournaments. J. Combinatorial Theory, 9 (1970).

[2] Adolfo Sanchez-Flores. On tournaments and their largest transitive subtournaments.
Graphs Combin., 10, 1994.

[3] Stanislaw P. Radziszowski. Small Ramsey numbers. Electron. J. Combin., 1:Dynamic
Survey 1, 30 pp. (electronic), 1994,

[4] Thilo Volker Weinert, Idiosynchromatic poetry. Combinatorica, 34 (2014).

[5] Andres Eduardo Caicedo and Jacob Hilton, Topological Ramsey numbers and countable ordinals.

[6] Jacob Hilton. The topological pigeonhole principle for ordinals.

Posted in Combinatorics, Guest post, Logic and set theory | Tagged | 3 Comments

Timothy Chow Launched Polymath12 on Rota Basis Conjecture and Other News

Polymath12

Timothy Chow launched polymath12 devoted to the Rota Basis conjecture on the polymathblog. A classic paper on the subject is the 1989 paper by Rosa Huang and Gian Carlo-Rota.

Let me mention a strong version of Rota’s conjecture (Conjecture 6 in that paper) due to Jeff Kahn that asserts that if you have n^2 bases B_{i,j} 1 \le i \le n,1\le j \le n of an n-dimensional vector space then you can choose b_ {ij} \in B_{i,j} such that for every k,1 \le k\le n, the vectors b_{ik}:1\le i \le n form a basis of V and also the vectors b_{kj}:1\le j \le n form a basis. This conjecture can be regarded as a strengthening of the Dinits Conjecture whose solution by Galvin is described in this post. Rota’s original conjecture is the case where B_{i,j} depends only on i.

A very nice special case of Rota’s conjecture was proposed by Jordan Ellenberg in the polymath12 thread: Given n-1 trees on n vertices, is it always possible to order the edges of each tree so that the kth edges in the trees form a tree for every k?

Two recent papers in the Notices AMS

The February 2017 issue of the Notices of the AMS has two beautiful papers on topics we discussed here. Henry Cohn  wrote an article A conceptual breakthrough in sphere packing about the breakthrough on sphere packings in 8 and 24 dimensions  (see this post) and  Art Duval, Carly Klivans, and Jeremy Martin wrote an article on the the Partitionability Conjecture. (That we mentioned here.)

I have some plans to write about the partitionability conjecture (and an even more general conjecture of mine) soon. But now I would like to draw your attention to a weakening of these conjectures, still implying the “numerical” consequences of the original conjectures, that was proved in 2000 by Art Duval and Ping Zhang in their paper Iterated homology and decompositions of simplicial complexes . The partitionability conjecture is about decompositions into subcubes (or intervals in the Boolean lattice) and the result is about decomposition into subtrees of the Boolean lattice. (See here for the massage “trees not cubes!” in another context.)

Two steps from fame

trampolin

This pictures was taken by Edna Wigderson in a 50th birthday party for Avi Wigderson. Unfortunately the picture shows us while landing from our 3 meter high (3.28 yards) jumps and thus does not fully capture the achievement.

The  guy on the left is Bernard Chazelle, a great computer scientist and geometer,  a long time friend of me and Avi, and the father of Damien Chazelle the director and writer of the movie La La Land now nominated for the record 14 Oscar awards. I wish Damien to win a record number of Oscars and to continue writing,  directing, and producing wonderful movies so as to keep shattering his own records and giving excitement and joy to hundreds of millions, perhaps even billions, of people. (Update: Six Oscars, Damien the youngest ever director to win.)

The Jerusalem Baroque orchestra and 2017 Bach Festival

For those in Israel let me draw your attention to the Jerusalem Baroque orchestra and especially to the 2017 Bach Festival. (I thanks Menachem Magidor for telling me about this wonderful orchestra.)

Posted in Combinatorics, Mathematics over the Internet, Movies, Music, Sport, Updates | Tagged | Leave a comment