论文标题
额头协议上的算法数，产生密集的Ruzsa-Szemerédi图和超图形
Algorithmic Number On the Forehead Protocols Yielding Dense Ruzsa-Szemerédi Graphs and Hypergraphs
论文作者
论文摘要
我们在额头协议上描述了提供密集的Ruzsa-Szemerédi图的算法数。一种协议导致了Ruzsa和Szemerédi的原始结构的简单自然扩展。该协议引起的图形具有$ n $顶点，$ω（n^2/\ log n）$边缘，可分解为$ n^{1+o（1/\ log \ log \ log n）} $诱导的匹配。另一个协议是Alon，Moitra和Sudakov的构建的明确（稍微简单），生成具有相似属性的图形。我们还将上述协议概括为三个以上的播放器，以构建密集的均匀的超图，其中每个边缘都在少量的少数简单中。
We describe algorithmic Number On the Forehead protocols that provide dense Ruzsa-Szemerédi graphs. One protocol leads to a simple and natural extension of the original construction of Ruzsa and Szemerédi. The graphs induced by this protocol have $n$ vertices, $Ω(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.
