{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T14:40:12Z","timestamp":1741358412395,"version":"3.38.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T00:00:00Z","timestamp":1735776000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T00:00:00Z","timestamp":1735776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003483","name":"Hebrew University of Jerusalem","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003483","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,2]]},"abstract":"Abstract<\/jats:title>\n A permutation \n \n $$\\pi \\in \\mathbb {S}_n$$<\/jats:tex-math>\n \n \n \u03c0<\/mml:mi>\n \u2208<\/mml:mo>\n \n S<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is k<\/jats:italic>-balanced<\/jats:italic> if every permutation of order k<\/jats:italic> occurs in \n \n $$\\pi $$<\/jats:tex-math>\n \n \u03c0<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> equally often, through order-isomorphism. In this paper, we explicitly construct k<\/jats:italic>-balanced permutations for \n \n $$k \\le 3$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \u2264<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, and every n<\/jats:italic> that satisfies the necessary divisibility conditions. In contrast, we prove that for \n \n $$k \\ge 4$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \u2265<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, no such permutations exist. In fact, we show that in the case \n \n $$k \\ge 4$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \u2265<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, every n<\/jats:italic>-element permutation is at least \n \n $$\\Omega _n(n^{k-1})$$<\/jats:tex-math>\n \n \n \n \u03a9<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n \n n<\/mml:mi>\n \n k<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> far from being k<\/jats:italic>-balanced. This lower bound is matched for \n \n $$k=4$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n =<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, by a construction based on the Erd\u0151s\u2013Szekeres permutation.<\/jats:p>","DOI":"10.1007\/s00493-024-00127-x","type":"journal-article","created":{"date-parts":[[2025,1,3]],"date-time":"2025-01-03T02:47:20Z","timestamp":1735872440000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["How Balanced Can Permutations Be?"],"prefix":"10.1007","volume":"45","author":[{"given":"Gal","family":"Beniamini","sequence":"first","affiliation":[]},{"given":"Nir","family":"Lavee","sequence":"additional","affiliation":[]},{"given":"Nati","family":"Linial","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,2]]},"reference":[{"issue":"1","key":"127_CR1","doi-asserted-by":"publisher","first-page":"R5","DOI":"10.37236\/1622","volume":"9","author":"MH Albert","year":"2002","unstructured":"Albert, M.H., Atkinson, M.D., Handley, C.C., Holton, D.A., Stromquist, W.: On packing densities of permutations. Electron. J. Comb. 9(1), R5 (2002)","journal-title":"Electron. J. Comb."},{"key":"127_CR2","unstructured":"B\u00f3na, M.: The copies of any permutation pattern are asymptotically normal (2007). arXiv preprint arXiv:0712.2792"},{"key":"127_CR3","unstructured":"Crudele, G., Dukes, P., Noel, J.A.: Six permutation patterns force quasirandomness (2023). arXiv preprint arXiv:2303.04776"},{"key":"127_CR4","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF02125347","volume":"9","author":"FRK Chung","year":"1989","unstructured":"Chung, F.R.K., Graham, R.L., Wilson, R.M.: Quasi-random graphs. Combinatorica 9, 345\u2013362 (1989)","journal-title":"Combinatorica"},{"issue":"1","key":"127_CR5","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.jcta.2004.01.006","volume":"106","author":"JN Cooper","year":"2004","unstructured":"Cooper, J.N.: Quasirandom permutations. J. Comb. Theory Ser. A 106(1), 123\u2013143 (2004)","journal-title":"J. Comb. Theory Ser. A"},{"key":"127_CR6","unstructured":"Cooper, J., Petrarca, A.: Symmetric and asymptotically symmetric permutations (2008). arXiv preprint arXiv:0801.4181"},{"key":"127_CR7","doi-asserted-by":"crossref","unstructured":"Dudek, B., Gawrychowski, P.: Counting 4-patterns in permutations is equivalent to counting 4-cycles in graphs (2020). arXiv preprint arXiv:2010.00348","DOI":"10.1145\/3313276.3316390"},{"key":"127_CR8","first-page":"463","volume":"2","author":"P Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463\u2013470 (1935)","journal-title":"Compos. Math."},{"issue":"6","key":"127_CR9","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1007\/s00493-020-4212-z","volume":"40","author":"C Even-Zohar","year":"2020","unstructured":"Even-Zohar, C.: Patterns in random permutations. Combinatorica 40(6), 775\u2013804 (2020)","journal-title":"Combinatorica"},{"key":"127_CR10","doi-asserted-by":"crossref","unstructured":"Even-Zohar, C., Leng, C.: Counting small permutation patterns. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2288\u20132302. SIAM (2021)","DOI":"10.1137\/1.9781611976465.136"},{"key":"127_CR11","unstructured":"Glock, S., K\u00fchn, D., Lo, A., Osthus, D.: The existence of designs via iterative absorption: hypergraph F-designs for arbitrary F (2016). arXiv preprint arXiv:1611.06827"},{"issue":"1","key":"127_CR12","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.jctb.2012.09.003","volume":"103","author":"C Hoppen","year":"2013","unstructured":"Hoppen, C., Kohayakawa, Y., Moreira, C.G., R\u00e1th, B., Sampaio, R.M.: Limits of permutation sequences. J. Comb. Theory Ser. B 103(1), 93\u2013113 (2013)","journal-title":"J. Comb. Theory Ser. B"},{"key":"127_CR13","unstructured":"Hoppen, C., Kohayakawa, Y., Tamm de\u00a0Ara\u00fajo Moreira, C.G., Sampaio, R.M.: Limits of permutation sequences through permutation regularity (2011). arXiv preprint arXiv:1106.1663"},{"key":"127_CR14","unstructured":"Hofer, L.: A central limit theorem for vincular permutation patterns. Discret. Math. Theor. Comput. Sci. 19 (2018)"},{"issue":"1\u20132","key":"127_CR15","first-page":"117","volume":"6","author":"S Janson","year":"2015","unstructured":"Janson, S., Nakamura, B., Zeilberger, D.: On the asymptotic statistics of the number of occurrences of multiple permutation patterns. J. Comb. 6(1\u20132), 117\u2013143 (2015)","journal-title":"J. Comb."},{"issue":"2","key":"127_CR16","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1002\/rsa.3240030203","volume":"3","author":"S Janson","year":"1992","unstructured":"Janson, S., Spencer, J.: Probabilistic construction of proportional graphs. Random Struct. Algorithms 3(2), 127\u2013137 (1992)","journal-title":"Random Struct. Algorithms"},{"key":"127_CR17","unstructured":"Keevash, P.: The existence of designs (2014). arXiv preprint arXiv:1401.3665"},{"issue":"2","key":"127_CR18","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1007\/s00039-013-0216-9","volume":"23","author":"D Kr\u00e1l\u2019","year":"2013","unstructured":"Kr\u00e1l\u2019, D., Pikhurko, O.: Quasirandom permutations are characterized by 4-point densities. Geom. Funct. Anal. 23(2), 570\u2013579 (2013)","journal-title":"Geom. Funct. Anal."},{"key":"127_CR19","volume-title":"Large Networks and Graph Limits","author":"L Lov\u00e1sz","year":"2012","unstructured":"Lov\u00e1sz, L.: Large Networks and Graph Limits, vol. 60. American Mathematical Society, Providence (2012)"},{"key":"127_CR20","unstructured":"Minsky, M., Papert, S.: Perceptron: an introduction to computational geometry (1969)"},{"key":"127_CR21","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/j.ejc.2018.05.007","volume":"73","author":"H Naves","year":"2018","unstructured":"Naves, H., Pikhurko, O., Scott, A.: How unproportional must a graph be? Eur. J. Comb. 73, 138\u2013152 (2018)","journal-title":"Eur. J. Comb."},{"key":"127_CR22","unstructured":"OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2018. Published electronically at http:\/\/oeis.org"},{"key":"127_CR23","doi-asserted-by":"crossref","unstructured":"Paturi, R.: On the degree of polynomials that approximate symmetric boolean functions (preliminary version). In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pp. 468\u2013474 (1992)","DOI":"10.1145\/129712.129758"},{"issue":"3","key":"127_CR24","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0095-8956(75)90084-2","volume":"19","author":"N Pippenger","year":"1975","unstructured":"Pippenger, N., Golumbic, M.C.: The inducibility of graphs. J. Comb. Theory Ser. B 19(3), 189\u2013203 (1975)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"127_CR25","doi-asserted-by":"publisher","first-page":"1239","DOI":"10.2178\/jsl\/1203350785","volume":"72","author":"AA Razborov","year":"2007","unstructured":"Razborov, A.A.: Flag algebras. J. Symb. Logic 72(4), 1239\u20131282 (2007)","journal-title":"J. Symb. Logic"},{"key":"127_CR26","unstructured":"Sliacan, J., Stromquist, W.: Improving bounds on packing densities of 4-point permutations. Discret. Math. Theor. Comput. Sci. 19(Permutation Patterns) (2018)"},{"key":"127_CR27","doi-asserted-by":"crossref","unstructured":"Thomason, A.: Pseudo-random graphs. In: North-Holland Mathematics Studies, vol. 144, pp. 307\u2013331. Elsevier (1987)","DOI":"10.1016\/S0304-0208(08)73063-9"},{"issue":"2\u20133","key":"127_CR28","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1016\/S0012-365X(02)00515-0","volume":"257","author":"HS Wilf","year":"2002","unstructured":"Wilf, H.S.: The patterns of permutations. Discret. Math. 257(2\u20133), 575\u2013583 (2002)","journal-title":"Discret. Math."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00127-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-024-00127-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00127-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T13:39:40Z","timestamp":1741354780000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-024-00127-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,2]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["127"],"URL":"https:\/\/doi.org\/10.1007\/s00493-024-00127-x","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2025,1,2]]},"assertion":[{"value":"5 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 October 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 October 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 January 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"9"}}