Hypergraph expanders from Cayley graphs
Hypergraph expanders from Cayley graphs
复制标题
凯莱图的超图扩展器
DOI：
--
复制
发表时间：
2017
影响因子：
1
通讯作者：
D. Conlon
中科院分区：
文献类型：
--
作者：
D. Conlon
提出了一种构造具有强扩展性质的稀疏3-一致超图的简单机制，该机制可以随机化。这些超图是用Cayley图在\begin{document}$$\mathbb{Z}_{2}^{t}$$\end{document}上构造的，它的顶点数是多对数的。它们的展开性来自于基本的Cayley图，包括图的顶点和边展开的类似性、骨架图边上随机游动的快速混合、大顶点子集上边的均匀分布和几何重叠性质。
We present a simple mechanism, which can be randomised, for constructing sparse 3-uniform hypergraphs with strong expansion properties. These hypergraphs are constructed using Cayley graphs over ℤ2t\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb{Z}_{2}^{t}$$\end{document} and have vertex degree which is polylogarithmic in the number of vertices. Their expansion properties, which are derived from the underlying Cayley graphs, include analogues of vertex and edge expansion in graphs, rapid mixing of the random walk on the edges of the skeleton graph, uniform distribution of edges on large vertex subsets and the geometric overlap property.
凯莱图所有均匀性的超图扩展器
影响因子：
1.8
作者：
Conlon, David;Tidor, Jonathan;Zhao, Yufei
通讯作者：
Zhao, Yufei
随机斯坦纳系统和每个维度的有界度共界扩展器
影响因子：
0.8
作者：
Lubotzky, Alexander;Luria, Zur;Rosenthal, Ron
通讯作者：
Rosenthal, Ron
DOI：
10.4171/owr/2016/46
发表时间：
2016
期刊：
Oberwolfach Reports
影响因子：
--
作者：
Loeser F
通讯作者：
Loeser F