{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T22:29:19Z","timestamp":1783031359736,"version":"3.54.6"},"reference-count":16,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T00:00:00Z","timestamp":1698278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>We study an abstract variant of squares (and shuffle squares) defined by a constraint graph\u00a0G, specifying which pairs of words form a square. So, a shuffle G-square is a word that can be split into two disjoint subwords U and W (of the same length), which are joined by an edge. This setting generalizes a recently introduced model of shuffle squares based on word symmetry and permutations. By using the probabilistic method, we provide a sufficient condition for a constraint graph G guaranteeing the avoidability of shuffle G-squares. By a more-elementary method (known as Rosenfeld counting), we prove that G-squares are avoidable over an alphabet of size 4\u03b1, \u03b1&gt;1, provided that the degree of every word of length n in G is at most \u03b1n. We also introduce the concept of the cutting distance between words and state several conjectures involving this notion and various kinds of shuffle squares. We suspect that, for every k\u2a7e2, there is a constant ck such that every even word can be turned into a shuffle square by cutting it in at most ck places and rearranging the resulting pieces. We present some computational, as well as theoretical evidence in favor of this conjecture.<\/jats:p>","DOI":"10.3390\/sym15111982","type":"journal-article","created":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T03:33:51Z","timestamp":1698377631000},"page":"1982","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["More Variations on Shuffle Squares"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0258-6143","authenticated-orcid":false,"given":"Jaros\u0142aw","family":"Grytczuk","sequence":"first","affiliation":[{"name":"Faculty of Mathematics and Information Science, Warsaw University of Technology, 00-662 Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5291-2701","authenticated-orcid":false,"given":"Bart\u0142omiej","family":"Pawlik","sequence":"additional","affiliation":[{"name":"Institute of Mathematics, Silesian University of Technology, 44-100 Gliwice, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4971-5360","authenticated-orcid":false,"given":"Mariusz","family":"Pleszczy\u0144ski","sequence":"additional","affiliation":[{"name":"Institute of Mathematics, Silesian University of Technology, 44-100 Gliwice, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2023,10,26]]},"reference":[{"key":"ref_1","first-page":"131","article-title":"Shuffling and Unshuffling","volume":"107","author":"Henshall","year":"2012","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"ref_2","unstructured":"He, X., Huang, E., Nam, I., and Thaper, R. (2021). Shuffle Squares and Reverse Shuffle Squares. arXiv."},{"key":"ref_3","first-page":"1","article-title":"\u00dcber unendliche Zeichenreihen","volume":"7","author":"Thue","year":"1906","journal-title":"Nor. Vid. Selsk. Skr. Mat. Nat. Kl."},{"key":"ref_4","unstructured":"Currie, J.D. (2014). Shuffle squares are avoidable, Unpublished manuscript."},{"key":"ref_5","unstructured":"M\u00fcller, M. (2015). Avoiding and Enforcing Repetitive Structures in Words. [Ph.D. Thesis, University of Kiel]."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1051\/ita\/2016007","article-title":"A short proof that shuffle squares and 7-avoidable","volume":"50","author":"Ochem","year":"2016","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"ref_7","unstructured":"Grytczuk, J., Kozik, J., and Zaleski, B. Avoiding Tight Twins in Sequences by Entropy Compression, Mittag-Leffler Institute."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.tcs.2022.10.028","article-title":"On shuffled-square-free words","volume":"941","author":"Bulteau","year":"2023","journal-title":"Theor. Comput. Sci."},{"key":"ref_9","unstructured":"Grytczuk, J., Pawlik, B., and Pleszczy\u0144ski, M. (2023). Variations on shuffle squares. arXiv."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.jcta.2004.04.002","article-title":"Excluded permutation matrices and the Stanley\u2013Wilf conjecture","volume":"107","author":"Marcus","year":"2004","journal-title":"J. Comb. Theory Ser. A"},{"key":"ref_11","unstructured":"Alon, N., and Spencer, J. (2016). The Probabilistic Method, Wiley. [4th ed.]."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/s00026-021-00534-7","article-title":"Nonrepetitive List Colorings of the Integers","volume":"25","author":"Bosek","year":"2021","journal-title":"Ann. Comb."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"P3.43","DOI":"10.37236\/9667","article-title":"Another Approach to Non-Repetitive Colorings of Graphs of Bounded Degree","volume":"27","author":"Rosenfeld","year":"2020","journal-title":"Electron. J. Comb."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1137\/0606010","article-title":"Bisection of circle colorings","volume":"6","author":"Goldberg","year":"1985","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0001-8708(87)90055-7","article-title":"Splitting necklaces","volume":"63","author":"Alon","year":"1987","journal-title":"Adv. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1090\/S0002-9939-1986-0861764-9","article-title":"The Borsuk-Ulam theorem and bisection of necklaces","volume":"98","author":"Alon","year":"1986","journal-title":"Proc. Am. Math."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/15\/11\/1982\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:12:31Z","timestamp":1760130751000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/15\/11\/1982"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,26]]},"references-count":16,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2023,11]]}},"alternative-id":["sym15111982"],"URL":"https:\/\/doi.org\/10.3390\/sym15111982","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,26]]}}}