On the completely positive and positive-semidefinite-preserving cones

The cone CP_n,q of completely positive linear transformations from $\text{M}{}_{\mathrm{n}}\text{(}\text{C}\text{)=}\text{M}{}_{\mathrm{n}}$ to $\text{M}$_q is shown to be isometrically isomorphic to $\text{P}$_nq, the cone of nq by nq positive semidefinite matrices. Generalizations of scalar and matrix results to $\text{CP}{}_{\mathrm{n,\; q}}\text{?}\text{HP}{}_{\mathrm{n,\; q}}\text{?}\text{L}\text{(}\text{M}{}_{\mathrm{n}}\text{,}\text{M}{}_{\mathrm{q}}\text{)}$ (where HP_n,q represents the hermitian-preserving linear transformations) are discussed. Relationships among the completely positives, the set of positive semidefinite preservers $\text{π(}\text{P}{}_{\mathrm{n}}\text{)}$, and its dual $\text{π(}\text{M}{}_{\mathrm{n}}\text{)}{}^1$ are given. Left and right facial ideals of CP are characterized. Properties of the joint angular field of values of a finite sequence of hermitian matrices H₁,…, H_m are studied, leading to a characterization of $\text{π(}\text{P}{}_{\mathrm{q}}\text{,}\text{P}{}_{\mathrm{n}}\text{)}$.     

Polytopes of partitions of numbers

We study the vertices and facets of the polytopes of partitions of numbers. The partition polytope P_n is the convex hull of the set of incidence vectors of all partitions n=x₁+2x₂++nx_n. We show that the sequence P₁,P₂,…,P_n,… can be treated as an embedded chain. The dynamics of behavior of the vertices of P_n, as n increases, is established. Some sufficient and some necessary conditions for a point of P_n to be its vertex are proved. Representation of the partition polytope as a polytope on a partial algebra—which is a generalization of the group polyhedron in the group theoretic approach to the integer linear programming—allows us to prove subadditive characterization of the nontrivial facets of P_n. These facets correspond to extreme rays of the cone of subadditive functions with additional requirements p₀=p_n and p_i+p_n−i=p_n,1≤i<n. The trivial facets are explicitly indicated. We also show how all vertices and facets of the polytopes of constrained partitions—in which some numbers are forbidden to participate—can be obtained from those of the polytope P_n. All vertices and facets of P_n for n≤8 and n≤6, respectively, are presented.     

Bipartite Distance-regular Graphs, Part I

Let Γ=(X,E) denote a bipartite distance-regular graph with diameter D≥4, and fix a vertex x of Γ. The Terwilliger algebra T=T(x) is the subalgebra of Mat _X(C) generated by A, E ^* ₀, E ^* ₁,…,E ^* _D, where A denotes the adjacency matrix for Γ and E ^* _i denotes the projection onto the i ^TH subconstituent of Γ with respect to x. An irreducible T-module W is said to be thin whenever dimE ^* _i W≤1 for 0≤i≤Di. The endpoint of W is min{i|E ^* _i W≠0}. We determine the structure of the (unique) irreducible T-module of endpoint 0 in terms of the intersection numbers of Γ. We show that up to isomorphism there is a unique irreducible T-module of endpoint 1 and it is thin. We determine its structure in terms of the intersection numbers of Γ. We determine the structure of each thin irreducible T-module W of endpoint 2 in terms of the intersection numbers of Γ and an additional real parameter ψ=ψ(W), which we refer to as the type of W. We now assume each irreducible T-module of endpoint 2 is thin and obtain the following two-fold result. First, we show that the intersection numbers of Γ are determined by the diameter D of Γ and the set of ordered pairs

Type-B generalized triangulations and determinantal ideals

For n≥3, let Ω_n be the set of line segments between the vertices of a convex n-gon. For j≥2, a j-crossing is a set of j line segments pairwise intersecting in the relative interior of the n-gon. For k≥1, let Δ_n,k be the simplicial complex of (type-A) generalized triangulations, i.e. the simplicial complex of subsets of Ω_n not containing any (k+1)-crossing.The complex Δ_n,k has been the central object of many papers. Here we continue this work by considering the complex of type-B generalized triangulations. For this we identify line segments in Ω_2n which can be transformed into each other by a 180^°-rotation of the 2n-gon. Let F_n be the set Ω_2n after identification, then the complex D_n,k of type-B generalized triangulations is the simplicial complex of subsets of F_n not containing any (k+1)-crossing in the above sense. For k=1, we have that D_n,1 is the simplicial complex of type-B triangulations of the 2n-gon as defined in [R. Simion, A type-B associahedron, Adv. Appl. Math. 30 (2003) 2-25] and decomposes into a join of an (n−1)-simplex and the boundary of the n-dimensional cyclohedron. We demonstrate that D_n,k is a pure, k(n−k)−1+kn dimensional complex that decomposes into a kn−1-simplex and a k(n−k)−1 dimensional homology-sphere. For k=n−2 we show that this homology-sphere is in fact the boundary of a cyclic polytope. We provide a lower and an upper bound for the number of maximal faces of D_n,k.On the algebraical side we give a term order on the monomials in the variables X_ij,1≤i,j≤n, such that the corresponding initial ideal of the determinantal ideal generated by the (k+1) times (k+1) minors of the generic n×n matrix contains the Stanley-Reisner ideal of D_n,k. We show that the minors form a Gröbner-Basis whenever k∈{1,n−2,n−1} thereby proving the equality of both ideals and the unimodality of the h-vector of the determinantal ideal in these cases. We conjecture this result to be true for all values of k<n.     

The Connected Monophonic Number of a Graph

For a connected graph G = (V, E) of order at least two, a chord of a path P is an edge joining two non-adjacent vertices of P. A path P is called a monophonic path if it is a chordless path. A set S of vertices of G is a monophonic set of G if each vertex v of G lies on an x ? y monophonic path for some elements x and y in S. The minimum cardinality of a monophonic set of G is defined as the monophonic number of G, denoted by m(G). A connected monophonic set of G is a monophonic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected monophonic set of G is the connected monophonic number of G and is denoted by m _c (G). We determine bounds for it and characterize graphs which realize these bounds. For any two vertices u and v in G, the monophonic distance d _m (u, v) from u to v is defined as the length of a longest u ? v monophonic path in G. The monophonic eccentricity e _m (v) of a vertex v in G is the maximum monophonic distance from v to a vertex of G. The monophonic radius rad _m G of G is the minimum monophonic eccentricity among the vertices of G, while the monophonic diameter diam _m G of G is the maximum monophonic eccentricity among the vertices of G. It is shown that for positive integers r, d and n ≥ 5 with r <  d, there exists a connected graph G with rad _m G =  r, diam _m G =  d and m _c (G) =  n. Also, if a,b and p are positive integers such that 2 ≤  a <  b ≤  p, then there exists a connected graph G of order p, m(G) =  a and m _c (G) =  b.     

An inequality for pseudo-subplanes of sets of orthogonal latin squares

Let L₁, L₂,…, L_t be a given set of t mutually orthogonal order-n latin squares defined on a symbol set S, |S| = n. The squares are equivalent to a (t + 2)-netN of order n which has n² points corresponding to the n² cells of the squares. A line of the net N defined by the latin square L_i comprises the n points of the net which are specified by a set of n cells of L_i all of which contain the same symbol x of S. If we pick out a particular r × r block B of cells, a line which contains points corresponding to r of the cells of B will be called an r-cell line. If there exist r(r ? 1) such lines among the tn lines of N, we shall say that they form a pseudo-subplane of order r-the “pseudo” means that these lines need not belong to only r ? 1 of the latin squares. The purpose of the present note is to prove that the hypothesis that such a pseudo-plane exists in N implies that $\text{r}{}^3\text{? (t + 2)r}{}^2\text{+ r + nt ?}{}^1\text{0}$.     

Approximation of analytic sets along Nash subvarieties

Let X be an analytic subset of pure dimension n of an open set U ⊂ C^m and let E be a Nash subset of U such that E ⊂ X.Then for every a ∈ E there is an open neighborhood V of a in U and a sequence {X_v} of complex Nash subsets of V of pure dimension n converging to X ∩ V in the sense of holomorphic chains such that the following hold for every v ∈ N: E ∩ V ⊂ X_v and the multiplicity of X_v at x equals the multiplicity of X at x for every x in a dense open subset of E ⊂ V.     

Results on the edge-connectivity of graphs

It is shown that if G is a graph of order p ≥ 2 such that deg u + deg v ≥ p ? 1 for all pairs u, v of nonadjacent vertices, then the edge-connectivity of G equals the minimum degree of G. Furthermore, if deg u + deg v ≥ p for all pairs u, v of nonadjacent vertices, then either p is even and G is isomorphic to $\text{K}{}_{\mathrm{<mtext>p</mtext><mtext>2</mtext>}}\text{× K}{}_2$ or every minimum cutset of edges of G consists of the collection of edges incident with a vertex of least degree.     

The stabilizer of immanants

Immanants are homogeneous polynomials of degree n in n² variables associated to the irreducible representations of the symmetric group S_n of n elements. We describe immanants as trivial S_n modules and show that any homogeneous polynomial of degree n on the space of n×n matrices preserved up to scalar by left and right action by diagonal matrices and conjugation by permutation matrices is a linear combination of immanants. Building on works of Duffner [5] and Purificação [3], we prove that for n?6 the identity component of the stabilizer of any immanant (except determinant, permanent, and π=(4,1,1,1)) is Δ(S_n)?T(GL_n×GL_n)?Z₂, where T(GL_n×GL_n) is the group consisting of pairs of n×n diagonal matrices with the product of determinants 1, acting by left and right matrix multiplication, Δ(S_n) is the diagonal of S_n×S_n, acting by conjugation (S_n is the group of symmetric group) and Z₂ acts by sending a matrix to its transpose. Based on the work of Purificação and Duffner [4], we also prove that for n?5 the stabilizer of the immanant of any non-symmetric partition (except determinant and permanent) is Δ(S_n)?T(GL_n×GL_n)?Z₂.     

The profile of the Cartesian product of graphs

Given a graph G, a proper labelingf of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile widthw_f(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labelingfofG, denoted by P_f(G), is the sum of all the w_f(v), where v∈V(G). The profile ofG is the minimum value of P_f(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Q_n. This can be used to determine the profile of Q_n and K_m×Q_n.     

Bounds in Polynomial Rings over Artinian Local Rings

Let R be a (mixed characteristic) Artinian local ring of length l and let X be an n-tuple of variables. We prove that several algebraic constructions in the ring R[X] admit uniform bounds on the degrees of their output in terms of l, n and the degrees of the input. For instance, if I is an ideal in R[X] generated by polynomials g _i of degree at most d and if f is a polynomial of degree at most d belonging to I, then f = q ₁ f ₁ + ··· + q _s f _s , for some q _i of degree bounded in terms of d, l and n only. Similarly, the module of syzygies of I is generated by tuples all of whose entries have degree bounded in terms of d, l and n only.     

Lie jets and symmetries of prolongations of geometric objects

The Lie jet L _θ λ of a field of geometric objects λ on a smooth manifold M with respect to a field θ of Weil A-velocities is a generalization of the Lie derivative L _v λ of a field λ with respect to a vector field v. In this paper, Lie jets L _θ λ are applied to the study of A-smooth diffeomorphisms on a Weil bundle T ^A M of a smooth manifold M, which are symmetries of prolongations of geometric objects from M to T ^A M. It is shown that vanishing of a Lie jet L _θ λ is a necessary and sufficient condition for the prolongation λ ^A of a field of geometric objects λ to be invariant with respect to the transformation of the Weil bundle T ^A M induced by the field θ. The case of symmetries of prolongations of fields of geometric objects to the second-order tangent bundle T ² M are considered in more detail.     

The ABC of hyper recursions

Each member of the family of Gauss hypergeometric functions

f_n=₂F₁(a+ε₁n,b+ε₂n;c+ε₃n;z),

An extended Kronecker product of matrices

Let $\text{A = (A}{}_1\text{¦ A}{}_2\text{¦ ··· ¦ A}{}_{\mathrm{r}}\text{)}\text{and}\text{B = (B}{}_1\text{¦ B}{}_2\text{¦ ··· ¦ B}{}_{\mathrm{r}}\text{)}$ be column-wise partitioned matrices over complex numbers. Then an extended Kronecker product is $\text{A ⊙ B = (A}{}_1\text{? B}{}_1\text{¦ ··· ¦ A}{}_{\mathrm{r}}\text{? B}{}_{\mathrm{r}}\text{)}$, where A_i ? B_i is the Kronecker product of A_i and B_i. Some properties of an extended Kronecker product of matrices are investigated. The properties of the solutions of the systems of linear equations whose coefficient matrices are extended Kronecker products of matrices are studied.     

On the vanishing of Selmer groups for elliptic curves over ring class fields

Let E/Q be an elliptic curve of conductor N without complex multiplication and let K be an imaginary quadratic field of discriminant D prime to N. Assume that the number of primes dividing N and inert in K is odd, and let Hc be the ring class field of K of conductor c prime to ND with Galois group Gc over K. Fix a complex character χ of Gc. Our main result is that if LK(E,χ,1)≠0 then Selp(E/Hc)χ_⊗W=0 for all but finitely many primes p, where Selp(E/Hc) is the p-Selmer group of E over Hc and W is a suitable finite extension of Zp containing the values of χ. Our work extends results of Bertolini and Darmon to almost all non-ordinary primes p and also offers alternative proofs of a χ-twisted version of the Birch and Swinnerton-Dyer conjecture for E over Hc (Bertolini and Darmon) and of the vanishing of Selp(E/K) for almost all p (Kolyvagin) in the case of analytic rank zero.     

Operators on the Lattice of Pseudovarieties of Finite Semigroups

L (F) of pseudovarieties of finite semigroups that attempts to take full advantage of the underlying lattice structure, Auinger, Hall and the present authors recently introduced fourteen complete congruences on L (F). Such congruences provide a framework from which to study L (F) both locally and globally. For each such congruence ρ and each U∈L (F) the ρ-class of U is an interval [U ^ρ, U _ρ]. This provides a family of operators of the form U⇒Uρ on L (F) that reveal important relationships between elements of L (F). Various aspects of these operators are considered including characterizations of U ^ρ, bases of pseudoidentities for U ^ρ, instances of commutativity (U ^ρ)^σ = U ^σ)^ρ, as well as the semigroups generated by certain pairs of such operators.     

Homology of balanced complexes via the Fourier transform

Let G ₀,…,G _k be finite abelian groups, and let G ₀∗⋯∗G _k be the join of the 0-dimensional complexes G _i . We give a characterization of the integral k-coboundaries of subcomplexes of G ₀∗⋯∗G _k in terms of the Fourier transform on the group G ₀×⋯×G _k . This provides a short proof of an extension of a recent result of Musiker and Reiner on a topological interpretation of the cyclotomic polynomial.     

Generating transformation semigroups using endomorphisms of preorders, graphs, and tolerances

Let Ω^Ω be the semigroup of all mappings of a countably infinite set Ω. If U and V are subsemigroups of Ω^Ω, then we write U≈V if there exists a finite subset F of Ω^Ω such that the subsemigroup generated by U and F equals that generated by V and F. The relative rank of U in Ω^Ω is the least cardinality of a subset A of Ω^Ω such that the union of U and A generates Ω^Ω. In this paper we study the notions of relative rank and the equivalence ≈ for semigroups of endomorphisms of binary relations on Ω.The semigroups of endomorphisms of preorders, bipartite graphs, and tolerances on Ω are shown to lie in two equivalence classes under ≈. Moreover such semigroups have relative rank 0, 1, 2, or d in Ω^Ω where d is the minimum cardinality of a dominating family for N^N. We give examples of preorders, bipartite graphs, and tolerances on Ω where the relative ranks of their endomorphism semigroups in Ω^Ω are 0, 1, 2, and d.We show that the endomorphism semigroups of graphs, in general, fall into at least four classes under ≈ and that there exist graphs where the relative rank of the endomorphism semigroup is 2^ℵ₀.     

Borel ideals vs. Borel sets of countable relations and trees

For every μ < ω₁, let I_μ be the ideal of all sets S ω^μ whose order type is <ω^μ. If μ = 1, then I₁ is simply the ideal of all finite subsets of ω, which is known to be Σ⁰₂-complete. We show that for every μ < ω₁, I_μ is Σ⁰_2μ-complete. As corollaries to this theorem, we prove that the set WO_ωμ of well orderings Rω × ω of order type <ω^μ is Σ⁰_2μ-complete, the set LP_μ of linear orderings R ω × ω that have a μ-limit point is Σ⁰_2μ+1-complete. Similarly, we determine the exact complexity of the set LT_μ of trees T ^<ωω of Luzin height <μ, the set WR_μ of well-founded partial orderings of height <μ, the set LR_μ of partial orderings of Luzin height <μ, the set WF_μ of well-founded trees T ^<ωω of height <μ(the latter is an old theorem of Luzin). The proofs use the notions of Wadge reducibility and Wadge games. We also present a short proof to a theorem of Luzin and Garland about the relation between the height of ‘the shortest tree’ representing a Borel set and the complexity of the set.