{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T15:36:30Z","timestamp":1772638590217,"version":"3.50.1"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T00:00:00Z","timestamp":1772582400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T00:00:00Z","timestamp":1772582400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2026,4]]},"abstract":"Abstract<\/jats:title>\n \n We say that a family of permutations\n t<\/jats:italic>\n -shatters a set if it induces at least\n t<\/jats:italic>\n distinct permutations on that set. What is the minimum number\n \n \n $$f_k(n,t)$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n t<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n of permutations of\n \n \n $$\\{1, \\dots , n\\}$$<\/jats:tex-math>\n \n \n {<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \u22ef<\/mml:mo>\n ,<\/mml:mo>\n n<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n that\n t<\/jats:italic>\n -shatter all subsets of size\n k<\/jats:italic>\n ? For\n \n \n $$t \\le 2$$<\/jats:tex-math>\n \n \n t<\/mml:mi>\n \u2264<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n \n \n $$f_k(n,t) = \\Theta (1)$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n t<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \u0398<\/mml:mi>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Spencer showed that\n \n \n $$f_k(n,t) = \\Theta (\\log \\log n)$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n t<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \u0398<\/mml:mi>\n \n (<\/mml:mo>\n log<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for\n \n \n $$3 \\le t \\le k$$<\/jats:tex-math>\n \n \n 3<\/mml:mn>\n \u2264<\/mml:mo>\n t<\/mml:mi>\n \u2264<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and\n \n \n $$f_k(n,k!) = \\Theta (\\log n)$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n !<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \u0398<\/mml:mi>\n \n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . In 1996, F\u00fcredi asked whether partial shattering with permutations must always fall into one of these three regimes. Johnson and Wickes recently settled the case\n \n \n $$k = 3$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n =<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n affirmatively and proved that\n \n \n $$f_k(n,t) = \\Theta (\\log n)$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n t<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \u0398<\/mml:mi>\n \n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for\n \n \n $$t > 2 (k-1)!$$<\/jats:tex-math>\n \n \n t<\/mml:mi>\n ><\/mml:mo>\n 2<\/mml:mn>\n (<\/mml:mo>\n k<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n !<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . We give a surprising negative answer to the question of F\u00fcredi by showing that a fourth regime exists for\n \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>\n . We establish that\n \n \n $$f_k(n,t) = \\Theta (\\sqrt{\\log n})$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n t<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \u0398<\/mml:mi>\n \n (<\/mml:mo>\n \n \n log<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for certain values of\n t<\/jats:italic>\n and prove that this is the only other regime when\n \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>\n . We also show that\n \n \n $$f_k(n,t) = \\Theta (\\log n)$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n t<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \u0398<\/mml:mi>\n \n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for\n \n \n $$t > 2^{k-1}$$<\/jats:tex-math>\n \n \n t<\/mml:mi>\n ><\/mml:mo>\n \n 2<\/mml:mn>\n \n k<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . This greatly narrows the range of\n t<\/jats:italic>\n for which the asymptotic behaviour of\n \n \n $$f_k(n,t)$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n t<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is unknown.\n <\/jats:p>","DOI":"10.1007\/s00493-026-00201-6","type":"journal-article","created":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T09:46:02Z","timestamp":1772617562000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Small Families of Partially Shattering Permutations"],"prefix":"10.1007","volume":"46","author":[{"given":"Ant\u00f3nio","family":"Gir\u00e3o","sequence":"first","affiliation":[]},{"given":"Lukas","family":"Michel","sequence":"additional","affiliation":[]},{"given":"Youri","family":"Tamitegama","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,3,4]]},"reference":[{"key":"201_CR1","unstructured":"Baber, R., Behague, N., Calbet, A., Ellis, D., Erde, J., Gray, R., Ivan, M., Janzer, B., Johnson, R., Mili\u0107evi\u0107, L., et\u00a0al.: A collection of open problems in celebration of Imre Leader\u2019s 60th birthday. arXiv preprint arXiv:2310.18163, (2023)"},{"issue":"1","key":"201_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1112\/plms\/pdu049","volume":"110","author":"D Conlon","year":"2015","unstructured":"Conlon, D., Fox, J., Lee, C., Sudakov, B.: The Erd\u0151s-Gy\u00e1rf\u00e1s problem on generalized Ramsey numbers. Proc. Lond. Math. Soc. 110(1), 1\u201318 (2015)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"3","key":"201_CR3","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/s004930070016","volume":"20","author":"D Eichhorn","year":"2000","unstructured":"Eichhorn, D., Mubayi, D.: Note-edge-coloring cliques with many colors on subcliques. Combinatorica 20(3), 441\u2013444 (2000)","journal-title":"Combinatorica"},{"key":"201_CR4","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/BF01195000","volume":"17","author":"P Erd\u0151s","year":"1997","unstructured":"Erd\u0151s, P., Gy\u00e1rf\u00e1s, A.: A variant of the classical Ramsey problem. Combinatorica 17, 459\u2013467 (1997)","journal-title":"Combinatorica"},{"issue":"2","key":"201_CR5","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1002\/(SICI)1098-2418(199603)8:2<97::AID-RSA1>3.0.CO;2-J","volume":"8","author":"Z F\u00fcredi","year":"1996","unstructured":"F\u00fcredi, Z.: Scrambling permutations and entropy of hypergraphs. Random Structures & Algorithms 8(2), 97\u2013104 (1996)","journal-title":"Random Structures & Algorithms"},{"issue":"1\u20133","key":"201_CR6","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0012-365X(95)00087-D","volume":"159","author":"Y Ishigami","year":"1996","unstructured":"Ishigami, Y.: An extremal problem of d permutations containing every permutation of every t elements. Discret. Math. 159(1\u20133), 279\u2013283 (1996)","journal-title":"Discret. Math."},{"key":"201_CR7","doi-asserted-by":"crossref","unstructured":"Johnson, J.R., Wickes, B.: Shattering k-sets with permutations. Order, pages 1\u201318, (2023)","DOI":"10.1007\/s11083-023-09637-7"},{"issue":"3","key":"201_CR8","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0012-365X(73)90098-8","volume":"6","author":"DJ Kleitman","year":"1973","unstructured":"Kleitman, D.J., Spencer, J.: Families of k-independent sets. Discret. Math. 6(3), 255\u2013262 (1973)","journal-title":"Discret. Math."},{"issue":"4","key":"201_CR9","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1002\/rsa.10082","volume":"22","author":"J Radhakrishnan","year":"2003","unstructured":"Radhakrishnan, J.: A note on scrambling permutations. Random Structures & Algorithms 22(4), 435\u2013439 (2003)","journal-title":"Random Structures & Algorithms"},{"issue":"1","key":"201_CR10","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N Sauer","year":"1972","unstructured":"Sauer, N.: On the density of families of sets. J. Combinatorial Theory, Series A 13(1), 145\u2013147 (1972)","journal-title":"J. Combinatorial Theory, Series A"},{"issue":"1","key":"201_CR11","doi-asserted-by":"publisher","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S Shelah","year":"1972","unstructured":"Shelah, S.: A combinatorial problem; stability and order for models and theories in infinitary languages. Pac. J. Math. 41(1), 247\u2013261 (1972)","journal-title":"Pac. J. Math."},{"key":"201_CR12","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF01896428","volume":"22","author":"JH Spencer","year":"1972","unstructured":"Spencer, J.H.: Minimal scrambling sets of simple orders. Acta Mathematica Academiae Scientiarum Hungaricae 22, 349\u2013353 (1972)","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"key":"201_CR13","doi-asserted-by":"crossref","unstructured":"Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity: festschrift for Alexey Chervonenkis, pages 11\u201330. Springer, (2015)","DOI":"10.1007\/978-3-319-21852-6_3"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-026-00201-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-026-00201-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-026-00201-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T09:46:04Z","timestamp":1772617564000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-026-00201-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,4]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["201"],"URL":"https:\/\/doi.org\/10.1007\/s00493-026-00201-6","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,4]]},"assertion":[{"value":"8 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 October 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 March 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"10"}}