Quasirandom Permutations

Details Quasirandom Permutations Quasirandom Permutations

2002-10-31

arxiv.org/abs/math/0211001v1

Mathematics

Combinatorics

30 pages, 2 figures, submitted to JCTA

Scientific paper

Chung and Graham define quasirandom subsets of $\mathbb{Z}_n$ to be those with any one of a large collection of equivalent random-like properties. We weaken their definition and call a subset of $\mathbb{Z}_n$ $\epsilon$-balanced if its discrepancy on each interval is bounded by $\epsilon n$. A quasirandom permutation, then, is one which maps each interval to a highly balanced set. In the spirit of previous studies of quasirandomness, we exhibit several random-like properties which are equivalent to this one, including the property of containing (approximately) the expected number of subsequences of each order-type. We provide a few applications of these results, present a construction for a family of strongly quasirandom permutations, and prove that this construction is essentially optimal, using a result of W. Schmidt on the discrepancy of sequences of real numbers.

Affiliated with

Also associated with

No associations

Rating

Quasirandom Permutations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quasirandom Permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quasirandom Permutations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-432318