PRESENTATIONS FOR SOME MONOIDS OF PARTIAL TRANSFORMATIONS ON A FINITE CHAIN

ABSTRACT

In this paper we calculate presentations for some natural monoids of transformations on a chain X _n  = {1 < 2 <?s < n}. First we consider 𝒪𝒟 _n [𝒫𝒪𝒟 _n ], the monoid of all full [partial] transformations on X _n that preserve or reverse the order. Two other monoids of partial transformations on X _n we look at are 𝒫𝒪𝒫 _n and 𝒫𝒪? _n –-the elements of the first preserve the orientation and the elements of the second preserve or reverse the orientation.     

On the Structure of IO n

Abstract. We study the structure of the semigroup IO _n of all order-preserving partial bijections on an n -element set. For this semigroup we describe maximal subsemigroups, maximal inverse subsemigroups, automorphisms and maximal nilpotent subsemigroups. We also calculate the maximal cardinality for the nilpotent subsemigroups in IO _n which happens to be given by the n -th Catalan number.     

Maximal Subsemigroups of Finite Transformation Semigroups K（n, r）

Let Tn be the full transformation semigroup on the n-element set Xn. For an arbitrary integer r such that 2 ≤ r ≤ n-1, we completely describe the maximal subsemigroups of the semigroup K(n, r) = {α∈Tn : |im α| ≤ r}. We also formulate the cardinal number of such subsemigroups which is an answer to Problem 46 of Tetrad in 1969, concerning the number of subsemigroups of Tn.     

Prophet regions and sharp inequalities for pth absolute moments of martingales

Exact comparisons are made relating E|Y₀|^p, E|Y_n−1|^p, and E(max_j≤n−1 |Y_j|^p), valid for all martingales Y₀,…,Y_n−1, for each p ≥ 1. Specifically, for p > 1, the set of ordered triples {(x, y, z) : X = E|Y₀|^p, Y = E |Y_n−1|^p, and Z = E(max_j≤n−1 |Y_j|^p) for some martingale Y₀,…,Y_n−1} is precisely the set {(x, y, z) : 0≤x≤y≤z≤Ψ_n,p(x, y)}, where Ψ_n,p(x, y) = xψ_n,p(y/x) if x > 0, and = a_n−1,py if x = 0; here ψ_n,p is a specific recursively defined function. The result yields families of sharp inequalities, such as E(max_j≤n−1 |Y_j|^p) + ψ_n,p^*(a) E |Y₀|^p ≤ aE |Y_n−1|^p, valid for all martingales Y₀,…,Y_n−1, where ψ_n,p^* is the concave conjugate function of ψ_n,p. Both the finite sequence and infinite sequence cases are developed. Proofs utilize moment theory, induction, conjugate function theory, and functional equation analysis.     

Expanders obtained from affine transformations

A bipartite graphG=(U, V, E) is an (n, k, δ, α) expander if |U|=|V|=n, |E|≦kn, and for anyX⊆U with |X|≦αn, |Γ _G (X)|≧(1+δ(1−|X|/n)) |X|, whereΓ _G (X) is the set of nodes inV connected to nodes inX with edges inE. We show, using relatively elementary analysis in linear algebra, that the problem of estimating the coefficientδ of a bipartite graph is reduced to that of estimating the second largest eigenvalue of a matrix related to the graph. In particular, we consider the case where the bipartite graphs are defined from affine transformations, and obtain some general results on estimating the eigenvalues of the matrix by using the discrete Fourier transform. These results are then used to estimate the expanding coefficients of bipartite graphs obtained from two-dimensional affine transformations and those obtained from one-dimensional ones.     

Idempotent Generation in the Endomorphism Monoid of a Uniform Partition

Denote by 𝒯_n and 𝒮_n the full transformation semigroup and the symmetric group on the set {1,…, n}, and ?_n = {1} ∪ (𝒯_n?𝒮_n). Let 𝒯(X, 𝒫) denote the monoid of all transformations of the finite set X preserving a uniform partition 𝒫 of X into m subsets of size n, where m, n ≥ 2. We enumerate the idempotents of 𝒯(X, 𝒫), and describe the submonoid S = ? E ? generated by the idempotents E = E(𝒯(X, 𝒫)). We show that S = S₁ ∪ S₂, where S₁ is a direct product of m copies of ?_n, and S₂ is a wreath product of 𝒯_n with 𝒯_m?𝒮_m. We calculate the rank and idempotent rank of S, showing that these are equal, and we also classify and enumerate all the idempotent generating sets of minimal size. In doing so, we also obtain new results about arbitrary idempotent generating sets of ?_n.     

Hereditarily finitely based monoids of extensive transformations

It is shown that the monoid E _n of extensive transformations of a chain of order n is hereditarily finitely based if and only if n ≤ 3. It follows that the submonoid OE _n of order-preserving transformations in E _n is also hereditarily finitely based if and only if n ≤ 3.     

Inequalities for a Polynomial and Its Derivative II

A well-known result of Rivlin states that if p(z) is a polynomial of degree n, such that p(z) ≠ 0 in |z| < 1, then max_{|z|=r < 1} |p(z)| ≤ ((r + 1)/2)ⁿ max_{|z| = 1} |p(z)|. In this paper, we consider the polynomial p(z) = a₀ + Σⁿ_{v = μ}a_υz^υ having all its zeros in |z| ≤ k > 1 and obtain a generalization of this result. Our result improves upon a result recently proved by Bidkham and Dewan (J. Math. Anal. Appl.166 (1992), 19-324).     

On deviations between empirical and quantile processes for mixing random variables

Let {X_n} be a strictly stationary φ-mixing process with Σ_j=1^∞ φ^1/2(j) < ∞. It is shown in the paper that if X₁ is uniformly distributed on the unit interval, then, for any t [0, 1], |F_n⁻¹(t) − t + F_n(t) − t| = O(n^−3/4(log log n)^3/4) a.s. and sup_0≤t≤1 |F_n⁻¹(t) − t + F_n(t) − t| = (O(n^−3/4(log n)^1/2(log log n)^1/4) a.s., where F_n and F_n⁻¹(t) denote the sample distribution function and tth sample quantile, respectively. In case {X_n} is strong mixing with exponentially decaying mixing coefficients, it is shown that, for any t [0, 1], |F_n⁻¹(t) − t + F_n(t) − t| = O(n^−3/4(log n)^1/2(log log n)^3/4) a.s. and sup_0≤t≤1 |F_n⁻¹(t) − t + F_n(t) − t| = O(n^−3/4(log n)(log log n)^1/4) a.s. The results are further extended to general distributions, including some nonregular cases, when the underlying distribution function is not differentiable. The results for φ-mixing processes give the sharpest possible orders in view of the corresponding results of Kiefer for independent random variables.     

Combinatorial Results for Semigroups of Order-Preserving Full Transformations

Let O_n be the semigroup of all order-preserving full transformations of a finite chain, say X_n = {1, 2, ..., n}, and for a given full transformation α: X_n → X_n let f(α) = |{x ∈ X_n: xα = x}|. In this note we obtain and discuss formulae for f(n,r,k) = |{α → O_n: f(α) = r ∧ max(Im α) = k}| and J(n,r,k) = |{α → O_n: |Im α| = r ∧ max(Im α) = k}|. We also obtain similar results for E(O_n), the set of idempotents of O_n.     

Second-order linearity of the general signed-rank statistic

Let X₁,…, X_n be i.i.d. random variables symmetric about zero. Let R_i(t) be the rank of |X_i − tn^−1/2| among |X₁ − tn^−1/2|,…, |X_n − tn^−1/2| and T_n(t) = Σ_{i = 1}ⁿφ((n + 1)⁻¹R_i(t))sign(X_i − tn^−1/2). We show that there exists a sequence of random variables V_n such that sup_{0 ≤ t ≤ 1} |T_n(t) − T_n(0) − tV_n| → 0 in probability, as n → ∞. V_n is asymptotically normal.     

On the Monoid of All Partial Order-Preserving Extensive Transformations

A partial transformation α on an n-element chain X _n is called order-preserving if x ≤ y implies xα ≤yα for all x, y in the domain of α and it is called extensive if x ≤ xα for all x in the domain of α. The set of all partial order-preserving extensive transformations on X _n forms a semiband POE _n . We determine the maximal subsemigroups as well as the maximal subsemibands of POE _n .     

Sylow Products and the Solvable Residual

We study the connection between products of Sylow subgroups of a finite group G and the solvable residual of G. Let Π(𝒫) be a product of Sylow subgroups of G such that each prime divisor of |G| is represented exactly once in Π(𝒫). We prove that there exists a unique normal subgroup N of G which is minimal subject to the requirement Π(𝒫) N = G. Furthermore, N is perfect, and the product of all of these subgroups is the solvable residual of G. We also prove that the solvable residual of G is generated by all elements which arise from non-trivial factorizations of 1 _G in such products of Sylow subgroups.     

On the approximate behavior of the posterior distribution for an extreme multivariate observation

The behavior of the posterior for a large observation is considered. Two basic situations are discussed; location vectors and natural parameters.Let X = (X₁, X₂, …, X_n) be an observation from a multivariate exponential distribution with that natural parameter Θ = (Θ₁, Θ₂, …, Θ_n). Let θ_x^* be the posterior mode. Sufficient conditions are presented for the distribution of Θ − θ_x^* given X = x to converge to a multivariate normal with mean vector 0 as |x| tends to infinity. These same conditions imply that E(Θ | X = x) − θ_x^* converges to the zero vector as |x| tends to infinity.The posterior for an observation X = (X₁, X₂, …, X_n is considered for a location vector Θ = (Θ₁, Θ₂, …, Θ_n) as x gets large along a path, γ, in Rⁿ. Sufficient conditions are given for the distribution of γ(t) − Θ given X = γ(t) to converge in law as t → ∞. Slightly stronger conditions ensure that γ(t) − E(Θ | X = γ(t)) converges to the mean of the limiting distribution.These basic results about the posterior mean are extended to cover other estimators. Loss functions which are convex functions of absolute error are considered. Let δ be a Bayes estimator for a loss function of this type. Generally, if the distribution of Θ − E(Θ | X = γ(t)) given X = γ(t) converges in law to a symmetric distribution as t → ∞, it is shown that δ(γ(t)) − E(Θ | X = γ(t)) → 0 as t → ∞.     

Exponential bounds of mean error for the kernel estimates of regression functions

Let (X, Y), (X₁, Y₁), …, (X_n, Y_n) be i.d.d. R^r × R-valued random vectors with E|Y| < ∞, and let Q_n(x) be a kernel estimate of the regression function Q(x) = E(Y|X = x). In this paper, we establish an exponential bound of the mean deviation between Q_n(x) and Q(x) given the training sample Zⁿ = (X₁, Y₁, …, X_n, Y_n), under conditions as weak as possible.     

On the structure of IO n

We study the structure of the semigroup IO _n of all order-preserving partial bijections on an n-element set. For this semigroup we describe maximal subsemigroups, maximal inverse subsemigroups, automorphisms and maximal nilpotent subsemigroups. We also calculate the maximal cardinality for the nilpotent subsemigroups in IO _n which happens to be given by the n-th Catalan number.     

On Sums of Two Coprime k-th Powers(II)

For fixed k ≥ 3, let E_k(x) denote the error term of the sum ?_{n ￡ x}r_k(n)\sum_{n\le x}\rho_k(n) , where r_k(n) = ?_{n=|m|^k+|l|^k, g.c.d.(m,l)=1}\rho_k(n) = \sum_{n=|m|^k+|l|^k, g.c.d.(m,l)=1} 1. It is proved that if the Riemann hypothesis is true, then E₃(x) << x^331/1254+eE_3(x)\ll x^{331/1254+\varepsilon} , E₄(x) << x^37/184+eE_4(x)\ll x^{37/184+\varepsilon} . A short interval result is also obtained.     

Strong asymptotics in Lagrange interpolation with equidistant nodes

In this paper we prove three conjectures of Revers on Lagrange interpolation for f_λ(t)=|t|^λ,λ>0, at equidistant nodes. In particular, we describe the rate of divergence of the Lagrange interpolants L_N( f_λ,t) for 0<|t|<1, and discuss their convergence at t=0. We also establish an asymptotic relation for max_|t|1| |t|^λ−L_N( f_λ,t)|. The proofs are based on strong asymptotics for |t|^λ−L_N( f_λ,t), 0|t|<1.     

Covering times of random walks on bounded degree trees and other graphs

The motivating problem for this paper is to find the expected covering time of a random walk on a balanced binary tree withn vertices. Previous upper bounds for general graphs ofO(|V| |E|)⁽¹⁾ andO(|V| |E|/d _min)⁽²⁾ imply an upper bound ofO(n ²). We show an upper bound on general graphs ofO( |E| log |V|), which implies an upper bound ofO(n log² n). The previous lower bound was (|V| log |V|) for trees.⁽²⁾ In our main result, we show a lower bound of (|V| (log _{d max} |V|)²) for trees, which yields a lower bound of (n log² n). We also extend our techniques to show an upper bound for general graphs ofO(max{E T_i} log |V|).