On the number of distinct block sizes in partitions of a set

The average number of distinct block sizes in a partition of a set of n elements is asymptotic to e log n as n → ∞. In addition, almost all partitions have approximately e log n distinct block sizes. This is in striking contrast to the fact that the average total number of blocks in a partition is ～n(log n)^?1 as n → ∞.     

Faster construction of optimal binary split trees

A binary split tree is a search structure combining features of heaps and binary search trees. Building an optimal binary split tree was originally conjectured to be intractable due to difficulties in applying dynamic programming techniques to the problem. However, two algorithms have recently been published which generate optimal trees in O(n⁵) time, for records with distinct access probabilities. An extension allowing nondistinct access probabilities required exponential time. These algorithms consider a range of values when only a single value is possible. A dynamic programming method for determining the correct value is given, resulting in an algorithm which builds an optimal binary split tree in O(n⁵) time for nondistinct access probabilities and Θ(n⁴) time for distinct access probabilities.     

The nucleus of a point determining graph

A graph is point determining if distinct points have distinct neighborhoods. In this paper we investigate the nucleus G⁰={υ?G:G–υ is point determining} of a point determining graph G. In particular, we characterize those graphs that are the nucleus of some connected point determining graph.     

Generalized inverses of certain Toeplitz matrices

The spectral inverse A^s of a Toeplitz matrix A whose form is related to that of a circulant matrix is studied by describing the algebraic structure of the semigroup of all matrices commuting with a given matrix with distinct eigenvalues. A computational form for A^s is given and necessary and sufficient conditions are found for A^s to be the Moore-Penrose generalized inverse A⁺.     

On 1-factors of point determining graphs

A graph G is said to be point determining if and only if distinct points of G have distinct neighborhoods. For such a graph G, the nucleus is defined to be the set G″ consisting of all points ν of G for which G-ν is a point determining graph.In [4], Summer exhibited several families of graphs H such that if G⁰ = H, for some point determining graph G, then G has a 1-factor. In this paper, we extend this class of graphs.     

Graph with given achromatic number

An irreducible (point-determining) graph is one in which distinct vertices have distinct neighbourhoods. Every graph X can be reduced to an irreducible graph X¹ by identifying all vertices with the same neighbourhood; the colourability properties of X¹ carry over to X. Hence irreducible graphs are instrumental in the study of achromatic number. We prove that there are only finitely many irreducible graphs with a given achromatic number, and describe all graphs with achromatic number less than four. We deduce certain bounds on the achromatic number X in terms of the number of vertices of X¹. In the course of the proofs we calculate the achromatic numbers of paths and cycles. Generalizations of the main theorem to homomorphisms other than colourings are discussed.     

Maximal number of distinct H-eigenpairs for a two-dimensional real tensor

Based on the generalized characteristic polynomial introduced by J. Canny in Generalized characteristic polynomials [J. Symbolic Comput., 1990, 9(3): 241–250], it is immediate that for any m-order n-dimensional real tensor, the number of distinct H-eigenvalues is less than or equal to n(m?1) ^n?1. However, there is no known bounds on the maximal number of distinct Heigenvectors in general. We prove that for any m ? 2, an m-order 2-dimensional tensor A exists such that A has 2(m ? 1) distinct H-eigenpairs. We give examples of 4-order 2-dimensional tensors with six distinct H-eigenvalues as well as six distinct H-eigenvectors. We demonstrate the structure of eigenpairs for a higher order tensor is far more complicated than that of a matrix. Furthermore, we introduce a new class of weakly symmetric tensors, called p-symmetric tensors, and show under certain conditions, p-symmetry will effectively reduce the maximal number of distinct H-eigenvectors for a given two-dimensional tensor. Lastly, we provide a complete classification of the H-eigenvectors of a given 4-order 2-dimensional nonnegative p-symmetric tensor. Additionally, we give sufficient conditions which prevent a given 4-order 2-dimensional nonnegative irreducible weakly symmetric tensor from possessing six pairwise distinct H-eigenvectors.     

The heterochromatic cycles in edge-colored graphs

Given a graph and an edge coloring C of G, a heterochromatic cycle of G is a cycle in which any pair of edges have distinct colors. Let d ^c (v), named the color degree of a vertex v, be the maximum number of distinct colored edges incident with v. In this paper, we give several sufficient conditions for the existence of heterochromatic cycles in edge-colored graphs.     

Proof of a conjecture on a discretized elliptic equation with cubic nonlinearity

We sharpen and prove a conjecture suggested by Chen and Xie, which states that in Galerkineigenfunction discretization for -Δu = u3 , when the finite-dimensional subspace is taken as the eigensubspace corresponding to an N-fold eigenvalue of -Δ, the discretized problem has at least 3N-1 distinct nonzero solutions. We also present a related result on the multiplicities of eigenvalues of -Δ.     

Essentially optimal computation of the inverse of generic polynomial matrices

We present an inversion algorithm for nonsingular n×n matrices whose entries are degree d polynomials over a field. The algorithm is deterministic and, when n is a power of two, requires O^∼(n³d) field operations for a generic input; the soft-O notation O^∼ indicates some missing log(nd) factors. Up to such logarithmic factors, this asymptotic complexity is of the same order as the number of distinct field elements necessary to represent the inverse matrix.     

On powers of certain lines

In this paper we answer questions of van Douwen and Pfeffer by showing that the spaces S, S², S³, and T, T², T³,... are topologically distinct, where S is the Sorgenfrey line and T is the set of irrational points in S. We obtain analogous results for the Michael line M and present related examples.     

Möbius homogeneous hypersurfaces with two distinct principal curvatures in S n+1

The purpose of this paper is to classify the Möbius homogeneous hypersurfaces with two distinct principal curvatures in S ⁿ⁺¹ under the Möbius transformation group. Additionally, we give a classification of the Möbius homogeneous hypersurfaces in S ⁴.     

A note on conjugacy classes of finite groups

Let G be a finite group and let x ^G denote the conjugacy class of an element x of G. We classify all finite groups G in the following three cases: (i) Each non-trivial conjugacy class of G together with the identity element 1 is a subgroup of G, (ii) union of any two distinct non-trivial conjugacy classes of G together with 1 is a subgroup of G, and (iii) union of any three distinct non-trivial conjugacy classes of G together with 1 is a subgroup of G.     

Exit time and invariant measure asymptotics for small noise constrained diffusions

Constrained diffusions, with diffusion matrix scaled by small ?>0, in a convex polyhedral cone G⊂R^k, are considered. Under suitable stability assumptions small noise asymptotic properties of invariant measures and exit times from domains are studied. Let B⊂G be a bounded domain. Under conditions, an “exponential leveling” property that says that, as ?→0, the moments of functionals of exit location from B, corresponding to distinct initial conditions, coalesce asymptotically at an exponential rate, is established. It is shown that, with appropriate conditions, difference of moments of a typical exit time functional with a sub-logarithmic growth, for distinct initial conditions in suitable compact subsets of B, is asymptotically bounded. Furthermore, as initial conditions approach 0 at a rate ?² these moments are shown to asymptotically coalesce at an exponential rate.     

The number of k-colorings of a graph on a fixed surface

We prove that, for every fixed surface S, there exists a largest positive constant c such that every 5-colorable graph with n vertices on S has at least c·2ⁿ distinct 5-colorings. This is best possible in the sense that, for each sufficiently large natural number n, there is a graph with n vertices on S that has precisely c·2ⁿ distinct 5-colorings. For the sphere the constant c is , and for each other surface, it is a finite problem to determine c. There is an analogous result for k-colorings for each natural number k>5.     

Color degree and alternating cycles in edge-colored graphs

Let G be an edge-colored graph. An alternating cycle of G is a cycle of G in which any two consecutive edges have distinct colors. Let d^c(v), the color degree of a vertex v, be defined as the maximum number of edges incident with v that have distinct colors. In this paper, we study color degree conditions for the existence of alternating cycles of prescribed length.     

On the nonnegative rank of Euclidean distance matrices

The Euclidean distance matrix for n distinct points in R^r is generically of rank r + 2. It is shown in this paper via a geometric argument that its nonnegative rank for the case r = 1 is generically n.     

Asymmetric multi-channel sampling in shift invariant spaces

We develop an asymmetric multi-channel sampling on a shift invariant space V(?) with a Riesz generator ?(t) in L²(R), where each channeled signal is assigned a uniform but distinct sampling rate. We use Fourier duality between V(?) and L²[0,2π] to find conditions under which there is a stable asymmetric multi-channel sampling formula on V(?).     

Classification of smooth structures on a homotopy complex projective space

We classify, up to diffeomorphism, all closed smooth manifolds homeomorphic to the complex projective n-space \(\mathbb {C}\textbf {P}^{n}\), where n=3 and 4. Let M²ⁿ be a closed smooth 2n-manifold homotopy equivalent to \(\mathbb {C}\textbf {P}^{n}\). We show that, up to diffeomorphism, M⁶ has a unique differentiable structure and M⁸ has at most two distinct differentiable structures. We also show that, up to concordance, there exist at least two distinct differentiable structures on a finite sheeted cover N²ⁿ of \(\mathbb {C}\textbf {P}^{n}\) for n=4,7 or 8 and six distinct differentiable structures on N¹⁰.     

Graphs with 1-Hamiltonian-connected cubes

The cube G³ of a connected graph G is that graph having the same vertex set as G and in which two distinct vertices are adjacent if and only if their distance in G is at most three. A Hamiltonian-connected graph has the property that every two distinct vertices are joined by a Hamiltonian path. A graph G is 1-Hamiltonian-connected if, for every vertex w of G, the graphs G and G?w are Hamiltonian-connected. A characterization of graphs whose cubes are 1-Hamiltonian-connected is presented.