Speaker: Eyal Karni (BIU)

Title: Combinatorial high dimensional expanders

Abstract:

An eps-expander is a graph G=(V,E) in which every set of vertices X where |X|<=|V|/2 satisfies |E(X,X^c)|>=eps*|X| . There are many edges that "go out" from any relevant set.

Over the last two decades or so, there have been various attempts to generalize this notion to higher dimensions. That means to talk about expansion in hypergraphs. There has been a growing interest in this field, motivated partially by its usefulness to constructing quantum error correcting codes. As the field is still in its infancy, There are limited ways to construct high dimensional expanders, and they typically rely upon heavy algebraic tools, while the hypergraphs are defined explicitly.

In his paper from 2017, David Conlon offered a simple combinatorial way to construct a 3 uniform hypergraph that satisfies some HD expansion properties. It is also randomizable, and edge-triangle-edge random walks on it converge rapidly. But, it has a drawback. It is based upon Abelian groups, so the provided expansion is limited.

There were some recent attempts to tackle that. Namely, in a paper by Michael Chapman, Nati Linial, Yuval Peled and an attempt by myself (under the guidance of Tali Kaufman).

The idea was also generalized recently to higher dimensions by David Conlon.

We will discuss the construction, its adaptions and generalizations.

(well, some of them, as much as the time allows).

Title: Combinatorial high dimensional expanders

Abstract:

An eps-expander is a graph G=(V,E) in which every set of vertices X where |X|<=|V|/2 satisfies |E(X,X^c)|>=eps*|X| . There are many edges that "go out" from any relevant set.

Over the last two decades or so, there have been various attempts to generalize this notion to higher dimensions. That means to talk about expansion in hypergraphs. There has been a growing interest in this field, motivated partially by its usefulness to constructing quantum error correcting codes. As the field is still in its infancy, There are limited ways to construct high dimensional expanders, and they typically rely upon heavy algebraic tools, while the hypergraphs are defined explicitly.

In his paper from 2017, David Conlon offered a simple combinatorial way to construct a 3 uniform hypergraph that satisfies some HD expansion properties. It is also randomizable, and edge-triangle-edge random walks on it converge rapidly. But, it has a drawback. It is based upon Abelian groups, so the provided expansion is limited.

There were some recent attempts to tackle that. Namely, in a paper by Michael Chapman, Nati Linial, Yuval Peled and an attempt by myself (under the guidance of Tali Kaufman).

The idea was also generalized recently to higher dimensions by David Conlon.

We will discuss the construction, its adaptions and generalizations.

(well, some of them, as much as the time allows).

## Date:

Mon, 10/06/2019 - 11:00 to 13:00

## Location:

CS bldg, room B-500, Safra campus