Ehud Friedgut

A quest for Hyper Regular Graphs

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 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,\ldots,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,\ldots), do there exist arbitrarily large finite (a,b,c\ldots)-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 that they do not exist.
In this talk, I'll present the results of our quest.