Stellar permutations of the two-element subsets of a finite set

Let X be a finite set and denote by X⁽²⁾ the set of 2-element subsets of X. A permutation ϕ of X⁽²⁾ is called stellar if, for each x in X, the image under ϕ of the star St(x) = {{x, y}: x ≠ y ∈ X} is a 2-regular graph spanning X − {x}. Several constructions of stellar permutations are given; in particular, there is a natural direct construction using self-orthogonal Latin squares, and a simple recursive construction using linear spaces having all line sizes at least four. Apart from some intrinsic interest, stellar permutations arise in the construction of certain designs. For example, applying such a map ϕ to each of the stars St(x) yields a double covering of the complete graph on X by near 2-factors. We also study stellar groups, that is groups {ϕ₁, …, ϕ_s} of permutations of X⁽²⁾ such that each ϕ_i is stellar (or the identity map). It is elementary to prove that s ≤ for any stellar group; when equality holds, one can construct an associated elation semibiplane. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 381–387, 1998     

Patterns in random permutations avoiding the pattern 321

We consider a random permutation drawn from the set of 321 ‐avoiding permutations of length n and show that the number of occurrences of another pattern σ has a limit distribution, after scaling by n^{m + ?} where m is the length of σ and ? is the number of blocks in it. The limit is not normal, and can be expressed as a functional of a Brownian excursion.     

On the minimum number of completely 3-scrambling permutations

A family P={π₁,…,π_q} of permutations of [n]={1,…,n} is completely k-scrambling [Spencer, Acta Math Hungar 72; Füredi, Random Struct Algor 96] if for any distinct k points x₁,…,x_k∈[n], permutations π_i's in P produce all k! possible orders on π_i(x₁),…,π_i(x_k). Let N^*(n,k) be the minimum size of such a family. This paper focuses on the case k=3. By a simple explicit construction, we show the following upper bound, which we express together with the lower bound due to Füredi for comparison.

     

Spherically symmetric random permutations

We consider random permutations which are spherically symmetric with respect to a metric on the symmetric group S_n and are consistent as n varies. The extreme infinitely spherically symmetric permutation‐valued processes are identified for the Hamming, Kendall‐tau and Cayley metrics. The proofs in all three cases are based on a unified approach through stochastic monotonicity.     

The maximal-inversion statistic and pattern-avoiding permutations

We define a new combinatorial statistic, maximal-inversion, on a permutation. We remark that the number M(n,k) of permutations in S_n with k maximal-inversions is the signless Stirling number c(n,n−k) of the first kind. A permutation π in S_n is uniquely determined by its maximal-inversion set . We prove it by making an algorithm for retrieving the permutation from its maximal-inversion set. Also, we remark on how the algorithm can be used directly to determine whether a given set is the maximal-inversion set of a permutation. As an application of the algorithm, we characterize the maximal-inversion set for pattern-avoiding permutations. Then we give some enumerative results concerning permutations with forbidden patterns.     

On the number of queries necessary to identify a permutation

Let p and q be two permutations over {1, 2,…, n}. We denote by m(p, q) the number of integers i, 1 ≤ i ≤ n, such that p(i) = q(i). For each fixed permutation p, a query is a permutation q of the same size and the answer a(q) to this query is m(p, q). We investigate the problem of finding the minimum number of queries required to identify an unknown permutation p. A polynomial-time algorithm that identifies a permutation of size n by O(n · log₂n) queries is presented. The lower bound of this problem is also considered. It is proved that the problem of determining the size of the search space created by a given set of queries and answers is #P-complete. Since this counting problem is essential for the analysis of the lower bound, a complete analysis of the lower bound appears infeasible. We conjecture, based on some preliminary analysis, that the lower bound is Ω(n · log₂n).     

Permutation Matrices, Wreath Products, and the Distribution of Eigenvalues

We consider a class of random matrix ensembles which can be constructed from the random permutation matrices by replacing the nonzero entries of the n×n permutation matrix matrix with M×M diagonal matrices whose entries are random Kth roots of unity or random points on the unit circle. Let X be the number of eigenvalues lying in a specified arc I of the unit circle, and consider the standardized random variable (X–E[X])/(Var(X))^1/2. We show that for a fixed set of arcs I ₁,...,I _N , the corresponding standardized random variables are jointly normal in the large n limit, and compare the covariance structures which arise with results for other random matrix ensembles.     

The Number of Permutations with Exactlyr132-Subsequences IsP-Recursive in the Size!

Proving a first nontrivial instance of a conjecture of Noonan and Zeilberger we show that the numberS_r(n) of permutations of lengthncontaining exactlyrsubsequences of type 132 is aP-recursive function ofn. We show that this remains true even if we impose some restrictions on the permutations. We also show the stronger statement that the ordinary generating functionG_r(x) ofS_r(n) is algebraic, in fact, it is rational in the variablesxand . We use this information to show that the degree of the polynomial recursion satisfied byS_r(n) isr.     

On some applications of a discrete-time model of failure and repair

Research on a discrete-time model of failure and repair studied by Rocha-Martinez and Shaked (1995) is continued in this paper. Among various related results, we prove that if for one point x∈]0,1[ the probability generating function of a non-negative integer valued random variable S satisfies Φ_S(x)⩽x^m for some integer m⩾0, then E(S)⩾m. We use these results to show that for any M (the ‘input’ lifetime of a unit in the model) the R_m's (the allowed number of repairs on the unit at time m, m⩾0) can be chosen such that M_u (the ‘output’ lifetime of the unit through the model) is in hazard rate ordering (therefore in stochastic ordering) arbitrarily large and such that E(R_m) is a minimum in some sense. As a first application, we see how a low-quality item (car, computer, washing machine, etc.) might fulfil strict durability regulations under an appropriate imperfect repair strategy (and be able to compete against the existing leading brand in the market) in such a way that the mean number of repairs be a minimum in some sense. As a second application we show how it can be easily proven that if M is of class: NBU, NWE, DMRL, IMRL, NBUE or NWUE, then M_u is not necessarily of the same class. © 1998 John Wiley & Sons, Ltd.     

Random and algebraic permutations’ statistics

An algebraic permutation $\hat{A}\in S(N=n^{m})$ is the permutation of the N points of the finite torus ? _n ^m , realized by a linear operator A∈SL(m,? _n ). The statistical properties of algebraic permutations are quite different from those of random permutations of N points. For instance, the period length T(A) grows superexponentially with N for some (random) permutations A of N elements, whereas $T(\hat{A})$ is bounded by a power of N for algebraic permutations  $\hat{A}$ . The paper also contains a strange mean asymptotics formula for the number of points of the finite projective line P¹(? _n ) in terms of the zeta function.     

Law of large numbers for increasing subsequences of random permutations

Let the random variable Z_n,k denote the number of increasing subsequences of length k in a random permutation from S_n, the symmetric group of permutations of {1,…,n}. We show that Var(Z) = o((EZ)²) as n → ∞ if and only if . In particular then, the weak law of large numbers holds for Z if ; that is, We also show the following approximation result for the uniform measure U_n on S_n. Define the probability measure μ on S_n by where U denotes the uniform measure on the subset of permutations that contain the increasing subsequence {x₁,x₂,…,x}. Then the weak law of large numbers holds for Z if and only if where ∣∣˙∣∣ denotes the total variation norm. In particular then, (*) holds if . In order to evaluate the asymptotic behavior of the second moment, we need to analyze occupation times of certain conditioned two‐dimensional random walks. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

A problem on semigroups satisfying permutation identities

Let σ be a nontrivial permutation of ordern. A semigroupS is said to be σ-permutable ifx ₁ x ₂ ...x _n =x _σ(1) x _σ(2) ...x _σ(n) , for every (x ₁ ,x ₂,...,x _n )∈S ⁿ . A semigroupS is called(r,t)-commutative, wherer,t are in ℕ^*, ifx ₁ ...x _r x _r+1 ...x _r+t =x _r+1 ...x _r+t x ₁ ...x _r , for every (x ₁ ,x ₂,...,x _r+t ∈S ^r+t . According to a result of M. Putcha and A. Yaqub ([11]), if σ is a fixed-point-free permutation andS is a σ-permutable semigroup then there existsk ∈ ℕ^* such thatS is (1,k)-commutative. In [8], S. Lajos raises up the problem to determine the leastk=k(n) ∈ ℕ^* such that, for every fixed-point-free permutation σ of ordern, every σ-permutable semigroup is also (1,k)-commutative. In this paper this problem is solved for anyn less than or equal to eight and also whenn is any odd integer. For doing this we establish that if a semigroup satisfies a permutation identity of ordern then inevitably it also satisfies some permutation identities of ordern+1.     

Setwise intersecting families of permutations

A family of permutations A⊂Sn is said to be t-set-intersecting if for any two permutations σ,π∈A, there exists a t-set x whose image is the same under both permutations, i.e. σ(x)=π(x). We prove that if n is sufficiently large depending on t, the maximum-sized t-set-intersecting families of permutations in Sn are cosets of stabilizers of t-sets. The t=2 case of this was conjectured by János Körner. It can be seen as a variant of the Deza-Frankl conjecture, proved in Ellis, Friedgut and Pilpel (2011) [3]. Our proof uses similar techniques to those of Ellis, Friedgut and Pilpel (2011) [3], namely, eigenvalue methods, together with the representation theory of the symmetric group, but the combinatorial part of the proof is harder.     

Surjective partial differential operators on real analytic functions defined on open convex sets

Let P(D) be a partial differential operator with constant coefficients which is surjective on the space A(Ω) of real analytic functions on a covex open set Ω⊂ℝ ⁿ . Let L(P _m ) denote the localizations at ∞ (in the sense of H?rmander) of the principal part P _m . Then Q(x+iτN)≠ 0 for (x,τ)∈ℝ ⁿ ×(ℝ\{ 0}) for any Q∈L(P _m ) if N is a normal to δΩ which is noncharacteristic for Q. Under additional assumptions this implies that P _m must be locally hyperbolic. Received: 24 January 2000     

Large deviations and moments for the Euler characteristic of a random surface

We study random surfaces constructed by glueing together N/k filled k‐gons along their edges, with all (N ? 1)!! = (N ? 1)(N ? 3)···3 · 1 pairings of the edges being equally likely. (We assume that lcm{2,k} divides N.) The Euler characteristic of the resulting surface is related to the number of cycles in a certain random permutation of {1,…,N}. Gamburd has shown that when 2 lcm{2,k} divides N, the distribution of this random permutation converges to that of the uniform distribution on the alternating group A_N in the total‐variation distance as N → ∞. We obtain large‐deviations bounds for the number of cycles that, together with Gamburd's (Ann Probab 34 (2006), 1827–1848) result, allow us to derive sharp estimates for the moments of the number of cycles. These estimates allow us to confirm certain cases of conjectures made by Pippenger and Schleich (Random Struct Algorithm 28 (2006), 247–288). © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Binomial posets, Möbius inversion, and permutation enumeration

A unified method is presented for enumerating permutations of sets and multisets with various conditions on their descents, inversions, etc. We first prove several formal identities involving Möbius functions associated with binomial posets. We then show that for certain binomial posets these Möbius functions are related to problems in permutation enumeration. Thus, for instance, we can explain “why” the exponential generating function for alternating permutations has the simple form (1 + sin x)/(cos x). We can also clarify the reason for the ubiquitous appearance of e^x in connection with permutations of sets, and of ξ(s) in connection with permutations of multisets.     

Asymptotics of random sums of negatively dependent random variables in the presence of dominatedly varying tails

Let X ₁ , X ₂ , . . . be a sequence of negatively dependent and identically distributed random variables, and let N be a counting random variable independent of X _i ’s. In this paper, we study the asymptotics for the tail probability of the random sum S_N = ?_{k = 1}^N X_k {S_N} = \sum\nolimits_{k = 1}^N {{X_k}} in the presence of heavy tails. We consider the following three cases: (i) P(N > x) = o(P(X ₁  > x)), and the distribution function (d.f.) of X ₁ is dominatedly varying; (ii) P(X ₁  > x) = o(P(N > x)), and the d.f. of N is dominatedly varying; (iii) the tails of X ₁ and N are asymptotically comparable and dominatedly varying.     

Some highly symmetric authentication perpendicular arrays

A set S of permutations of k objects is -uniform, t-homogeneous if for every pair A, B of t-subsets of the ground set, there are exactly permutations in S mapping A onto B. Arithmetical conditions and symmetries are discussed. We describe the character-theoretic method which is useful if S is contained in a permutation group. A main result is the construction of a 2-uniform, 2-homogeneous set of permutations on 6 objects and of a 3-uniform, 3-homogeneous set of permutations on 9 objects. These are contained in the simple permutation groups PSL ₂(5) and PSL ₂(8), respectively. The result is useful in the framework of theoretical secrecy and authentication (see Stinson 1990, Bierbrauer and Tran 1991).     

Extinction and non-extinction for a polytropic filtration equation with a nonlocal source

In this article, the authors establish the conditions for the extinction of solutions, in finite time, of the fast diffusive polytropic filtration equation u _t ?=?div(|?u ^m | ^p?2?u ^m )?+?a∫_Ω u ^q (y,?t)dy with a, q, m?>?0, p?>?1, m(p???1)?R ^N (N?>?2). More precisely speaking, it is shown that if q?>?m(p???1), any non-negative solution with small initial data vanishes in finite time, and if 0?q?m(p???1), there exists a solution which is positive in Ω for all t?>?0. For the critical case q?=?m(p???1), whether the solutions vanish in finite time or not depends on the comparison between a and μ, where μ?=?∫?_Ωφ ^p?1(x)dx and φ is the unique positive solution of the elliptic problem ?div(|?φ| ^p?2?φ)?=?1, x?∈?Ω; φ(x)?=?0, x?∈??Ω.     

Permutation-operator inequalities on certain symmetry classes of tensors

If A∈T(m, N), the real-valued N-linear functions on E_m, and σ∈S_N, the symmetric group on {…,N}, then we define the permutation operator P_σ: T(m, N) → T(m, N) such that P_σ(A)(x₁,x₂,…,x_N = A(x_σ(1),x_σ(2),…, x_σ(N)). Suppose Σ^q_i=1n_i = N, where the n_i are positive integers. In this paper we present a condition on σ that is sufficient to guarantee that 〈P_σ(A₁?A₂???A_q),A₁?A₂?? ? A_q〉 ? 0 for A_i∈S(m, n_i), where S(m, n_i) denotes the subspace of T(m, n_i) consisting of all the fully symmetric members of T(m, n_i). Also we present a broad generalization of the Neuberger identity which is sometimes useful in answering questions of the type described below. Suppose G and H are subgroups of S_N. We let T_G(m, N) denote all A∈T(m, N) such that P_σ(A) = A for all σ∈G. We define the symmetrizer $\text{S}$_G: T(m, N)→T_G(m,N) such that $\text{S}{}_{\mathrm{G}}\text{(A) = 1/|G|Σ}{}_{\mathrm{\sigma \in G}}\text{P}{}_{\mathrm{\sigma }}\text{(A)}$. Suppose H is a subgroup of G and A∈T_H(m, N). Clearly $\text{6}\text{S}{}_{\mathrm{<mtext>G</mtext>}}\text{6(A) 6? 6A6.}$ We are interested in the reverse type of comparison. In particular, if D is a suitably chosen subset of T_H(m,N), then can we explicitly present a constant C>0 such that $\text{6}\text{S}{}_{\mathrm{G}}\text{(A)6?C6A6}$ for all A∈D?