New integral representations of nth order convex functions

In this paper we give an integral representation of an n-convex function f in general case without additional assumptions on function f. We prove that any n-convex function can be represented as a sum of two (n+1)-times monotone functions and a polynomial of degree at most n. We obtain a decomposition of n-Wright-convex functions which generalizes and complements results of Maksa and Páles (2009) [13]. We define and study relative n-convexity of n-convex functions. We introduce a measure of n-convexity of f. We give a characterization of relative n-convexity in terms of this measure, as well as in terms of nth order distributional derivatives and Radon-Nikodym derivatives. We define, study and give a characterization of strong n-convexity of an n-convex function f in terms of its derivative f(n+1)(x) (which exists a.e.) without additional assumptions on differentiability of f. We prove that for any two n-convex functions f and g, such that f is n-convex with respect to g, the function g is the support for the function f in the sense introduced by W?sowicz (2007) [29], up to polynomial of degree at most n.     

On the decomposition of n! into prime powers

If n is a positive integer, we write n! as a product of n prime powers, each at least as large as n^δ(n). We define α(n) to be max δ(n), where the maximum is taken over all decompositions of the required type. We then show that lim_n→∞α(n) exists, and we calculate its value.     

Note on the size of binary Armstrong codes

We show for binary Armstrong codes Arm(2, k, n) that asymptotically n/k ≤ 1.224, while such a code is shown to exist whenever n/k ≤ 1.12. We also construct an Arm(2, n ? 2, n) and Arm(2, n ? 3, n) for all admissible n.     

Scheduling CCRR tournaments

In this paper, we construct CCRRS, complete coupling round robin schedules, for n teams each consisting of two pairs. The motivation for these schedules is a problem in scheduling bridge tournaments. We construct CCRRS(n) for n a positive integer, n?3, with the possible exceptions of n∈{54,62}. For n odd, we show that a CCRRS(n) can be constructed using a house with a special property. For n even, a CCRRS(n) can be constructed from a Howell design, H(2n-2,2n), with a special property called Property P. We use a combination of direct and recursive constructions to construct H(2n-2,2n) with Property P. In order to apply our main recursive construction, we need group divisible designs with odd group sizes and odd block sizes. One of our main results is the existence of these group divisible designs.     

A note on growing binary trees

The class ? of binary search trees is studied. A leaf is a vertex of degree 0; ?_n is the subset of ? consisting of trees with n leaves. We grow trees in ?_n from ?_n ? 1 thereby inducing a probability measure on ?_n. We will show that the expected value of the average leaf distance of t ∈ ?_n is asymptotic to log₂n as n → ∞.     

Integrability of rotationally symmetric n-harmonic maps

A rotationally symmetric n-harmonic map is a rotationally symmetric p-harmonic map between two n-dimensional model spaces such that p=n. We show that rotationally symmetric n-harmonic maps can be integrated and are n-harmonic diffeomorphism, and apply such results to investigate the asymptotic behaviors of these maps. We also derive this integrability using Lie theory.     

Large deviations of the extreme eigenvalues of random deformations of matrices

Consider a real diagonal deterministic matrix X _n of size n with spectral measure converging to a compactly supported probability measure. We perturb this matrix by adding a random finite rank matrix, with delocalized eigenvectors. We show that the joint law of the extreme eigenvalues of the perturbed model satisfies a large deviation principle in the scale n, with a good rate function given by a variational formula. We tackle both cases when the extreme eigenvalues of X _n converge to the edges of the support of the limiting measure and when we allow some eigenvalues of X _n , that we call outliers, to converge out of the bulk. We can also generalise our results to the case when X _n is random, with law proportional to e ^{?n Tr V(X)} dX, for V growing fast enough at infinity and any perturbation of finite rank.     

Shortest string containing all permutations

In this paper, we consider the problem of constructing a shortest string of {1,2,…,n} containing all permutations on n elements as subsequences. For example, the string 1 2 1 3 1 2 1 contains the 6 (=3!) permutations of {1,2,3} and no string with less than 7 digits contains all the six permutations. Note that a given permutation, such as 1 2 3, does not have to be consecutive but must be from left to right in the string.We shall first give a rule for constructing a string of {1,2,…,n} of infinite length and the show that the leftmost n²?2n+4 digits of the string contain all the n! permutations (for n≥3). We conjecture that the number of digits f(n) = n²?2n+4 (for n≥3) is the minimum.Then we study a new function F(n,k) which is the minimum number of digits required for a string of n digits to contain all permutations of i digits, i≤k. We conjecture that F(n,k) = k(n?1) for 4≤k ≤n?1.     

Latin trades on three or four rows

Latin trades are closely related to the problem of critical sets in Latin squares. We denote the cardinality of the smallest critical set in any Latin square of order n by scs(n). A consideration of Latin trades which consist of just two columns, two rows, or two elements establishes that scs(n)?n-1. We conjecture that a consideration of Latin trades on four rows may establish that scs(n)?2n-4. We look at various attempts to prove a conjecture of Cavenagh about such trades. The conjecture is proven computationally for values of n less than or equal to 9. In particular, we look at Latin squares based on the group table of Z_n for small n and trades in three consecutive rows of such Latin squares.     

Matrices permutation equivalent to primitive matrices

We give a necessary and sufficient condition for an n×n (0,1) matrix (or more generally, an n×n nonnegative matrix) to be permutation equivalent to a primitive matrix. More precisely, except for two simple permutation equivalent classes of n×n (0,1) matrices, each n×n (0,1) matrix having no zero row or zero column is permutation equivalent to some primitive matrix. As an application, we use this result to characterize the subsemigroup of B_n (B_n is the multiplicative semigroup of n×n Boolean matrices) generated by all the primitive matrices and permutation matrices. We also consider a more general problem and give a necessary and sufficient condition for an n×n nonnegative matrix to be permutation equivalent to an irreducible matrix with given imprimitive index.     

Extremal critically connected matroids

A connected matroid M is called a critically connected matroid if the deletion of any one element from M results in a disconnected matroid. We show that a critically connected matroid of rank n, n≥3, can have at most 2n?2 elements. We also show that a critically connected matroid of rank n on 2n?2 elements is isomorphic to the forest matroid of K₂, n?2.     

Derivations for a class of matrix function algebras

We study a class of matrix function algebras, here denoted T⁺(C_n). We introduce a notion of point derivations, and classify the point derivations for certain finite dimensional representations of T⁺(C_n). We use point derivations and information about n×n matrices to show that every T⁺(C_n)-valued derivation on T⁺(C_n) is inner.     

Algorithmic Folding Complexity

How do we most quickly fold a paper strip (modeled as a line) to obtain a desired mountain-valley pattern of equidistant creases (viewed as a binary string)? Define the folding complexity of a mountain-valley string as the minimum number of simple folds required to construct it. We first show that the folding complexity of a length-n uniform string (all mountains or all valleys), and hence of a length-n pleat (alternating mountain/valley), is O(lg² n). We also show that a lower bound of the complexity of the problems is ??(lg² n/lg lg n). Next we show that almost all mountain-valley patterns require ??(n/lg n) folds, which means that the uniform and pleat foldings are relatively easy problems. We also give a general algorithm for folding an arbitrary sequence of length n in O(n/lg n) folds, meeting the lower bound up to a constant factor.     

On the number of transversals in Cayley tables of cyclic groups

It is well known that if n is even, the addition table for the integers modulo n (which we denote by B_n) possesses no transversals. We show that if n is odd, then the number of transversals in B_n is at least exponential in n. Equivalently, for odd n, the number of diagonally cyclic latin squares of order n, the number of complete mappings or orthomorphisms of the cyclic group of order n, the number of magic juggling sequences of period n and the number of placements of n non-attacking semi-queens on an n×n toroidal chessboard are at least exponential in n. For all large n we show that there is a latin square of order n with at least (3.246)ⁿ transversals.We diagnose all possible sizes for the intersection of two transversals in B_n and use this result to complete the spectrum of possible sizes of homogeneous latin bitrades.We also briefly explore potential applications of our results in constructing random mutually orthogonal latin squares.     

Isomorphisms,automorphisms, and generalized involution models of projective reflection groups

We investigate the generalized involution models of the projective reflection groups G(r, p, q, n). This family of groups parametrizes all quotients of the complex reflection groups G(r, p, n) by scalar subgroups. Our classification is ultimately incomplete, but we provide several necessary and sufficient conditions for generalized involution models to exist in various cases. In the process we solve several intermediate problems concerning the structure of projective reflection groups. We derive a simple criterion for determining whether two groups G(r, p, q, n) and G(r, p′, q′, n) are isomorphic. We also describe explicitly the form of all automorphisms of G(r, p, q, n), outside a finite list of exceptional cases. Building on prior work, this allows us to prove that G(r, p, 1, n) has a generalized involution model if and only if G(r, p, 1, n) ≌ G(r, 1, p, n). We also classify which groups G(r, p, q, n) have generalized involution models when n = 2, or q is odd, or n is odd.     

Pseudospectra, critical points and multiple eigenvalues of matrix polynomials

We develop a general framework for perturbation analysis of matrix polynomials. More specifically, we show that the normed linear space L_m(C^n×n) of n-by-n matrix polynomials of degree at most m provides a natural framework for perturbation analysis of matrix polynomials in L_m(C^n×n). We present a family of natural norms on the space L_m(C^n×n) and show that the norms on the spaces C^m+1 and C^n×n play a crucial role in the perturbation analysis of matrix polynomials. We define pseudospectra of matrix polynomials in the general framework of the normed space L_m(C^n×n) and show that the pseudospectra of matrix polynomials well known in the literature follow as special cases. We analyze various properties of pseudospectra in the unified framework of the normed space L_m(C^n×n). We analyze critical points of backward errors of approximate eigenvalues of matrix polynomials and show that each critical point is a multiple eigenvalue of an appropriately perturbed polynomial. We show that common boundary points of components of pseudospectra of matrix polynomials are critical points. As a consequence, we show that a solution of Wilkinson’s problem for matrix polynomials can be read off from the pseudospectra of matrix polynomials.     

A construction of 2-designs from Steiner systems and extendable designs

We give a construction of a 2-(mn²+1,mn,(n+1)(mn−1)) design starting from a Steiner system S(2,m+1,mn²+1) and an affine plane of order n. This construction is applied to known classes of Steiner systems arising from affine and projective geometries, Denniston designs, and unitals. We also consider the extendability of these designs to 3-designs.     

Hadamard grade of power series

The Hadamard product of two power series ∑anzn and ∑bnzn is the power series ∑anbnzn. We define the (Hadamard) grade of a power series A to be the least number (finite or infinite) of algebraic power series, the Hadamard product of which equals A. We study and discuss this notion.     

Completion of a partial integral matrix to a unimodular matrix

We first characterize submatrices of a unimodular integral matrix. We then prove that if n entries of an n × n partial integral matrix are prescribed and these n entries do not constitute a row or a column, then this matrix can be completed to a unimodular matrix. Consequently an n × n partial integral matrix with n − 1 prescribed entries can always be completed to a unimodular matrix.