@HUJI

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 is known is d=4, where there is known to be one 16 vertex triangulation. In his talk, we will study this object in some detail. In the first part of the talk, we give one construction of this object, and study its combinatorial properties, including the remarkable 16_6 configuration of its vertices which naturally extends to the 22-point Witt design. In the next part, we reconsider the minimal triangulations of and and see how they can be generalized to two more constructions of a 16-vertex both of which, somewhat surprisingly, turn out to be the complex in our first construction.

(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  then where

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 -cohomology was introduced by Gromov and independently by Linial, Meshulam and Wallach. We will see that for this generalization there is no direct higher dimensional analogue of the lower bound of the Cheeger inequality.

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