{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T19:48:01Z","timestamp":1769111281750,"version":"3.49.0"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2018,10,31]],"date-time":"2018-10-31T00:00:00Z","timestamp":1540944000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,5]]},"abstract":"<jats:p>We give the first polynomial upper bound on the mixing time of the edge-flip Markov chain for unbiased dyadic tilings, resolving an open problem originally posed by Janson, Randall and Spencer in 2002 [14]. A <jats:italic>dyadic tiling<\/jats:italic> of size <jats:italic>n<\/jats:italic> is a tiling of the unit square by <jats:italic>n<\/jats:italic> non-overlapping dyadic rectangles, each of area 1\/<jats:italic>n<\/jats:italic>, where a <jats:italic>dyadic rectangle<\/jats:italic> is any rectangle that can be written in the form [<jats:italic>a<\/jats:italic>2<jats:sup>\u2212<jats:italic>s<\/jats:italic><\/jats:sup>, (<jats:italic>a<\/jats:italic> + 1)2<jats:sup>\u2212<jats:italic>s<\/jats:italic><\/jats:sup>] \u00d7 [<jats:italic>b<\/jats:italic>2<jats:sup>\u2212<jats:italic>t<\/jats:italic><\/jats:sup>, (<jats:italic>b<\/jats:italic> + 1)2<jats:sup>\u2212<jats:italic>t<\/jats:italic><\/jats:sup>] for <jats:italic>a<\/jats:italic>, <jats:italic>b<\/jats:italic>, <jats:italic>s<\/jats:italic>, <jats:italic>t<\/jats:italic> \u2208 \u2124<jats:sub>\u2a7e<\/jats:sub> 0. The edge-flip Markov chain selects a random edge of the tiling and replaces it with its perpendicular bisector if doing so yields a valid dyadic tiling. Specifically, we show that the relaxation time of the edge-flip Markov chain for dyadic tilings is at most <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>4.09<\/jats:sup>), which implies that the mixing time is at most <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>5.09<\/jats:sup>). We complement this by showing that the relaxation time is at least \u03a9(<jats:italic>n<\/jats:italic><jats:sup>1.38<\/jats:sup>), improving upon the previously best lower bound of \u03a9(<jats:italic>n<\/jats:italic> log <jats:italic>n<\/jats:italic>) coming from the diameter of the chain.<\/jats:p>","DOI":"10.1017\/s0963548318000470","type":"journal-article","created":{"date-parts":[[2018,10,31]],"date-time":"2018-10-31T10:21:03Z","timestamp":1540981263000},"page":"365-387","source":"Crossref","is-referenced-by-count":2,"title":["Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings"],"prefix":"10.1017","volume":"28","author":[{"given":"S.","family":"CANNON","sequence":"first","affiliation":[]},{"given":"D. A.","family":"LEVIN","sequence":"additional","affiliation":[]},{"given":"A.","family":"STAUFFER","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,10,31]]},"reference":[{"key":"S0963548318000470_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-016-0735-z"},{"key":"S0963548318000470_ref22","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"key":"S0963548318000470_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10051"},{"key":"S0963548318000470_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2224-8_7"},{"key":"S0963548318000470_ref24","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871056"},{"key":"S0963548318000470_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-009-0978-y"},{"key":"S0963548318000470_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-012-0599-2"},{"key":"S0963548318000470_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008792"},{"key":"S0963548318000470_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-012-1460-9"},{"key":"S0963548318000470_ref23","doi-asserted-by":"publisher","DOI":"10.1063\/1.533199"},{"key":"S0963548318000470_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21718"},{"key":"S0963548318000470_ref4","doi-asserted-by":"publisher","DOI":"10.1214\/16-EJP4321"},{"key":"S0963548318000470_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-009-0781-9"},{"key":"S0963548318000470_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2011.08.021"},{"key":"S0963548318000470_ref2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1157118"},{"key":"S0963548318000470_ref17","volume-title":"Markov Chains and Mixing Times","author":"Levin","year":"2009"},{"key":"S0963548318000470_ref3","doi-asserted-by":"publisher","DOI":"10.1214\/14-AAP1033"},{"key":"S0963548318000470_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007978"},{"key":"S0963548318000470_ref9","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005359"},{"key":"S0963548318000470_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.11.010"},{"key":"S0963548318000470_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00508-3"},{"key":"S0963548318000470_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-008-0189-z"},{"key":"S0963548318000470_ref19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360355"},{"key":"S0963548318000470_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-48115-7_2"},{"key":"S0963548318000470_ref21","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/043\/09"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000470","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,11]],"date-time":"2019-04-11T23:38:36Z","timestamp":1555025916000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000470\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,31]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["S0963548318000470"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000470","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,31]]}}}