Combinatorics: Amitay Kamber (HUJI)

HUJI Combinatorics Seminar 

When: Monday April 19th, 2021, at 10:30AM

Zoom link:

Speaker:  Amitay Kamber (HUJI)
Title: Combinatorics via Closed Orbits: Vertex Expansion and Graph Quantum Ergodicity

A Lossless expander is a d-regular graph such that small sets with m vertices have close to dm neighbors. Explicit construction of a family of such graphs will have a lot of applications– for example, they are unique neighbor expanders. 

It is believed is that the Ramanujan graph (i.e., graphs with an optimal spectral gap) that are constructed from number theory, such as the celebrated graphs of Lubotzky, Phillips, and Sarnak, are lossless expanders. We show that this belief is actually false – one can construct arithmetic Ramanujan graphs with a small subset having no unique neighbors. 

Our graphs also have an eigenfunction of the adjacency operator of small support, again contradicting common expectations in the field of graph quantum ergodicity.
The construction is based on a general method of constructing extremal combinatorial objects from closed orbits of subgroups of semisimple p-adic groups. Similar ideas are very common in number theory and homogeneous dynamics, and we introduce them to combinatorics.

Joint work with Tali Kaufman.


Mon, 19/04/2021 - 10:30 to 12:30