HUJI Combinatorics Seminar 


When: Monday Nov 30th, 2020 11AM


Zoom link: https://huji.zoom.us/j/85226464650?pwd=Tk13TEtEekJVMklUWWNnTjhlOGdNUT09

Speaker: Ehud Friedgut (Weizmann)

Title:  A quest for Hyper Regular Graphs

Abstract:

A graph is a-regular if all vertices have degree a, it's (a, b)-regular if it's a-regular, and the graph induced on the neighborhood of every vertex is (a, b)-regular. And so on and so forth: it's (a, b, c)-regular if it's a-regular and every neighborhood is (b, c)-regular. For example K_n, is (n-1,n-2,...,1)-regular, and so are graphs consisting of disjoint unions of it. However, the disjoint unions are not connected. This raises the following question:
For a fixed tuple (a, b, c, ...), do there exist arbitrarily large finite (a, b, c, ...)-regular graphs where the graphs, the neighborhoods, the second neighborhoods etc. are connected? This question was raised by Irit Dinur in the context of designing high-dimensional expanders, hence the hope was that if such beasts exist, the neighborhoods are not only connected but also have good expansion. 
Prior to this work, some examples of connected and link connected (a, b)-regular graphs were known, but no such (a, b, c)-regular graphs. So, with a student of mine, Yonatan Iluz, we set out on a quest to discover such objects or to prove they do not exist.
In this talk, I'll present the results of our quest.