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, Ω (n2/ log n) edges, and are decomposable into n1+O(1/loglogn) induced matchings.Another protocol is a somewhat simpler version of theconstruction of , 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.
All Science Journal Classification (ASJC) codes
- NOF protocol
- Ruzsa–Szemerédi graph
- communication complexity
- induced matching