The seventeen camels riddle, and Noga Alon’s camel proof and algorithms

Three children inherited 17 camels. The will gave one half to one child, one third to a second child and one ninth to the third. The children did not know what to do and  a neighbor offered to lend them a camel. Now there were 18 camels. One child got $\frac{18}{2}=9$ camels the second got $\frac{18}{3}=6$ camels, and the third got $\frac{18}{9}=2$ camels. Altogether they got 17 camels so they could give back the extra camel to the kind neighbor.

In the very short 2003 paper A simple algorithm for edge-coloring bipartite multigraphs, Information Processing Letters 85 (2003), 301-302, Noga Alon used a similar idea for algorithmic purposes. (He also observed the connection to the camel riddle). Here is how the extra camel idea is used for:

Theorem:  A bipartite cubic graph $G$ has a perfect matching.

(A cubic graph is a  3-regular graph.)

Proof: Suppose that $G$ has $n$ vertices. Multiply each edge $r$ times ($r$ large) so that the degree of each vertex $3r$ is of the form $2^m-1$. Now ask your neighbor to give you an additional perfect matching and add it to the graph which now is regular of degree $2^{m}$ . The new graph has an Eulerian cycle. (If not connected, every connected component has an Eulerian cycle.) When we walk on the Eulerian cycle and take either the even edges or the odd edges we get two subraphs of degree $2^{m-1}$.  At least one of them does not use all the edges of the neighbor. We move to this subgraph and give the unused edge back to the neighbor.  We repeat, and in each step we move to a regular subgraph of degree  a smaller power of two, and give back at least one edge to the kind neighbor. If $r$ is large enough to start with we will end with a perfect matching that uses only the original edges of our graph.

(Remark: We can take $m=n/2$ or $m=n/2+1$. If we are a little more careful and in each step try to give many edges back to the kind neighbor we can use $m=\log n$ or so.)

Posted in Combinatorics | Tagged | 4 Comments

Edmund Landau and the Early Days of the Hebrew University of Jerusalem

Some personal/historical remarks in  first minutes of my lecture at 7ECM on July 2016…

German-Jewish mathematicians in the early days of the Hebrew University of Jerusalem

Being invited to give a plenary lecture at the 7ECM was a great honor and, as Keren Vogtmann said in her beautiful opening lecture on outer spaces, it was also a daunting task. I am thankful to Günter Ziegler for his introduction. When I ask myself in what way I am connected to the person I was thirty years ago, one answer is that it is my long-term friendship with Günter and other people that makes me the same person. My lecture deals with the analysis of Boolean functions in relation to expansion (isoperimetric) properties of subsets of the discrete n-dimensional cube. The lecture has made a subjective selection of some results, proofs, and problems from this area.

Yesterday, Leonid Polterovich and I were guests of the exhibition “Transcending Tradition: Jewish Mathematicians in German-Speaking Academic Culture.” I will start by briefly mentioning the great impact of German-Jewish mathematicians on the early history of the Einstein Institute of Mathematics and Physics at the Hebrew University of Jerusalem, my main academic home since the early seventies. In this picture you can see some early faces of our Institute.

Edmund Landau, the founder and first head of the Institute, moved to Jerusalem from Göttingen in 1927 and moved back to Göttingen a year and a half later. Abraham (Adolf) Halevi Fraenkel moved to Jerusalem from Kiel in 1928 and he can be seen as the father of logic, set theory, and computer science in Israel. My own academic great-grandfather is Michael Fekete, who immigrated to Jerusalem from Budapest in 1928.

Two remarkable documents by Edmund Landau

I would like to say a few words about two remarkable documents written by Landau in 1925, both related to the inauguration ceremony of the Hebrew University of Jerusalem. You can read more about them in the paper Zionist internationalism through number theory: Edmund Landau at the Opening of the Hebrew University in 1925 by Leo Corry and Norbert Schappacher . The first document is Landau’s toast for the opening ceremonies. Let me quote two sentences:

May great benefit emerge from this house dedicated to pure science, which does not know borders between people and people. And may this awareness emerge from Zion and penetrate the hearts of all those who are still far from this view.

The second document, also from 1925, is probably the first mathematical paper written in Hebrew in modern times. It is devoted to twenty-three problems in number theory and here are its concluding sentences.

At this number of twenty-three problems I want to stop, because
twenty-three is a prime number, i.e., a very handsome number for us. I am certain that I should not fear to be asked by you, for what purpose does one deal with the theory of numbers and what applications may it have. For we deal with science for the sake of it, and dealing with it was a solace in the days of internal and external war that as Jews and as Germans we fought and still fight today.

I wish to make two remarks: First, note that Landau moved from the very ambitious hopes and program of science as a bridge that eliminates borders between nations to a more modest and realistic hope that science and mathematics give comfort in difficult times. Juggling between very ambitious programs and sober reality is in the nature of our profession and we are getting paid both for the high hopes and aims, as well as for the modest results. Second, Landau is famous for his very rigorous and formal mathematical style but his 1925 lecture is entertaining and playful. I don’t know if his move to Jerusalem was the reason for this apparent change of style. Parts of Landau’s lecture almost read like stand-up comedy. Here is, word for word, what Landau wrote about the twin prime conjecture:

Satan knows [the answer]. What I mean is that besides God Almighty no one knows the answer, not even my friend Hardy in Oxford.

These days, ninety years after Landau’s lecture, we can say that besides God Almighty no one knows the answer and not even our friend James Maynard from Oxford. We can only hope that the situation will change before long.

Landau’s hopeful comments were made only nine years after the end of the terrible First World War. He himself died in 1938 in Berlin, after having been stripped of his teaching privileges a few years earlier. I don’t know to what extent the beauty of mathematics was a source of comfort in his last years, but we can assume that this was indeed the case. My life, like the lives of many others of my generation, was overshadowed by the Second World War and the Holocaust and influenced by the quest to come to terms with those horrible events.

Here is the videotaped lecture. (and the slides).

More sources: The home page of my Institute, and a page about its history; An article in the  AMS Notices; A blog post in Hebrew about the 1925 Hebrew University events;  Shaul Katz: Berlin roots – Zionist incarnation: The ethos of pure mathematics and the beginnings of the Einstein Institute of Mathematics at the Hebrew University of JerusalemScience in Context 17(1/2), 199-234 (2004); A blog post about Yaakov Levitzki  and the Amitzur-Levitzki theorem; Schappacher, Norbert:  Edmund Landau’s Göttingen — From the life and death of a great mathematical center.   Mathematical Intelligencer 13 (1991), 12-18. (Talk at the Dedication of the Landau Center for Research in Mathematical Analysis, Jerusalem, Feb. 28th, 1989). A recent post on Tao’s blog related to mathematics, science, scientific relations and recent events.

(Below) First and last page of Hardy and Heilborn obituary on Landau.

Boolean Functions: Influence, Threshold, and Noise

Here is the written version of my address at the 7ECM last July in Berlin.

Boolean functions, Influence, threshold, and Noise

Trying to follow an example of a 1925 lecture by Landau (mentioned in the lecture), the writing style is very much that of a lecture. It goes without saying that I will be very happy for corrections and suggestions of all kinds.

Laci Babai Visits Israel!

I am sure that every one of the readers of this blog heard about Laci Babai’s quasi-polynomial algorithm for graph isomorphism and also the recent drama about it: A mistake pointed out by Harald Helfgott,  a new sub-exponential but not quasi-polynomial version of the algorithm that Laci found in a couple of days, and then, a week later, a new variant of the algorithm again found by Laci which is  quasi-polynomial. You can read the announcement on Babai’s homepage, three excellent Quanta magazine articles by Erica Klarreich (I,II,III), Blog posts over Harald’s blog (III,II,I) with links to the video and article (in French), and many blog posts all over the Internet (GLL4,GLL3,GLL2,GLL1,…).

Babai’s result is an off-scale scientific achievement, it is wonderful in many respects, and I truly admire and envy Laci for this amazing breakthrough. I also truly admire  Harald  for his superb job as a Bourbaki expositor.

Laci Babai is visiting and he is giving lectures on graph isomorphism and related topics all over the Israel.

Tel Aviv University

Tel Aviv University: Sackler distinguished lectures in Pure Mathematics Wednesday, January 18 (Poster. Sorry, too late, I heard it was very inspiring, don’t miss the other talks!)

Tel Aviv University Combinatorics seminar:  Sunday, Jan. 22, 10:00-11:00, Location: Melamed (Shenkar building, ground floor, room 6)
Title: Canonical partitioning and the emergence of the Johnson graphs: Combinatorial aspects of the Graph Isomorphism problem

(The talk does not depend on Wednesday’s talk)

Hebrew University of Jerusalem

Hebrew University Colloquium San. Jan 22, 16:00-17:00 Title: Graph isomorphism and coherent configurations: The Split-or-Johnson routine

Lecture room 2, Manchester building (Mathematics)

The Technion

Local versus global symmetry and the Graph Isomorphism problem I–III

Lecture I: Monday, January 23, 2017 at 15:30

Lecture II: Tuesday, January 24, 2017 at 15:30

Lecture III: Thursday, January 26, 2017 at 15:30

All lectures will take place at Auditorium 232, Amado Mathematics Building, Technion (Website)

Weitzman Institute

Pekeris lecture, Jan 29, 11:00-12:00 Hidden irregularity versus hidden symmetry

EBNER AUDITORIUM (webpage)

Polymath10 conclusion

The Polymath10 project on the Erdos-Rado Delta-System conjecture took place over this blog from November 2015 to May 2016. I aimed for an easy-going project that people could participate calmly aside from their main research efforts and  the duration of the project was planned for one year. I also wanted to propose and develop my own homological approach to the problem.

The purpose of this post is to (belatedly) formally announce that the project has ended,  to give links to the individual posts and to briefly mention some advances and some thoughts about it.

The posts were

The problem was not solved and we did not come near a solution. The posts contain some summary of the discussions, a few results, and some proposals by the participants. Phillip Gibbs found a remarkable relation between the general case and the balanced case.  Dömötör Palvolgyi shot down quite a few conjectures I made, and Ferdinand Ihringer presented results about some Erdos-Ko-Rado extensions we considered  (In term of upper bounds for sunflower-free families). Several participants have made interesting proposals for attacking the problem.

I presented in the second post a detailed homological approach, and developed it further in the later threads  with the help of Eran Nevo and a few others. Then, after a major ingredient was shot down, I revised it drastically in the last post.

Participants made several computer experiments, for sunflower-free sets, for random sunflower-free sets, and also regarding the homologica/algebraic ideas.

The posts (and some comments) give some useful links to literature regarding the problem, and post 5 was devoted  to a startling development which occurred separately – the solution of the Erdos-Szemeredi sunflower conjecture for sunflowers with three petals following the cup set developments.  (The Erdos-Szemeredi sunflower conjecture is  weaker than the Erdos-Rado conjecture.)

The origin of my homological approach

A (too) strong version of the homological conjecture appeared in my 1983 Ph. D. thesis written in Hebrew. The typesetting used the Hebrew version of Troff.

Posted in Combinatorics, Open problems, Polymath10 | | 4 Comments

Five years ago I wrote a post entitled Is Backgammon in P? It was based on conversations with Peter Bro Miltersen and Uri Zwick (shown together in the above picture) about the computational complexity of computing the values (and equilibrium points) of various stochastic games, and also on some things I learned from my game theory friends over the years about proving that values exist for some related games. A few weeks ago  two former students of Peter, Rasmus Ibsen-Jensen and  Kristoffer Arnsfelt Hansen visited Israel and I had a chance to chat with them and learn about some recent exciting advances.

In what way is Backgammon harder than chess?

Is there a polynomial time algorithm for chess?  Well, if we consider the complexity of chess in terms of the board size then it is fair to think that the answer is “no”. But if we wish to consider the complexity in terms of the number of all possible positions then it is easy to go backward over all positions and determine  the outcome of the game when we start with each given position.

Now, what about backgammon?   Like chess, backgammon is a game of complete information.  The difference between backgammon and chess is the element of luck; at each position your possible moves are determined by a roll of two dice. This element of luck increases the computational  skill needed for playing backgammon compared to chess. It can easily be seen that optimal strategy for players in backgammon need not involve any randomness.

Problem 1: Is there a polynomial time algorithm to find the optimal strategy (and thus the value) of a stochastic zero sum game with perfect information? (Like backgammon)

This question (raised by Ann Condon in 1998) represents one of the most fundamental open problem in algorithmic game theory.

In what way is heads-up poker harder than backgammon?

Heads-up poker is just a poker game with two players.  To make it concrete you may think about heads-up Texas hold’em poker. This is not a game with complete information, but by according to the minmax theorem  it still has a value. The optimal strategies are mixed and involve randomness.

Problem 2: Is there a polynomial time algorithm to find the optimal strategy (and thus the value) of a stochastic zero-sum game with incomplete information? (like heads-up Texas hold’em poker).

It will be very nice to find even a sub-exponential algorithm for a stochastic zero-sum game with incomplete information like poker. Continue reading

The Median Game

Update: Apparently this game was invented already by Douglas Hofstadter who called it  “Mediocrity” and it is published in Hofstadter’s book Metamagical Themas: Questing for the Essence of Mind and Pattern. It is also called “Hruska.” (See here and here.)

Ehud Friedgut reminded me of the game MEDIAN which I proposed many years ago.

There are three players and they play the game for eight rounds. In every round all players simultaneously say a number between 1 and 8. A player whose number is (strictly) between the other two get a point. At the end of the game the winner is the player whose number of points is strictly between those of the others.

Posted in Games | Tagged | 4 Comments

International mathematics graduate studies at the Hebrew University of Jerusalem

I am very happy to announce that a Ph. D program in mathematics for international students at the Hebrew University of Jerusalem is now open. Here is the link to the home page.

Our Institute

The institute was inaugurated in 1925 by a lecture of Edmund Landau, who later served as one of the first heads of the department. It has since developed into a defining and leading place in mathematics research, with world renowned research faculty working in diverse areas of up-to-date research.

Our graduate program gives students the chance to develop into researchers that shape mathematics of the future. The department offers a uniquely attractive environment to learn and work, with weekly seminars, frequent special lecture series on current topics in mathematics and scientific exchange with visiting researchers from around the world.

The environment

This is enriched further by the Israel Institute of Advanced Studies situated at Hebrew University that organizes thematic years on state-of-the art advances in science, and the close collaboration with the renowned departments of physics and computer science and engineering. You can venture even further and visit the nearby University of Tel Aviv, the Technion, the Weizmann Institute, Bar Ilan University, Ben Gurion University or the University of Haifa, that contribute to the active research environment and that we here enjoy a frequent and close scientific exchange with. Continue reading

Polynomial Method Workshop

The workshop on the  “polynomial method” will take place at the Hebrew University of Jerusalem on Monday Dec 26 and Tuesday Dec 27. The event is organized by Jordan Ellenberg and Gil Kalai.

Program:

Monday 10-11:45  (Combinatorics seminar) Adam Shefer – Geometric Incidences and the Polynomial Method

Location: Rothberg (CS) B220

On Monday afternoon we will have four talks at the library of Belgium house by

13:15-14:00  Peter Pach,  Progression-free sets. New: SLIDES
14:10-14:55 Shoham Letzter,

15:15-16:00 Jordan Ellenberg,
16:10- 16:55 Fedya Petrov, Group rings vs. polynomials. New: SLIDES

and a problem session moderated by Jordan starting at 16:55. New: PROBLEMS.

On Tuesday we start at 9:30 and will have four talks at the library of Belgium house:

9:30-10:15 Noga Alon,  Combinatorial Nullstellensatz and its algorithmic aspects. New: SLIDES
10:35-11:20  Olga Holtz, A potpourri on power ideals, hyperplane
arrangements, graphs, and zonotopes (NEW: SLIDES)

11:30- 12:15 Aart Blokhuis,  The polynomial method in finite geometry

( lunch)

Wednesday 9:30-10:15,  Anurag Bishnoi, zeros of polynomials over a finite grid.  NEW:SLIDE.

Thursday 11:00-12:00 Seva Lev,  Avoiding 3AP with differences in $\{0,1\}^n$ Room 209 Mathematics.

Further informal discussions and talks may continue on Wednesday/Thursday.

The Thursday 14:30 Colloquium by Jordan Ellenberg will be on The cap set problem.

I will update titles as they come along.

Amazing: Stefan Glock, Daniela Kühn, Allan Lo, and Deryk Osthus give a new proof for Keevash’s Theorem. And more news on designs.

Blogging was slow recently, and I have various half written posts on all sort of interesting things, and plenty of unfulfilled promises. I want to quickly share with you two and a half news items regarding combinatorial designs. As you may remember Peter Keevash proved the century old conjecture on the existence of designs. We talked about it in this post, and again in this post. I wrote a Bourbaki exposition about this development and related results and problems. I gained some (rather incomplete) understanding of the proof by listening to Peter’s lectures, looking at the papers, talking to people, preparing to my lecture about it, writing the presentation, and  incorporating remarks of people who read earlier versions and pointed out that I miss some important ingredient.

The existence of designs – second proof!

A new proof for Keevash’s theorem on the existence of designs was discovered by  Stefan Glock, Daniela Kühn, Allan Lo, and Deryk Osthus! The proof is given in the paper  The existence of designs via iterative absorption, and the paper contains also some new applications of the method of proof. This is great news! A second proof to a major difficult theorem is always very very important and exciting.  Keevash’s theorem gave a vast generalization of the problem for decompositions of hypergraphs to complete subhypergraphs  and the new theorem is even a much more general hypergraph decomposition theorem. Congratulations!

New q-analogs of designs

One of the important open problems about designs is the existence of q-analogs. The first example was given in 1987 by Simon Thomas. Michael  Braun, Tuvi Etzion , Patric R. J. Östergard , Alexander Vardy,  and Alferd Wasserman found  remarkable new q-designs. See also this article: Researchers found mathematical structure that was thought not to exist.  Congratulations! It is an interesting question if the new existence methods apply to q-analogs (and perhaps in greater generality for all sort of algebraic gadgets).

Some more things

As part of a project with Nati Linial and Yuval Peled I was interested in finding a k-dimensional simplicial complex on k(k-1) vertices with a complete (k-1)-dimensional skeleton, with vanishing rational homology so that every (k-1) face is included in the same number of k-faces. (This “same number” must be k.) Better still I want all links of i-faces to be combinatorially the same. For k=2 the 6-vertex triangulation of  $\mathbb R P^2$  is an example, but I did not have any other example. I asked about it on MathOverflow and  GNiklasch identified a remarkable example for k=3. (And there are some hopes for k=4.) Actually, I need to devote a post to MathOverflow experiences. I got answers there to several problems that intrigued me for decades.

One more thing: Daniela Kühn and Deryk Osthus were involved in recent years (sometimes with coauthors) in knocking out some very important problems in graph theory and extremal combinatorics. Their ICM14 survey describes some of their works related to Hamiltonian cycles including their solution to the famous Kelly’s conjecture.