论文标题
高规范图和高维扩展器
Hyper-regular graphs and high dimensional expanders
论文作者
论文摘要
令$ g =（v，e）$为有限图。对于$ d_0> 0 $，我们说$ g $是$ d_0 $ regular，如果每个$ v \ in v $ in v $都有$ d_0 $。我们说$ g $是$（d_0，d_1）$ - 常规，如果$ 0 <d_1 <d_0 $，如果$ g $是$ d_0 $常规的，则对于v $中的每一个$ v \，在$ v $ $ v $的邻居上诱导的子图是$ d_1 $ - regular。 Similarly, $G$ is $(d_0, d_1,\ldots, d_{n-1})$-regular for $0<d_{n-1}<\ldots<d_1<d_0$, if $G$ is $d_0$ regular and for every $1\leq i\leq n-1$, the joint neighborhood of every clique of size $i$ is $d_i$-regular;在这种情况下，我们说$ g $是$ n $ dimensional hr-graph Graph（HRG）。在这里，我们定义了一种新型的图形产品，通过它构建了无限家庭的示例，$ n $二维的HRG，使每个大小的共同社区最多可以连接到$ n-1 $。尤其是依靠考夫曼和奥本海姆的工作，我们的产品产生了一个无限的$ n $ dimensional hrg家族，用于任意大型$ n $，具有良好的扩展属性。这回答了关于此类物体存在的Dinur问题。
Let $G= (V,E)$ be a finite graph. For $d_0>0$ we say that $G$ is $d_0$-regular, if every $v\in V$ has degree $d_0$. We say that $G$ is $(d_0, d_1)$-regular, for $0<d_1<d_0$, if $G$ is $d_0$ regular and for every $v\in V$, the subgraph induced on $v$'s neighbors is $d_1$-regular. Similarly, $G$ is $(d_0, d_1,\ldots, d_{n-1})$-regular for $0<d_{n-1}<\ldots<d_1<d_0$, if $G$ is $d_0$ regular and for every $1\leq i\leq n-1$, the joint neighborhood of every clique of size $i$ is $d_i$-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.
