The Rado Multiplicity Problem in Vector Spaces over Finite Fields

EUROCOMB’23

Juanjo Rué Christoph Spiegel

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-108

PDF
Abstract
We study an analogue of the Ramsey multiplicity problem for additive structures, establishing the minimum number of monochromatic $3$-APs in $3$-colorings of $\mathbb{F}_3^n$ and obtaining the first non-trivial lower bound for the minimum number of monochromatic $4$-APs in $2$-colorings of $\mathbb{F}_5^n$. The former parallels results by Cumings et al. \cite{CummingsEtAl_2013} in extremal graph theory and the latter improves upon results of Saad and Wolf \cite{SaadWolf_2017}. Lower bounds are notably obtained by extending the flag algebra calculus of Razborov \cite{razborov2007flag}.

Pages:
784–789
References

P. J. Cameron, J. Cilleruelo, and O. Serra. On monochromatic solutions of equations in groups. Revista Matemática Iberoamericana, 23(1):385-395, 2007.
https://doi.org/10.4171/RMI/499

David Conlon. On the Ramsey multiplicity of complete graphs. Combinatorica, 32:171-186, 2012.
https://doi.org/10.1007/s00493-012-2465-x

J. Cummings, D. Král', F. Pfender, K. Sperfeld, A. Treglown, and M. Young. Monochromatic triangles in three-coloured graphs. Journal of Combinatorial Theory, Series B, 103(4):489-503, 2013.
https://doi.org/10.1016/j.jctb.2013.05.002

B. A. Datskovsky. On the number of monochromatic Schur triples. Advances in Applied Mathematics, 31(1):193-198, 2003.
https://doi.org/10.1016/S0196-8858(03)00010-1

P. Erdős. On the number of complete subgraphs contained in certain graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl, 7(3):459-464, 1962.

J. Fox, H. T. Pham, and Y. Zhao. Common and Sidorenko linear equations. The Quarterly Journal of Mathematics, 72(4):1223-1234, 2021.
https://doi.org/10.1093/qmath/haaa068

A. W. Goodman. On sets of acquaintances and strangers at any party. The American Mathematical Monthly, 66(9):778-783, 1959.
https://doi.org/10.1080/00029890.1959.11989408

R. Graham, V. Rödl, and A. Ruciński. On Schur properties of random subsets of integers. Journal of Number Theory, 61(2):388-408, 1996.
https://doi.org/10.1006/jnth.1996.0155

N. Kamčev, A. Liebenau, and N. Morrison. Towards a characterisation of Sidorenko systems. arXiv preprint arXiv:2107.14413, 2021.

A. Lamaison, P. P. Pach, et al. Common systems of two equations over the binary field. In Discrete Mathematics Days 2022, pages 169-173. Editorial de la Universidad de Cantabria, 2022.

A. A. Razborov. Flag algebras. The Journal of Symbolic Logic, 72(4):1239-1282, 2007.
https://doi.org/10.2178/jsl/1203350785

A. Robertson and D. Zeilberger. A 2-coloring of [1, n] can have (1/22) n² + o(n) monochromatic Schur triples, but not less! The Electronic Journal of Combinatorics, 5(1):R19, 1998.
https://doi.org/10.37236/1357

A. Saad and J. Wolf. Ramsey multiplicity of linear patterns in certain finite abelian groups. The Quarterly Journal of Mathematics, 68(1):125-140, 2017.

T. Schoen. The number of monochromatic Schur triples. European Journal of Combinatorics, 20(8):855-866, 1999.
https://doi.org/10.1006/eujc.1999.0297

A. Thomason. A disproof of a conjecture of Erdős in Ramsey theory. Journal of the London Mathematical Society, 2(2):246-255, 1989.
https://doi.org/10.1112/jlms/s2-39.2.246

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Juanjo Rué, Christoph Spiegel

PDF