# School Starts at HUJI

We are now starting the third week of the academic year at HUJI. As usual, things are very hectic, a lot of activities in the mathematics department, in our sister CS department, around in the campus, and in our combinatorics group. A lot is also happening in other universities around. This semester I am teaching a course on “Social Choice and some Topics from Cooperative Game Theory” in our Federmann Center for the Study of Rationality. I will probably create a page for the course in the near future. During the summer we ran an informal multi-university research activity on analysis of Boolean functions where for two months we met every week for a whole day. I will try to report on what we were studying  and we will probably meet during the academic year 2-3 times each semester.

A few of many future events: Later this month we will have here a cozy Polish-Israeli meeting on  topological combinatorics, on December we will celebrate Ilya Rips 65 birthday with a conference on  geometric and combinatorial group theory, and at the last two weeks of January our traditional The 18th yearly midrasha (school) in mathematics that will be devoted to combinatorics with six lecture series and a few additional talks aimed at teaching some of the very latest exciting developments. If you did not register yet to the Midrasha, please go ahead and do so. This can be a very nice opportunity to visit Israel and learn some exciting combinatorics and to meet people. Partial support for travel and local expenses is available.

COMBSEM – weeks I, II, III

Our weekly combinatorics seminar is meeting on Mondays 9-11. Let me tell you a little on what we had in the first two weeks and what is planned for the third.

Week I:  A startling extension of the associahedron

Monday, October 27, 11:00–13:00, at room B221 in Rothberg building
(new CS and engineering building).

Speaker: Jean-Philippe Labbé, HU

Title: A construction of complete multiassociahedric fans

Abstract:
Originally, Coxeter groups emerged as an algebraic abstraction of
groups generated by reflections in a vector space. The relative
generality of their definition allows them to be related to many
combinatorial, geometric and algebraic objects. This talk show cases
recent developments in the study of a family of simplicial spheres
describing multi-triangulations of convex polygons based on
combinatorial aspects of Coxeter groups of type A. This family of
simplicial spheres generalizes the associahedra. A conjecture of
Jonsson (2003) asserts that these simplicial spheres can be realized
geometrically as the boundary complex of a convex polygon, that would
be thus called multiassociahedron. We will describe a
construction method to obtain complete simplicial fans realizing an
infinite non-trivial family of multi-associahedra.  At it turned out,  Jonsson’s conjecture is closely related to a conjecture by Miller and Knudson.
This is joint work with Nantel Bergeron and Cesar Ceballos (Fields
Institute and York Univ.).

Week II: Finally, progress on Withenhausen’s problem in 2 dimension

Speaker: Evan deCorte, HU

Title: Spherical sets avoiding a prescribed set of angles

Abstract: Let X be any subset of the interval [-1,1]. A subset I of
the unit sphere in $R^n$ will be called X-avoiding if <u,v> is not in X
for any u,v in I. The problem of determining the maximum surface
measure of a {0}-avoiding set was first stated in a 1974 note by H.S.
Witsenhausen; there the upper bound of 1/n times the surface measure
of the sphere is derived from a simple averaging argument. A
consequence of the Frankl-Wilson theorem is that this fraction
decreases exponentially, but until now the 1/3 upper bound for the
case n=3 has not moved. We improve this bound to 0.313 using an
approach inspired by Delsarte’s linear programming bounds for codes,
combined with some combinatorial reasoning. In the second half of the
talk, we turn our attention to the following question: Does there
exist an X-avoiding subset of the unit sphere maximizing the surface
measure among all X-avoiding subsets? (Or could there be a supremum
measure which is never attained as a maximum?) Using a combination of
harmonic and functional analysis, we show that a maximizer must exist
when n is at least 3, regardless of X. When n=2, the existence of a
maximizer depends on X; sometimes it exists, sometimes it does not.
This is joint work with Oleg Pikhurko.

Week III (coming up tommorow): Ramsey numbers for cliques vs cubes conquered at last!

Speaker: Gonzalo Fiz Pontiveros, HU

Title:  The Ramsey number of the clique and the hypercube

Abstract:
The Ramsey number $r(K_s,Q_n)$ is the smallest positive integer N
such that every red-blue colouring of the edges of the complete graph
$K_N$ on N vertices contains either a red n-dimensional hypercube,
or a blue clique on s vertices. It was conjectured in 1983 by
Erdos and Burr that $r(K_s,Q_n)=(s-1)(2^{n}-1)+1$ for every
positive integer s and every sufficiently large n. The aim of the
talk is to give an overview of the proof of this result and, if time
allows it, discuss some related problems.

Joint work with S. Griffiths, R.Morris, D.Saxton and J.Skokan.

# In And Around Combinatorics: The 18th Midrasha Mathematicae. Jerusalem, JANUARY 18-31

The 18th yearly school in mathematics is devoted this year to combinatorics. It will feature lecture series by Irit Dinur, Joel Hass, Peter Keevash, Alexandru Nica, Alexander Postnikov, Wojciech Samotij, and David Streurer and additional activities. As usual grants for local and travel expences are possible.

# Media Item from “Haaretz” Today: “For the first time ever…”

Maryam Mirzakhani received the medal from South Korea’s president Park Geun-hye.

Here is an article from today’s Israeli newspaper Haaretz.  It is based on this article by the Guardian (Thanks, Manor!).  See also this post on Laba’s accidental mathematician and John Baez’ Google+ post.

The ICM 2014 started today in Seoul. The International congress taking place once every four years is an exciting event, celebrated by thousands of mathematicians in Seoul and many others all over the world. The opening ceremonies came with the announcement of  Artur Avila, Manjul Bhargava, Martin Hairer, and Maryam Mirzakhani as 2014 Fields medalist, Subhash Khot won the Nevanlinna prize, Stanley Osher won the Gauss prize and Phillip Griffiths is the Chern medalist, and  Adrián Paenza won the Leelavati Prize. Heartly congratulations to Artur, Manjul, Martin, Maryam, Subhash, Stanley, Phillip, and Adrián! This is also the first for Brazil, Austria, Canada, and Iran! More on the Fields medalists works can be found on Terry Tao’s blog. (New) And here is a live bloging (with pictures) on ICM2014 day 1 from Gowers’s blog.   And also here from the ICM site on the work of all prize recipients. And from Quanta Magazine: (More) More on Osher, Griffiths, and Khot on terry Tao’s blog, on Khot on Scott Aaronson’s blog and on a description of the laudations on Gowers blog.

# Jim Geelen, Bert Gerards, and Geoﬀ Whittle Solved Rota’s Conjecture on Matroids

Gian Carlo Rota

## Rota’s conjecture

I just saw in the Notices of the AMS a paper by Geelen, Gerards, and Whittle where they announce and give a high level description of their recent proof of Rota’s conjecture. The 1970 conjecture asserts that for every finite field, the class of matroids representable over the field can be described by a finite list of forbidden minors. This was proved by William Tutte in 1938 for binary matroids (namely those representable over the field of two elements). For binary matroids Tutte found a single forbidden minor.  The ternary case was settled by by Bixby and by Seymour in the late 70s (four forbidden minors).  Geelen, Gerards and Kapoor proved recently that there are seven forbidden minors over a field of four elements.  The notices paper gives an excellent self-contained introduction to the conjecture.

This is a project that started in 1999 and it will probably take a couple more years to complete writing the proof. It relies on ideas from the Robertson-Seymour forbidden minor theorem for graphs. Congratulations to Jim, Bert, and Geoff!

Well, looking around I saw that this was announced in August 22’s post in a very nice group blog devoted by matroids- Matroid Union, with contributions by Dillon Mayhew, Stefan van Zwam, Peter Nelson, and Irene Pivotto. August 22? you may ask, yes! August 22, 2013. I missed the news by almost a year. It was reported also here and here  and here, and here, and here, and here!

This is a good opportunity to mention two additional conjectures by Gian-Carlo Rota. But let me ask you, dear readers, before that a little question.

## Rota’s unimodality conjecture and June Huh’s work

Rota’s unimodality conjecture predicts that the coefficients of the characteristic polynomial of a matroid form a log-concave sequence. This implies that the coefficients are unimodal. A special case of the conjecture is an earlier famous conjecture (by Read) asserting that the coefficients of the chromatic polynomial of a graph are unimodal (and log-concave). This conjecture about matroids was made also around the same time by Heron and Welsh.

June Huh proved Reads’ unimodality conjecture for graphs and the more general Heron-Rota-Welsh conjecture for representable matroids for characteristic 0. Later Huh and  Eric Katz proved the case of  representable matroids for arbitrary characteristics. I already mentioned these startling results earlier and we may come back to them later.

Huh’s path to mathematics was quite amazing. He wanted to be a science-writer and accomponied Hironaka on whom he planned to write. Hironaka introduced him to mathematics in general and to algebraic geometry and this led June to study mathematics and a few years later to use deep connections between algebraic geometry and combinatorics to prove the conjecture.

## Rota’s basis conjecture

Rota’s basis conjecture from the late 80’s appears to remain wide open. The problem first appeared in print in a paper by Rosa Huang and Rota. Here is a post about it also from “the matroid union.” It is the first problem in Rota’s article entitled “Ten Mathematics problems I will never solve“. Having access only to page one of the paper I can only guess what the other nine problems might be.

Rota’s portrait by Fan Chung Graham

# Pictures from Recent Quantum Months

A special slide I prepared for my lecture at Gdansk featuring Robert Alicki and I as climber on the mountain of quantum computers “because it is not there.”

It has been quite a while since I posted here about quantum computers. Quite a lot happened in the last months regarding this side of my work, and let me devote this post mainly to pictures. So here is a short summary going chronologically backward in time. Last week – Michel Dyakonov visited Jerusalem, and gave here the condensed matter physics seminar on the spin Hall effect. A couple of weeks before in early January we had the very successful Jerusalem physics winter school on Frontier in quantum information. (Here are the recorded lectures.) Last year I gave my evolving-over-time lecture on why quantum computers cannot work in various place and different formats in Beer-Sheva, Seattle, Berkeley, Davis (CA), Gdansk, Paris, Cambridge (US), New-York, and Jerusalem. (The post about the lecture at MIT have led to a long and very interesting discussion mainly with Peter Shor and Aram Harrow.) In August I visited Robert Alicki, the other active QC-skeptic, in Gdansk and last June I took part in organizing a (successful) quantum information conference Qstart in Jerusalem (Here are the recorded lectures.).

And now some pictures in random ordering

With Robert Alicki in Gdynia near Gdansk

With (from left) Connie Sidles, Yuri Gurevich, John Sidles and Rico Picone in Seattle  (Victor Klee used to take me to the very same restaurant when I visited Seattle in the 90s and 00s.) Update: Here is a very interesting post on GLL entitled “seeing atoms” on John Sidles work.

With Michel Dyakonov (Jerusalem, a few days ago)

With Michal Horodecki in Sopot  near Gdansk (Michal was a main lecturer in our physics school a few weeks ago.)

Aram Harrow and me meeting a year ago at MIT.

Sometimes Robert and I look skeptically in the same direction and other times we look skeptically in opposite directions. These pictures are genuine! Our skeptical face impressions are not staged. The pictures were taken by Maria, Robert’s wife. Robert and I are working for many years (Robert since 2000 and I since 2005) in trying to examine skeptically the feasibility of quantum fault-tolerance. Various progress in experimental quantum error-correction and other experimental works give good reasons to believe that our views could be examined in the rather near future.

A slide I prepared for a 5-minute talk at the QSTART rump session referring to the impossibility of quantum fault-tolerance as a mild earthquake with wide impact.

This is a frame from the end-of-shooting of a videotaped lecture on “Why quantum computers cannot work” at the Simons Institute for the Theory of Computing at Berkeley. Producing a videotaped lecture is a very interesting experience! Tselil Schramm (in the picture holding spacial sets of constant width) helped me with this production.