Monochromatic configurations on a circle

EUROCOMB’23

Gábor Damásdi Nora Frankl Janos Pach Dömötör Pálvölgyi

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

PDF
Abstract
For $k\geq 3$, call a $k$-tuple $(d_1,d_2,\dots,d_k)$ with $d_1\geq d_2\geq \dots \geq d_k>0$ and $\sum_{i=1}^k d_i=1$ a Ramsey $k$-tuple if the following is true: in every two-colouring of the circle of unit perimeter, there is a monochromatic $k$-tuple of points in which the distances of cyclically consecutive points, measured along the arcs, are $d_1,d_2,\dots,d_k$ in some order. By a conjecture of Stromquist, if $d_i=\frac{2^{k-i}}{2^k-1}$, then $(d_1,\dots,d_k)$ is Ramsey. Our main result is a proof of the converse of this conjecture. That is, we show that if $(d_1,\dots,d_k)$ is Ramsey, then $d_i=\frac{2^{k-i}}{2^k-1}$. We do this by finding connections of the problem to certain questions from number theory about partitioning $\mathbb{N}$ into so-called Beatty sequences. We also disprove a majority version of Stromquist‘s conjecture, study a robust version, and discuss a discrete version.

Pages:
320–327
References

E. Altman, B. Gaujal, and A. Hordijk: Balanced sequences and optimal routing, J. ACM, 47(4), 752-775, 2000, ACM New York, NY, USA.
https://doi.org/10.1145/347476.347482

J. Barát and P. P. Varjú: Partitioning the positive integers to seven Beatty sequences, Indag. Math. (N.S.), 14(2), 149-161, 2003, Elsevier.
https://doi.org/10.1016/S0019-3577(03)90000-0

S. Beatty, N. Altshiller-Court, O. Dunkel, A. Pelletier, F. Irwin, J. L. Riley, P. Fitch, and D. M. Yost: Problems for Solutions: 3173-3180, Amer. Math. Monthly, 33(3), 159-159, 1926, Mathematical Association of America.
https://doi.org/10.2307/2300153

A. Bialostocki and M. J. Nielsen: Minimum sets forcing monochromatic triangles, Ars Combin., 81, 297-304, 2006, Waterloo [Ont.] Dept. of Combinatorics and Optimization, University of Waterloo.

I. G. Connell: Some properties of Beatty sequences I, Canad. Math. Bull., 2(3), 190-197, 1959, Cambridge University Press.
https://doi.org/10.4153/CMB-1959-025-0

P. Erdős and R. L. Graham: Old and new problems and results in combinatorial number theory, volume 28, 1980, L'Enseignement Mathematiques Un. Geneve.

A. S. Fraenkel: Complementing and exactly covering sequences, J. Combin. Theory Ser. A, 14(1), 8-20, 1973, Elsevier.
https://doi.org/10.1016/0097-3165(73)90059-9

A. S. Fraenkel: The bracket function and complementary sets of integers, Canad. J. Math., 21, 6-27, 1969, Cambridge University Press.
https://doi.org/10.4153/CJM-1969-002-7

R. L. Graham: Covering the positive integers by disjoint sets of the form {[nα+β]: n= 1, 2,…}, J. Combin. Theory Ser. A, 15(3), 354-358, 1973, Academic Press.
https://doi.org/10.1016/0097-3165(73)90084-8

Ryozo Morikawa: On eventually covering families generated by the bracket function, Bull. Fac. Liberal Arts, Nagasaki Univ., Natural Science, 23(1), 17-22, 1982.

T. Skolem: Über einige Eigenschaften der Zahlenmengen [αn+β] bei irrationalem α mit einleitenden Bemerkungen über einige kombinatorische probleme, Norske Vid. Selsk. Forh, 30, 42-49, 1957.

E. Steinitz: Bedingt konvergente Reihen und konvexe Systeme (Teil I.), Journal für die Reine und Angewandte Mathematik, 143, 128-175, 1913.
https://doi.org/10.1515/crll.1913.143.128

R. Tauraso: Problems and Solutions, Problem 12251, Amer. Math. Monthly, 128(5), 467, 2021, Taylor & Francis.

R. Tijdeman: On complementary triples of Sturmian bisequences, Indagationes Mathematicae, 7(3), 419-424, 1996, Elsevier.
https://doi.org/10.1016/0019-3577(96)83728-1

R. Tijdeman: Exact covers of balanced sequences and Fraenkel's conjecture, Algebraic number theory and Diophantine analysis (Graz, 1998), 467-483, 2000, de Gruyter Berlin.

R. Tijdeman: Fraenkel's conjecture for six sequences, Discrete Math., 222(1-3), 223-234, 2000, Elsevier.
https://doi.org/10.1016/S0012-365X(99)00411-2

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 Gábor Damásdi, Nora Frankl, Janos Pach, Dömötör Pálvölgyi

PDF