Search results for " permutation"
showing 10 items of 41 documents
A Note on Resampling the Integration Across the Correlation Integral with Alternative Ranges
2003
Abstract This paper reconsiders the nonlinearity test proposed by Ko[cbreve]enda (Ko[cbreve]enda, E. (2001). An alternative to the BDS test: integration across the correlation integral. Econometric Reviews20:337–351). When the analyzed series is non‐Gaussian, the empirical rejection rates can be much larger than the nominal size. In this context, the necessity of tabulating the empirical distribution of the statistic each time the test is computed is stressed. To that end, simple random permutation works reasonably well. This paper also shows, through Monte Carlo experiments, that Ko[cbreve]enda's test can be more powerful than the Brock et al. (Brock, W., Dechert, D., Scheickman, J., LeBar…
The measurement of rank mobility
2009
Abstract In this paper we investigate the problem of measuring social mobility when the social status of individuals is given by their rank. In order to sensibly represent the rank mobility of subgroups within a given society, we address the problem in terms of partial permutation matrices which include standard (“global”) matrices as a special case. We first provide a characterization of a partial ordering on partial matrices which, in the standard case of global matrices, coincides with the well-known “concordance” ordering. We then provide a characterization of an index of rank mobility based on partial matrices and show that, in the standard case of comparing global matrices, it is equi…
Quantum lower bound for inverting a permutation with advice
2014
Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input $y$. Classically, there is a data structure of size $\tilde{O}(S)$ and an algorithm that with the help of the data structure, given $f(x)$, can invert $f$ in time $\tilde{O}(T)$, for every choice of parameters $S$, $T$, such that $S\cdot T \ge N$. We prove a quantum lower bound of $T^2\cdot S \ge \tilde{\Omega}(\epsilon N)$ for quantum algorithms that invert a random permutation $f$ on an $\epsilon$ fraction of…
Mahonian STAT on words
2016
In 2000, Babson and Steingrimsson introduced the notion of what is now known as a permutation vincular pattern, and based on it they re-defined known Mahonian statistics and introduced new ones, proving or conjecturing their Mahonity. These conjectures were proved by Foata and Zeilberger in 2001, and by Foata and Randrianarivony in 2006.In 2010, Burstein refined some of these results by giving a bijection between permutations with a fixed value for the major index and those with the same value for STAT , where STAT is one of the statistics defined and proved to be Mahonian in the 2000 Babson and Steingrimsson's paper. Several other statistics are preserved as well by Burstein's bijection.At…
Characterizing normal Sylow p-subgroups by character degrees
2012
Abstract Suppose that G is a finite group, let p be a prime and let P ∈ Syl p ( G ) . We prove that P is normal in G if and only if all the irreducible constituents of the permutation character ( 1 P ) G have degree not divisible by p.
Gray code for permutations with a fixed number of cycles
2007
AbstractWe give the first Gray code for the set of n-length permutations with a given number of cycles. In this code, each permutation is transformed into its successor by a product with a cycle of length three, which is optimal. If we represent each permutation by its transposition array then the obtained list still remains a Gray code and this allows us to construct a constant amortized time (CAT) algorithm for generating these codes. Also, Gray code and generating algorithm for n-length permutations with fixed number of left-to-right minima are discussed.
Lines on the Dwork pencil of quintic threefolds
2012
We present an explicit parametrization of the families of lines of the Dwork pencil of quintic threefolds. This gives rise to isomorphic curves which parametrize the lines. These curves are 125:1 covers of certain genus six curves. These genus six curves are first presented as curves in P^1*P^1 that have three nodes. It is natural to blow up P^1*P^1 in the three points corresponding to the nodes in order to produce smooth curves. The result of blowing up P^1*P^1 in three points is the quintic del Pezzo surface dP_5, whose automorphism group is the permutation group S_5, which is also a symmetry of the pair of genus six curves. The subgroup A_5, of even permutations, is an automorphism of ea…
From First Principles to the Burrows and Wheeler Transform and Beyond, via Combinatorial Optimization
2007
AbstractWe introduce a combinatorial optimization framework that naturally induces a class of optimal word permutations with respect to a suitably defined cost function taking into account various measures of relatedness between words. The Burrows and Wheeler transform (bwt) (cf. [M. Burrows, D. Wheeler, A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, 1994]), and its analog for labelled trees (cf. [P. Ferragina, F. Luccio, G. Manzini, S. Muthukrishnan, Structuring labeled trees for optimal succinctness, and beyond, in: Proc. of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 198–207]), are special cases i…
Combinatorial Gray codes for classes of pattern avoiding permutations
2007
The past decade has seen a flurry of research into pattern avoiding permutations but little of it is concerned with their exhaustive generation. Many applications call for exhaustive generation of permutations subject to various constraints or imposing a particular generating order. In this paper we present generating algorithms and combinatorial Gray codes for several families of pattern avoiding permutations. Among the families under consideration are those counted by Catalan, Schr\"oder, Pell, even index Fibonacci numbers and the central binomial coefficients. Consequently, this provides Gray codes for $\s_n(\tau)$ for all $\tau\in \s_3$ and the obtained Gray codes have distances 4 and 5.
Tetravalent single-chain avidin: from subunits to protein domains via circularly permuted avidins
2005
scAvd (single-chain avidin, where two dcAvd are joined in a single polypeptide chain), having four biotin-binding domains, was constructed by fusion of topologically modified avidin units. scAvd showed similar biotin binding and thermal stability properties as chicken avidin. The DNA construct encoding scAvd contains four circularly permuted avidin domains, plus short linkers connecting the four domains into a single polypeptide chain. In contrast with wild-type avidin, which contains four identical avidin monomers, scAvd enables each one of the four avidin domains to be independently modified by protein engineering. Therefore the scAvd scaffold can be used to construct spatially and stoich…