BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We give the automata which describe time evolution rules of the box-ball system (BBS) with a carrier. It can be shown by use of tropical geometry, such systems are ultradiscrete analogues of KdV equation. We discuss their relation with the lamplighter group generated by an automaton. We present spectral analysis of the stochastic matrices induced by these automata, and verify their spectral coincidence.
Let g, h be a random pair of generators of G=Sym(n) or G=Alt(n). We show that, with probability tending to 1 as n→∞, (a) the diameter of G with respect to S={g,h,g−1,h−1} is at most O(n2(logn)c), and (b) the mixing time of G with respect to S is at most O(n3(logn)c). (Both c and the implied constants are absolute.) These bounds are far lower than the strongest worst-case bounds known (in Helfgott--Seress, 2013); they roughly match the worst known examples. We also give an improved, though still non-constant, bound on the spectral gap. Our results rest on a combination of the algorithm in (Babai--Beals--Seress, 2004) and the fact that the action of a pair of random permutations is almost certain to act as an expander on ℓ-tuples, where ℓ is an arbitrary constant (Friedman et al., 1998).
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.