Abstract
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, \(\Omega(n^2/\log n)\) edges, and are decomposable into \(n^{1+O(1/\log \log n)}\) induced matchings. Another protocol is a somewhat simpler version of the construction of [1], 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, extending a result of Fox and Loh.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Alon, A. Moitra and B. Sudakov, Nearly complete graphs decomposable into large induced matchings and their applications, in: Proc. of the 44thACM STOC (2012), pp. 1079-1089; also: J. Eur. Math. Soc. (JEMS), 15 (2013), 1575–1596
N. Alon and J. Spencer, The Probabilistic Method (4th edition), Wiley Interscience (2016)
Behrend, F.A.: On sets of integers which contain no three terms in arithmetic progression. Proc. Nat. Acad. Sci. USA 32, 331–332 (1946)
Birk, Y., Linial, N., Meshulam, R.: On the uniform-traffic capacity of single-hop interconnections employing shared directional multichannels. IEEE Trans. Inform. Theory 39, 186–191 (1993)
F. R. K. Chung and R. L. Graham, Erdős on Graphs; his Legacy of Unsolved Problems, A K Peters, Ltd. (1998).
A. Chandra, M. Furst, and R. Lipton, Multi-party protocols, in: Proceedings of the 15th ACM Symposium on the Theory of Computing (ACM, 1983), 94–99
Chung, F.R.K., Lu, L.: An upper bound for the Turán number \(t_3(n,4)\). J. Combin. Theory Ser. A 87, 381–389 (1999)
Erdős, P.: On the combinatorial problems which I would most like to see solved. Combinatorica. 1, 25–42 (1981)
P. Erdős, Some problems on finite and infinite graphs, in: Logic and Combinatorics, (Arcata, Calif., 1985), Contemp. Math., vol. 65, Amer. Math. Soc. (Providence, RI, 1987), pp. 223–228
P. Erdős, Problems and results in combinatorial analysis and graph theory, in: Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), Discrete Math., 72 (1988), 81–92
P. Erdős, Some of my favourite problems in various branches of combinatorics, in: Combinatorics 92 (Catania, 1992), Matematiche (Catania)47 (1992), 231–240
Erdős, P., Simonovits, M.: Supersaturated graphs and hypergraphs. Combinatorica 3, 181–192 (1983)
J. Fox, A new proof of the graph removal lemma, Ann. of Math. (2), 174 (2011), 561–579
Fox, J., Loh, P.: On a problem of Erdős and Rothschild on edges in triangles. Combinatorica 32, 619–628 (2012)
W. T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. of Math. (2), 166 (2007), 897–946
N. G. Hadziivanov and S. V. Nikiforov, Solution of a problem of P. Erdős about the maximum number of triangles with a common edge in a graph, C. R. Acad. Bulgare Sci., 32 (1979), 1315–1318 (in Russian)
Katona, G., Nemetz, T., Simonovits, M.: On a problem of Turán in the theory of graphs. Mat. Lapok 15, 228–238 (1964)
E. Kushilevitz and N. Nisan, Communication Complexity, Cambridge University Press (1997).
N. Linial, T. Pitassi, and A. Shraibman, On the communication complexity of high-dimensional permutations, preprint, arXiv:1706.02207 (2017)
Nagle, B., Rödl, V., Schacht, M.: The counting lemma for regular \(k\)-uniform hypergraphs. Random Structures Algorithms 28, 113–179 (2006)
Rödl, V., Skokan, J.: Regularity lemma for \(k\)-uniform hypergraphs. Random Structures Algorithms 25, 1–42 (2004)
I. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, in: Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland (Amsterdam–New York, 1978), pp. 939–945
Turán, P.: Research problems. MTA Mat. Kut. Int. Közl. 6, 417–423 (1961)
E. Szemerédi, Regular partitions of graphs, in: Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) (J.C. Bermond, J.C. Fournier, M. Las Vergnas and D. Sotteau, eds.), CNRS (Paris, 1978), pp. 399–401
Acknowledgement
We thank an anonymous referee for several very helpful comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to Endre Szemerédi, for his 80th birthday
Research supported in part by NSF grant DMS-1855464, ISF grant 281/17, BSF grant 2018267 and the Simons Foundation.
Rights and permissions
About this article
Cite this article
Alon, N., Shraibman, A. Number on the Forehead Protocols yielding dense Ruzsa–Szemerédi graphs and hypergraphs. Acta Math. Hungar. 161, 488–506 (2020). https://doi.org/10.1007/s10474-020-01069-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10474-020-01069-8