Number on the Forehead Protocols yielding dense Ruzsa–Szemerédi graphs and hypergraphs

We describe algorithmic Number On the Forehead protocols thatprovide 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²/ log n) edges, and are decomposable into n^{1+O(1/loglogn)} induced matchings.Another protocol is a somewhat simpler version of theconstruction of [1], producing graphs with similar properties.We also generalize the above protocols to morethan three players, in orderto construct dense uniformhypergraphs in which every edge lies in a positivesmall number of simplices, extending a result of Fox and Loh.