Algorithmic Number On the Forehead Protocols Yielding Dense Ruzsa-Szemerédi Graphs and Hypergraphs
Algorithmic Number On the Forehead Protocols Yielding Dense Ruzsa-Szemerédi Graphs and Hypergraphs
复制标题
额头协议上的算法数产生密集的 Ruzsa-Szemerédi 图和超图
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
A. Shraibman
中科院分区：
文献类型：
--
作者：
N. Alon;A. Shraibman
我们描述了提供密集 Ruzsa-Szemeredi 图的算法 Number On the Forehead 协议。一项协议可以对 Ruzsa 和 Szemeredi 的原始结构进行简单而自然的扩展。该协议生成的图有 $n$ 个顶点、$Omega(n^2/log n)$ 个边，并且可分解为 $n^{1+O(1/log log n)}$ 生成的匹配。另一个协议是 Alon、Moitra 和 Sudakov 构造的显式（且稍微简单）版本，生成具有类似属性的图。我们还将上述协议推广到三个以上的参与者，以构造密集的均匀超图，其中每条边都位于正的少量单纯形中。
We describe algorithmic Number On the Forehead protocols that provide dense Ruzsa-Szemeredi graphs. One protocol leads to a simple and natural extension of the original construction of Ruzsa and Szemeredi. The graphs induced by this protocol have $n$ vertices, $Omega(n^2/log n)$ edges, and are decomposable into $n^{1+O(1/log log n)}$ induced matchings. Another protocol is an explicit (and slightly simpler) version of the construction of Alon, Moitra and Sudakov, producing graphs with similar properties. We also generalize the above protocols to more than three players, in order to construct dense uniform hypergraphs in which every edge lies in a positive small number of simplices.