{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,28]],"date-time":"2024-06-28T18:21:29Z","timestamp":1719598889010},"reference-count":10,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2020,10,26]],"date-time":"2020-10-26T00:00:00Z","timestamp":1603670400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,5]]},"abstract":"Abstract<\/jats:title>A k<\/jats:italic>-permutation family on n<\/jats:italic> vertices is a set-system consisting of the intervals of k<\/jats:italic> permutations of the integers 1 to n<\/jats:italic>. The discrepancy of a set-system is the minimum over all red\u2013blue vertex colourings of the maximum difference between the number of red and blue vertices in any set in the system. In 2011, Newman and Nikolov disproved a conjecture of Beck that the discrepancy of any 3-permutation family is at most a constant independent of n<\/jats:italic>. Here we give a simpler proof that Newman and Nikolov\u2019s sequence of 3-permutation families has discrepancy $\\Omega (\\log \\,n)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We also exhibit a sequence of 6-permutation families with root-mean-squared discrepancy $\\Omega (\\sqrt {\\log \\,n} )$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>; that is, in any red\u2013blue vertex colouring, the square root of the expected squared difference between the number of red and blue vertices in an interval of the system is $\\Omega (\\sqrt {\\log \\,n} )$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548320000474","type":"journal-article","created":{"date-parts":[[2020,10,26]],"date-time":"2020-10-26T09:12:38Z","timestamp":1603703558000},"page":"398-411","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["A simplified disproof of Beck\u2019s three permutations conjecture and an application to root-mean-squared discrepancy"],"prefix":"10.1017","volume":"30","author":[{"given":"Cole","family":"Franks","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,10,26]]},"reference":[{"key":"S0963548320000474_ref6","first-page":"253","volume-title":"IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)","author":"Newman","year":"2012"},{"key":"S0963548320000474_ref2","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1109\/FOCS.2008.51","volume-title":"IEEE 49th Annual Symposium on Foundations of Computer Science (FOCS \u201908)","author":"Guruswami","year":"2008"},{"key":"S0963548320000474_ref10","unstructured":"[10] Spencer, J. H. , Srinivasan, A. and Tetali, P. (2018) The discrepancy of permutation families."},{"key":"S0963548320000474_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488652"},{"key":"S0963548320000474_ref1","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1965-017-1"},{"key":"S0963548320000474_ref7","unstructured":"[7] Newman, A. and Nikolov, A. (2011) A counterexample to Beck\u2019s conjecture on the discrepancy of three permutations. arXiv:1104.2922"},{"key":"S0963548320000474_ref3","unstructured":"[3] Larsen, K. G. (2019) Constructive discrepancy minimization with hereditary L2 guarantees. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"S0963548320000474_ref5","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1090\/S0002-9939-2012-11334-6","article-title":"The determinant bound for discrepancy is almost tight","volume":"141","author":"Matou\u0161ek","year":"2013","journal-title":"Proc. Amer. Math. Soc."},{"key":"S0963548320000474_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(86)80041-5"},{"key":"S0963548320000474_ref9","unstructured":"[9] Spencer, J. H. (1987) Ten Lectures on the Probabilistic Method, Vol. 52 of Proc. CBMS-NRM Regional Conference Series in Applied Mathematics. SIAM."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000474","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T12:00:44Z","timestamp":1618315244000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000474\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,26]]},"references-count":10,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["S0963548320000474"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000474","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,26]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}