Geodesic
On Motzkin's Problem in the Circle Group
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Analytic and Combinatorial Number Theory, Tome 314 (2021), pp. 49-70.

Voir la notice de l'article provenant de la source Math-Net.Ru

Given a subset $D$ of the interval $(0,1)$, if a Borel set $A\subset [0,1)$ contains no pair of elements whose difference modulo $1$ is in $D$, then how large can the Lebesgue measure of $A$ be? This is the analogue in the circle group of a well-known problem of Motzkin, originally posed for sets of integers. We make a first treatment of this circle-group analogue, for finite sets $D$ of missing differences, using techniques from ergodic theory, graph theory and the geometry of numbers. Our results include an exact solution when $D$ has two elements at least one of which is irrational. When every element of $D$ is rational, the problem is equivalent to estimating the independence ratio of a circulant graph. In the case of two rational elements, we give an estimate for this ratio in terms of the odd girth of the graph, which is asymptotically sharp and also recovers the classical solution of Cantor and Gordon to Motzkin's original problem for two missing differences. 
@article{TM_2021_314_a2,
     author = {Pablo Candela and Carlos Catal\'a and Juanjo Ru\'e and Oriol Serra},
     title = {On {Motzkin's} {Problem} in the {Circle} {Group}},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {49--70},
     publisher = {mathdoc},
     volume = {314},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TM_2021_314_a2/}
}
TY  - JOUR
AU  - Pablo Candela
AU  - Carlos Catalá
AU  - Juanjo Rué
AU  - Oriol Serra
TI  - On Motzkin's Problem in the Circle Group
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2021
SP  - 49
EP  - 70
VL  - 314
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TM_2021_314_a2/
LA  - ru
ID  - TM_2021_314_a2
ER  - 
%0 Journal Article
%A Pablo Candela
%A Carlos Catalá
%A Juanjo Rué
%A Oriol Serra
%T On Motzkin's Problem in the Circle Group
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2021
%P 49-70
%V 314
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TM_2021_314_a2/
%G ru
%F TM_2021_314_a2
Pablo Candela; Carlos Catalá; Juanjo Rué; Oriol Serra. On Motzkin's Problem in the Circle Group. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Analytic and Combinatorial Number Theory, Tome 314 (2021), pp. 49-70. http://geodesic.mathdoc.fr/item/TM_2021_314_a2/

[1] Albertson M.O., Collins K.L., “Homomorphisms of 3-chromatic graphs”, Discrete Math., 54 (1985), 127–132 | DOI | MR | Zbl

[2] Avila A., Candela P., “Towers for commuting endomorphisms, and combinatorial applications”, Ann. Inst. Fourier, 66:4 (2016), 1529–1544 | DOI | MR | Zbl

[3] Bermond J.C., Comellas F., Hsu D.F., “Distributed loop computer-networks: A survey”, J. Parallel Distrib. Comput., 24:1 (1995), 2–10 | DOI

[4] Cai J.-Y., Havas G., Mans B., Nerurkar A., Seifert J.-P., Shparlinski I., “On routing in circulant graphs”, Computing and combinatorics, Proc. 5th Annu. Int. Conf. COCOON'99 (Tokyo, 1999), Lect. Notes Comput. Sci., 1627, Springer, Berlin, 1999, 360–369 | DOI | MR

[5] Cantor D.G., Gordon B., “Sequences of integers with missing differences”, J. Comb. Theory. Ser. A, 14 (1973), 281–287 | DOI | MR | Zbl

[6] Cassels J.W.S., An introduction to the geometry of numbers, Class. Math., Springer, Berlin, 1997 | MR | Zbl

[7] Codenotti B., Gerace I., Vigna S., “Hardness results and spectral techniques for combinatorial problems on circulant graphs”, Linear Algebra Appl., 285:1–3 (1998), 123–142 | DOI | MR | Zbl

[8] Conze J.P., “Entropie d'un groupe abélien de transformations”, Z. Wahrscheinlichkeitstheor. verw. Geb., 25 (1972), 11–30 | DOI | MR | Zbl

[9] Costa S.I.R., Strapasson J.E., Alves M.M.S., Carlos T.B., “Circulant graphs and tessellations on flat tori”, Linear Algebra Appl., 432:1 (2010), 369–382 | DOI | MR | Zbl

[10] Dooley A.H., Zhang G., Local entropy theory of a random dynamical system, Mem. AMS, 233, N 1099, Amer. Math. Soc., Providence, RI, 2015 | MR

[11] Fiz Pontiveros G., “Sums of dilates in $\mathbb Z_p$”, Comb. Probab. Comput., 22:2 (2013), 282–293 | DOI | MR | Zbl

[12] Gao G., Zhu X., “Star-extremal graphs and the lexicographic product”, Discrete Math., 152:1–3 (1996), 147–156 | DOI | MR | Zbl

[13] Gómez D., Gutierrez J., Ibeas Á., “Optimal routing in double loop networks”, Theor. Comput. Sci., 381:1–3 (2007), 68–85 | DOI | MR | Zbl

[14] Gupta S., “Sets of integers with missing differences”, J. Comb. Theory. Ser. A, 89:1 (2000), 55–69 | DOI | MR | Zbl

[15] Hahn G., Tardif C., “Graph homomorphisms: Structure and symmetry”, Graph symmetry: Algebraic methods and applications, Proc. NATO Adv. Study Inst. sémin. math. supér. (Montréal, 1996), NATO ASI Ser. C. Math. Phys. Sci., 497, Kluwer, Dordrecht, 1997, 107–166 | MR | Zbl

[16] Haralambis N.M., “Sets of integers with missing differences”, J. Comb. Theory. Ser. A, 23 (1977), 22–33 | DOI | MR | Zbl

[17] Hoshino R., Independence polynomials of circulant graphs, PhD thesis, Dalhousie Univ., Halifax, 2007 | MR

[18] Hwang F.K., “A complementary survey on double-loop networks”, Theor. Comput. Sci., 263:1–2 (2001), 211–229 | DOI | MR | Zbl

[19] Kaib M., Schnorr C.P., “The generalized Gauss reduction algorithm”, J. Algorithms, 21:3 (1996), 565–578 | DOI | MR | Zbl

[20] Katznelson Y., Weiss B., “Commuting measure-preserving transformations”, Isr. J. Math., 12 (1972), 161–173 | DOI | MR | Zbl

[21] Kechris A.S., Classical descriptive set theory, Grad. Texts Math., 156, Springer, New York, 1995 | DOI | MR | Zbl

[22] Kleitman D.J., “On a combinatorial conjecture of Erdős”, J. Comb. Theory, 1 (1966), 209–214 | DOI | MR | Zbl

[23] Lih K.-W., Liu D.D.-F., Zhu X., “Star-extremal circulant graphs”, SIAM J. Discrete Math., 12:4 (1999), 491–499 | DOI | MR | Zbl

[24] Lindenstrauss E., “Pointwise theorems for amenable groups”, Invent. math., 146:2 (2001), 259–295 | DOI | MR | Zbl

[25] Lindenstrauss E., Weiss B., “Mean topological dimension”, Isr. J. Math., 115 (2000), 1–24 | DOI | MR | Zbl

[26] Liu D.D.-F., “From rainbow to the lonely runner: A survey on coloring parameters of distance graphs”, Taiwanese J. Math., 12:4 (2008), 851–871 | DOI | MR | Zbl

[27] Liu D.D.-F., Robinson G., “Sequences of integers with three missing separations”, Eur. J. Comb., 85 (2020), 103056 | DOI | MR | Zbl

[28] Marklof J., Strömbergsson A., “Diameters of random circulant graphs”, Combinatorica, 33:4 (2013), 429–466 | DOI | MR | Zbl

[29] Ornstein D.S., Weiss B., “Entropy and isomorphism theorems for actions of amenable groups”, J. anal. math., 48 (1987), 1–141 | DOI | MR | Zbl

[30] Pandey R.K., “Maximal upper asymptotic density of sets of integers with missing differences from a given set”, Math. Bohem., 140:1 (2015), 53–69 | DOI | MR | Zbl

[31] Pandey R.K., Tripathi A., “On the density of integral sets with missing differences”, Combinatorial number theory, Proc. “Integers Conference 2007” (Carrollton, GA, 2007), W. de Gruyter, Berlin, 2009, 157–169 | MR | Zbl

[32] Srivastava A., Pandey R.K., Prakash O., “Motzkin's maximal density and related chromatic numbers”, Unif. Distrib. Theory, 13:1 (2018), 27–45 | DOI | MR | Zbl

[33] Wong C.K., Coppersmith D., “A combinatorial problem related to multimodule memory organizations”, J. Assoc. Comput. Mach., 21:3 (1974), 392–402 | DOI | MR | Zbl