Equivalence systems with finitely many relations

We consider a setX with a finite totally ordered setE of equivalence relations onX. We describe the automorphism group of this system, that is, the group of all those permutations ofX that leave each relation inE invariant.     

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.     

Permutation codes with specified packing radius

Most papers on permutation codes have concentrated on the minimum Hamming distance of the code. An (n, d) permutation code (or permutation array) is simply a set of permutations on n elements in which the Hamming distance between any pair of distinct permutations (or codewords) is at least d. An (n, 2e + 1) or (n, 2e + 2) permutation code is able to correct up to e errors. These codes have a potential application to powerline communications. It is known that in an (n, 2e) permutation code the balls of radius e surrounding the codewords may all be pairwise disjoint, but usually some overlap. Thus an (n, 2e) permutation code is generally unable to correct e errors using nearest neighbour decoding. On the other hand, if the packing radius of the code is defined as the largest value of e for which the balls of radius e are all pairwise disjoint, a permutation code with packing radius e can be denoted by [n, e]. Such a permutation code can always correct e errors. In this paper it is shown that, in almost all cases considered, the number of codewords in the best [n, e] code found is substantially greater than the largest number of codewords in the best known (n, 2e + 1) code. Thus the packing radius more accurately specifies the requirement for an e-error-correcting permutation code than does the minimum Hamming distance. The techniques used include construction by automorphism group and several variations of clique search They are enhanced by two theoretical results which make the computations feasible.     

Bounds on permutation codes of distance four

A permutation code of length n and distance d is a set Γ of permutations from some fixed set of n symbols such that the Hamming distance between each distinct x,y∈Γ is at least d. In this note, we determine some new results on the maximum size of a permutation code with distance equal to 4, the smallest interesting value. The upper bound is improved for almost all n via an optimization problem on Young diagrams. A new recursive construction improves known lower bounds for small values of n.     

The radial part of Brownian motion II. Its life and times on the cut locus

Summary This paper is a sequel to Kendall (1987), which explained how the Itô formula for the radial part of Brownian motionX on a Riemannian manifold can be extended to hold for all time including those times a whichX visits the cut locus. This extension consists of the subtraction of a correction term, a continuous predictable non-decreasing processL which changes only whenX visits the cut locus. In this paper we derive a representation onL in terms of measures of local time ofX on the cut locus. In analytic terms we compute an expression for the singular part of the Laplacian of the Riemannian distance function. The work uses a relationship of the Riemannian distance function to convexity, first described by Wu (1979) and applied to radial parts of -martingales in Kendall (1993).The first author's research was supported by a visiting fellowship awarded by the UK Science and Engineering Council, by travel funds provided by a European Community SCIENCE initiative, by the Max-Planck-Institute of Bonn, and by a grant from NSA     

Non-baire unions in category bases

We consider a partition of a spaceX consisting of a meager subset ofX and obtain a sufficient condition for the existence of a subfamily of this partition which gives a non-Baire subset ofX. The condition is formulated in terms of the theory of J. Morgan [1].     

Minimal generalized permutations

In this paper, we obtain the number of the minimal generalized permutations on a finite set. Also, we determine the minimal generalized permutations on a setX of cardinality less than or equal to 4.     

Maximal sets of permutations constructed from projective planes

On the set of n²+n+1 points of a projective plane, a set of n²+n+1 permutations is constructed with the property that any two are a Hamming distance 2n+1 apart. Another set is constructed in which every pair are a Hamming distance not greater than 2n+1 apart. Both sets are maximal with respect to the stated property.     

Metrics on the set of semimartingale filtrations

Let X be a stochastic process with cadlag paths. We consider the set of all filtrations under which X is a semimartingale, and we define a distance between such filtrations with the help of the bounded variation parts in the corresponding decompositions of X. We show that this distance is a complete metric on the set of semimartingale filtrations if the given process X is continuous.     

The minimal cardinality where the Reznichenko property fails

A topological spaceX has the Fréchet-Urysohn property if for each subsetA ofX and each elementx inĀ, there exists a countable sequence of elements ofA which converges tox. Reznichenko introduced a natural generalization of this property, where the converging sequence of elements is replaced by a sequence of disjoint finite sets which eventually intersect each neighborhood ofx. In [5], Kočinac and Scheepers conjecture: The minimal cardinality of a setX of real numbers such thatC _p(X) does not have the weak Fréchet-Urysohn property is equal to b. (b is the minimal cardinality of an unbounded family in the Baire space^Nℕ.) We prove the Kočinac-Scheepers conjecture by showing that ifC _p(X) has the Reznichenko property, then a continuous image ofX cannot be a subbase for a non-feeble filter on ℕ. The author is partially supported by the Golda Meir Fund and the Edmund Landau Center for Research in Mathematical Analysis and Related Areas, sponsored by the Minerva Foundation (Germany).     

On the Hamming distance in combinatorial optimization problems on hypergraph matchings

In this note we consider the properties of the Hamming distance in combinatorial optimization problems on hypergraph matchings, also known as multidimensional assignment problems. It is shown that the Hamming distance between feasible solutions of hypergraph matching problems can be computed as an optimal value of linear assignment problem. For random hypergraph matching problems, an upper bound on the expected Hamming distance to the optimal solution is derived, and an exact expression is obtained in the special case of multidimensional assignment problems with 2 elements in each dimension.     

Measure-valued Markov branching processes conditioned on non-extinction

We consider a particular class of measure-valued Markov branching processes that are constructed as “superprocesses” over some underlying Markov process. Such a processX dies out almost surely, so we introduce various conditioning schemes which keepX alive at large times. Under suitable hypotheses, which include the convergence of the semigroup for the underlying process to some limiting probability measureν, we show that the conditional distribution oft ⁻¹ X _t converges to that ofZν ast → ∞, whereZ is some strictly positive, real random variable. Research supported in part by NSF grant DMS 8701212. Research supported in part by an NSERC operating grant.     

The Local Structure of a Bipartite Distance-regular Graph

In this paper, we consider a bipartite distance-regular graph Γ = (X, E) with diameter d ≥ 3. We investigate the local structure ofΓ , focusing on those vertices with distance at most 2 from a given vertex x. To do this, we consider a subalgebra R = R(x) ofMat_{0307a0x.gif X}(C), where 0307a1x.gifX denotes the set of vertices in X at distance 2 from x. R is generated by matrices Ã, 0307a2x.gif J, and 0307a3x.gif D defined as follows. For all y, z 0307a4x.gif X, the (y,z )-entry of à is 1 if y, z are at distance 2, and 0 otherwise. The (y, z)-entry of 0307a5x.gif J equals 1, and the (y,z )-entry of 0307a6x.gif D equals the number of vertices of X adjacent to each ofx , y, and z. We show that R is commutative and semisimple, with dimension at least 2. We assume that R is one of 2, 3, or 4, and explore the combinatorial implications of this. We are motivated by the fact that if Γ has a Q-polynomial structure, then R ≤ 4.     

Itô correction terms for the radial parts of semimartingales on manifolds

Summary We consider functions,F, of a semimartingale,X, on a complete manifold which fail to beC ² only on, and are sufficiently well-behaved near, a codimension 1 subset . We obtain an extension of the Itô formula which is valid for all time by adding a continuous predictable process given explicitly in terms of two geometric local times ofX on and the Gâteaux derivative ofF. We then examine the cut locus of a point of the manifold in sufficient detail to show that this result applies to give a corresponding expression for the radial part of the semimartingale.     

Binary relations as lattice isomorphisms

Summary In 1963, Zaretskiį established a one-to-one correspondence between the setB _X of binary relations on a set X and the set of triples of the form (W, ϕ, V) where W and V are certain lattices and ϕ: W→V is an isomorphism. We provide a multiplication for these triples making the Zaretskiį correspondence a semigroup isomorphism. In addition, we consider faithful representations ofB _X by pairs of partial transformations and also as the translational hull of its rectangular relations. Using these triples, we study idempotents, regular and completely regular elements and relationsH-equivalent to some relations with familiar properties such as reflexivity, transitivity, etc. Entrata in Redazione il 14 aprile 1998.     

Tight subgroups in torsion-free Abelian groups

LetX be a torsion-free abelian group. We study the class of all completely decomposable subgroups ofX which are maximal with respect to inclusion. These groups are called tight subgroups ofX and we state sufficient conditions on a subgroup to be tight. In particular we consider tight subgroups of bounded completely decomposable groups. For those we show that every regulating subgroup is tight and we characterize the tight subgroups of finite index in almost completely decomposable groups. The second author was supported by a MINERVA fellowship.     

On computing majority by comparisons

The elements of a finite setX (of odd cardinalityn) are divided into two (as yet unknown) classes and a member of the larger class is to be identified. The basic operation is to test whether two objects are in the same class. We show thatn-B(n) comparisons are necessary and sufficient in worst case, whereB(n) is the number of 1's in the binary expansion ofn.Supported in part by NSF grant DMS87 03541 and Air Force Office of Scientific Research grant AFOSR-0271.     

Partition and composition matrices

This paper introduces two matrix analogues for set partitions. A composition matrix on a finite set X is an upper triangular matrix whose entries partition X, and for which there are no rows or columns containing only empty sets. A partition matrix is a composition matrix in which an order is placed on where entries may appear relative to one-another.We show that partition matrices are in one-to-one correspondence with inversion tables. Non-decreasing inversion tables are shown to correspond to partition matrices with a row ordering relation. Partition matrices which are s-diagonal are classified in terms of inversion tables. Bidiagonal partition matrices are enumerated using the transfer-matrix method and are equinumerous with permutations which are sortable by two pop-stacks in parallel.We show that composition matrices on X are in one-to-one correspondence with (2+2)-free posets on X. Also, composition matrices whose rows satisfy a column-ordering relation are shown to be in one-to-one correspondence with parking functions. Finally, we show that pairs of ascent sequences and permutations are in one-to-one correspondence with (2+2)-free posets whose elements are the cycles of a permutation, and use this relation to give an expression for the number of (2+2)-free posets on {1,…,n}.     

Inference on superimposed subcritical Galton-Watson processes with immigration

Summary In this paper we consider the superimposed processZ generated by two independent subcritical Galton-Watson processesX ₁ andX ₂, with immigration, by the relationZ=X ₁ +X ₂. The seemingly second order autoregressive relation, that is identified inZ, is exploted towards proposing CAN estimators for the parameters ofZ,X ₁ andX ₂, based on only a partial realisation ofZ, using time series techniques. The results of this paper are motivated by a time series approach for studying specific branching processes due to Venkataraman (1982,Adv. Appl. Prob.,14, 1–20).     

Odd and even hamming spheres also have minimum boundary

Combinatorial problems with a geometric flavor arise if the set of all binary sequences of a fixed length n, is provided with the Hamming distance. The Hamming distance of any two binary sequences is the number of positions in which they differ. The (outer) boundary of a set A of binary sequences is the set of all sequences outside A that are at distance 1 from some sequence in A. Harper [6] proved that among all the sets of a prescribed volume, the ‘sphere’ has minimum boundary.We show that among all the sets in which no pair of sequences have distance 1, the set of all the sequences with an even (odd) number of 1's in a Hamming ‘sphere’ has the same minimizing property. Some related results are obtained. Sets with more general extremal properties of this kind yield good error-correcting codes for multi-terminal channels.