Ilya Rips and me during Ilyafest last week (picture Itai Benjamini)
Ilya Rips Birthday Conference
Last week we had here a celebration for Ilya Rips’ birthday. Ilya is an extraordinary mathematician with immense influence on algebra and topology. There were several startling ongoing mathematical projects that he is involved with that were discussed. One is a very ambitious project with Alexei Kanel-Belov is to get a “small cancellation theory” for rings and this has already fantastic consequences. Another is a work with Yoav Segev and Katrin Tent, on sharply 2- transitive groups, that answered a major old question with connections to groups, rings, and geometry. Happy birthday, Ilya!
Achimedes on infinity
Reviel Netz (רויאל נץ) gave a seminar lecture in the department about infinity in Archimedes’ mathematical thoughts that developed into an interesting conversation. The lecture took place a day after Netz’s second poetry book (in Hebrew) appeared.
The combinatorics school (midrasha) is coming.
Two weeks with extensive illuminating lecture series. Do not miss!
At Combsem
On our Monday combinatorics seminar, we had, since my last report, three excellent lectures. And next Monday we are having Avi Wigderson.
Dec 1
Speaker: Sonia Balagopalan, HU
Title: A 16-vertex triangulation of the 4-dimensional real projective space
Abstract:
Very little is known about the problem of finding minimal (simplicial) triangulations of real projective spaces. In fact the largest dimension d for which a vertex minimal triangulation of 
(Sonia’s talk led to my question regarding automorphisms of the symmetric group.)
Dec 8
Speaker: Eoin Long, Tel Aviv University
Title: Frankl-Rodl type theorems for codes and permutations
Abstract:
How large can a family F of subsets of [n] be if the intersection of every two sets A,B in F has cardinality different from t? The Frankl-Rodl theorem shows that if 
In this talk I will describe a new proof of this theorem. Our method extends to codes with forbidden distances, where over large alphabets our bound is significantly better than that obtained by Frankl and Rodl. One consequence of this result is a Frankl-Rodl type theorem for permutations with a forbidden distance.
Joint work with Peter Keevash.
Dec 15
Speaker: Anna Gundert, University of Cologne
Title: Higher-Dimensional Discrete Cheeger Inequalities
Abstract:
For graphs, the notion of expansion is a highly useful concept that has found applications in various areas, especially in combinatorics and theoretical computer science. In recent years, the success of this concept has inspired the search for a corresponding notion in higher dimensions.
Expansion for graphs can be expressed combinatorially or via the spectrum of the Laplacian. The close connection of these two notions is expressed, e.g., by the discrete Cheeger inequality, the lower bound of which states that the spectral gap of a graph G is at most the Cheeger constant measuring the edge expansion of G.
This talk adresses generalizations of expansion properties to finite simplicial complexes of higher dimension. Whereas higher dimensional Laplacians were introduced already in the 1940s by Eckmann, the generalization of edge expansion to simplicial complexes is not straightforward.
Recently, a topologically motivated notion analogous to edge expansion that is based on 
A different, combinatorially motivated generalization of the Cheeger constant was studied by Parzanchevski, Rosenthal and Tessler. They showed that the spectral gap of a k-complex X with complete (k-1)-skeleton is indeed bounded above by this Cheeger constant. We will see how this can be extended to arbitrary complexes.
Joint work with Uli Wagner and May Szedlak.
Dec 22
Speaker: Felix Goldberg, Haifa University
Title: Power laws, sandpiles, and pseudo-inverses.
The talk was on the Chip-firing -game model of Bjorner, Lovasz and Shor. Felix gave a large improvement for the time it takes to the game to stabilize for certain classes of graphs. This used tools from matrix theory. Here is the detailed abstract (in pdf).
Dec 29
Speaker: Avi Wigderson, IAS
Title: Sum-of-Squares (SOS) proofs and algorithms for the Planted Clique problem
Abstract:
I will start by explaining, motivating and giving the historical background for both the Planted Clique problem as well as the computational model – the SOS/Lasserre hierarchy of semi-definite programs.
The main result of this work is an average-case lower bound on the number of rounds required by to solve the planted clique problem in random graphs. Roughly speaking, d rounds of SOS cannot find a planted k-clique in a random graph on n vertices unless
I will describe some of the mathematical techniques that are needed for proving that sum-of-squares algorithms require many rounds to find planted cliques in random graphs. In particular, I will explain how to construct a “dual certificate” (aka vector solution, aka pseudo-expectation) for *every* graph. This reduces the problem to showing that a certain random matrix associated to the graph is PSD (Positive Semi-Definite). Proving this statement splits into two sub-problems. One is proving that the expectation of the random matrix is PSD – this part uses the theory of association schemes and in particular the Johnson scheme, which I will introduce. The second is proving that the random matrix is concentrated about its expectation. This will require new large deviation results for matrices with correlated entries.
No special background will be assumed.
Joint work with Raghu Meka and Aaron Potechin
