Hyper-regular graphs and high dimensional expanders
Hyper-regular graphs and high dimensional expanders
复制标题
超正则图和高维扩展器
DOI：
--
复制
发表时间：
2020
影响因子：
1
通讯作者：
Yonatan Iluz
中科院分区：
文献类型：
--
作者：
E. Friedgut;Yonatan Iluz
设G=(V，E)是有限图。对于d0>；0，我们说G是d0-正则的，如果每个v∈V都有d0次。我们说G是(d0，d1)-正则的，对0<；d1<；d0，如果G是d0正则的，且对每个v∈V，在v的邻域上诱导的子图是d1-正则的。类似地，G是(d0，d1，⋯，dN−1)-正则的，如果对0<；dn−1<；⋯<；d1<；d0，如果G是d0正则的，且对于每个v∈V，在v的邻域上诱导的子图是(d1，⋯，dn−1)-正则的(即，对于每1个≤i≤n−1，每个大小为i的团的联合邻域是双正则的)；在这种情况下，我们说G是n维超正则图。在这里我们定义了一种新的图积，通过它我们构造了n维HRG的无限族的例子，使得每个大小不超过n−1的团的联合邻域是连通的。特别是，依赖于Kaufman和Oppenheim的工作，我们的积得到了对任意大的n具有良好扩展性质的n维HRG的无限族。这回答了迪努尔关于这种物体存在的问题。
Let G = (V, E) be a finite graph. For d0 > 0 we say that G is d0-regular, if every v ∈ V has degree d0. We say that G is (d0, d1)-regular, for 0 < d1 < d0, if G is d0 regular and for every v ∈ V, the subgraph induced on v’s neighbors is d1-regular. Similarly, G is (d0, d1,⋯,dn−1)-regular for 0 < dn−1 < ⋯ < d1 < d0, if G is d0 regular and for every v ∈ V, the subgraph induced on v’s neighbors is (d1,⋯,dn−1)-regular (i.e., for every 1 ≤ i ≤ n − 1, the joint neighborhood of every clique of size i is di-regular); in that case, we say that G is an n-dimensional hyper-regular graph (HRG). Here we define a new kind of graph product, through which we build examples of infinite families of n-dimensional HRG such that the joint neighborhood of every clique of size at most n − 1 is connected. In particular, relying on the work of Kaufman and Oppenheim, our product yields an infinite family of n-dimensional HRG for arbitrarily large n with good expansion properties. This answers a question of Dinur regarding the existence of such objects.
影响因子：
--
作者：
Jérôme Kunegis
通讯作者：
Jérôme Kunegis