Harmonic morphisms from the classical non-compact semisimple Lie groups

We construct the first known complex-valued harmonic morphisms from the non-compact Lie groups SLn(R), SU^∗(2n) and Sp(n,R) equipped with their standard Riemannian metrics. We then introduce the notion of a bi-eigenfamily and employ this to construct the first known solutions on the non-compact Riemannian SO^∗(2n), SO(p,q), SU(p,q) and Sp(p,q). Applying a duality principle we then show how to manufacture the first known complex-valued harmonic morphisms from the compact Lie groups SO(n), SU(n) and Sp(n) equipped with semi-Riemannian metrics.     

Degenerate principal series representations and their holomorphic extensions

Let X=H/L be an irreducible real bounded symmetric domain realized as a real form in an Hermitian symmetric domain D=G/K. The intersection S of the Shilov boundary of D with X defines a distinguished subset of the topological boundary of X and is invariant under H. It can be realized as S=H/P for certain parabolic subgroup P of H. We study the spherical representations of H induced from P. We find formulas for the spherical functions in terms of the Macdonald hypergeometric function. This generalizes the earlier result of Faraut-Koranyi for Hermitian symmetric spaces D. We consider a class of H-invariant integral intertwining operators from the representations on L²(S) to the holomorphic representations of G restricted to H. We construct a new class of complementary series for the groups H=SO(n,m), SU(n,m) (with n−m>2) and Sp(n,m) (with n−m>1). We realize them as discrete components in the branching rule of the analytic continuation of the holomorphic discrete series of G=SU(n,m), SU(n,m)×SU(n,m) and SU(2n,2m) respectively.     

Hua operators and Poisson transform for bounded symmetric domains

Let Ω be a bounded symmetric domain of non-tube type in Cn with rank r and S its Shilov boundary. We consider the Poisson transform Psf(z) for a hyperfunction f on S defined by the Poisson kernel Ps(z,u)=s(h(z,z)^n/r/²|h(z,u)^n/r|), (z,u)×Ω×S, s∈C. For all s satisfying certain non-integral condition we find a necessary and sufficient condition for the functions in the image of the Poisson transform in terms of Hua operators. When Ω is the type I matrix domain in Mn,m(C) (n?m), we prove that an eigenvalue equation for the second order Mn,n-valued Hua operator characterizes the image.     

Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph

For a graph G in read-only memory on n vertices and m edges and a write-only output buffer, we give two algorithms using only O(n) rewritable space. The first algorithm lists all minimal a−b separators of G with a polynomial delay of O(nm). The second lists all minimal vertex separators of G with a cumulative polynomial delay of O(n³m).One consequence is that the algorithms can list the minimal a−b separators (and minimal vertex separators) spending O(nm) time (respectively, O(n³m) time) per object output.     

Mod 2 indecomposable orthogonal invariants

Over an algebraically closed base field k of characteristic 2, the ring R^G of invariants is studied, G being the orthogonal group O(n) or the special orthogonal group SO(n) and acting naturally on the coordinate ring R of the m-fold direct sum kⁿ⊕?⊕kⁿ of the standard vector representation. It is proved for O(n) (n?2) and for SO(n) (n?3) that there exist m-linear invariants with m arbitrarily large that are indecomposable (i.e., not expressible as polynomials in invariants of lower degree). In fact, they are explicitly constructed for all possible values of m. Indecomposability of corresponding invariants over immediately follows. The constructions rely on analysing the Pfaffian of the skew-symmetric matrix whose entries above the diagonal are the scalar products of the vector variables.     

Centroids,Representations, and Submodular Flows

The notion of centroid of a tree is generalized to apply to an arbitrary intersecting family of sets. Centroids are used to construct a compact representation for any intersecting family of sets, as well as any crossing family. The size of the representation for a family on n elements is O(n²), compared to size O(n³) for previous representations. Efficient algorithms to construct the representation are given. For example on a network of n vertices and m edges, the representation of all minimum cuts uses O(m log(n²/m)) space; it is constructed in O(nm log(n²/m)) time (this is the best-known time for finding one minimum cut). The representation is used to improve several submodular flow algorithms. For example a minimum-cost dijoin is found in time O(n²m); as a result a minimum-cost planar feedback are set is found in time O(n³). The previous best-known time bounds for these two problems are both a factor n larger.     

Harmonic morphisms from the classical compact semisimple Lie groups

In this article, we introduce a new method for manufacturing harmonic morphisms from semi-Riemannian manifolds. This is employed to yield a variety of new examples from the compact Lie groups SO(n), SU(n) and Sp(n) equipped with their standard Riemannian metrics. We develop a duality principle and show how this can be used to construct the first known examples of harmonic morphisms from the non-compact Lie groups , SU ^*(2n), , SO ^*(2n), SO(p, q), SU(p, q) and Sp(p, q) equipped with their standard dual semi-Riemannian metrics.      

Harmonic morphisms from the compact semisimple Lie groups and their non-compact duals

In this paper we prove the local existence of complex-valued harmonic morphisms from any compact semisimple Lie group and their non-compact duals. These include all Riemannian symmetric spaces of types II and IV. We produce a variety of concrete harmonic morphisms from the classical compact simple Lie groups SO(n), SU(n), Sp(n) and globally defined solutions on their non-compact duals SO(n,C)/SO(n), SLn(C)/SU(n) and Sp(n,C)/Sp(n).     

Smoothness of convolution powers of orbital measures on the symmetric space SU(n)/SO(n)

We prove that if m_a = m_K*d_a*m_K{\mu _{a}\,{=}\,m_{K}*\delta _{a}*m_{K}} is the K-bi-invariant measure supported on the double coset KaK í SU(n){KaK\subseteq SU(n)} , for K = SO(n), then m_a^k{\mu _{a}^{k}} is absolutely continuous with respect to the Haar measure on SU(n) for all a not in the normalizer of K if and only if k ≥ n. The measure, μ _a , supported on the minimal dimension double coset has the property that m_a^n-1{\mu _{a}^{n-1}} is singular to the Haar measure.     

Discrete components of some complementary series representations

We show that the restriction of the complementary series representations of SO(n, 1) to SO(m, 1) (m < n) contains complementary series representations of SO(m, 1) discretely, provided that the continuous parameter is sufficiently close to the first point of reducibility and the representation of M — the compact part of the Levi- is a sufficiently small fundamental representation.     

Generating 3-vertex connected spanning subgraphs

In this paper we present an algorithm to generate all minimal 3-vertex connected spanning subgraphs of an undirected graph with n vertices and m edges in incremental polynomial time, i.e., for every K we can generate K (or all) minimal 3-vertex connected spanning subgraphs of a given graph in O(K²log(K)m²+K²m³) time, where n and m are the number of vertices and edges of the input graph, respectively. This is an improvement over what was previously available and is the same as the best known running time for generating 2-vertex connected spanning subgraphs. Our result is obtained by applying the decomposition theory of 2-vertex connected graphs to the graphs obtained from minimal 3-vertex connected graphs by removing a single edge.     

Fuzzy complex Grassmannians and quantization of line bundles

We construct by purely representation-theoretic methods fuzzy versions of an arbitrary complex Grassmannian M=Gr _n (ℂ ^n+m ), i.e., a sequence of matrix algebras tending SU(n+m)-equivariantly to the algebra of smooth functions on M. We also show that this approximation can be interpreted in terms of the Berezin-Toeplitz quantization of M. Furthermore, we use branching rules to prove that the quantization of every complex line bundle over M is given by a SU(n+m)-equivariant truncation of the space of its L ²-sections.     

Degenerate orbits of adjoint representation of orthogonal and unitary groups regarded as algebraic submanifolds

We suggest a method for describing some types of degenerate orbits of orthogonal and unitary groups in the corresponding Lie algebras as level surfaces of a special collection of polynomial functions. This method allows one to describe orbits of the types SO(2n)/SO(2k)×SO(2) ^n?k , SO(2n+1)/SO(2k+1)×SO(2) ^n?k , and (S)U(n)/(S)(U(2k)×U(2) ^n?k ) in so(2n), so(2n+1), and (s)u(n), respectively. In addition, we show that the orbits of minimal dimensions of the groups under consideration can be described in the corresponding algebras as intersections of quadries. In particular, this approach is used for describing the orbit CP ^n?1?u(n).     

A twisted factorization method for symmetric SVD of a complex symmetric tridiagonal matrix

This paper presents an O(n²) method based on the twisted factorization for computing the Takagi vectors of an n‐by‐n complex symmetric tridiagonal matrix with known singular values. Since the singular values can be obtained in O(n²) flops, the total cost of symmetric singular value decomposition or the Takagi factorization is O(n²) flops. An analysis shows the accuracy and orthogonality of Takagi vectors. Also, techniques for a practical implementation of our method are proposed. Our preliminary numerical experiments have verified our analysis and demonstrated that the twisted factorization method is much more efficient than the implicit QR method, divide‐and‐conquer method and Matlab singular value decomposition subroutine with comparable accuracy. Copyright © 2009 John Wiley & Sons, Ltd.     

Sharp Nash inequalities on the unit sphere: The influence of symmetries

In this paper both we establish the best constants for the Nash inequalities on the standard unit sphere Sⁿ of Rⁿ⁺¹, n≥3 and we give answers on the existence of extremal functions on the corresponding problems. Also we study the problem of the best constants in the case where the data are invariant under the action of the group G=O(k)×O(m), k+m=n+1 and we find the best constants.     

Projective pseudodifferential analysis and harmonic analysis

We consider pseudodifferential operators on functions on Rn+1 which commute with the Euler operator, and can thus be restricted to spaces of functions homogeneous of some given degree. The symbols of such restrictions can be regarded as functions on a reduced phase space, isomorphic to the homogeneous space Gn/Hn=SL(n+1,R)/GL(n,R), and the resulting calculus is a pseudodifferential analysis of operators acting on spaces of appropriate sections of line bundles over the projective space Pn(R): these spaces are the representation spaces of the maximal degenerate series (πiλ,ε) of Gn. This new approach to the quantization of Gn/Hn, already considered by other authors, has several advantages: as an example, it makes it possible to give a very explicit version of the continuous part from the decomposition of L²(Gn/Hn) under the quasiregular action of Gn. We also consider interesting special symbols, which arise from the consideration of the resolvents of certain infinitesimal operators of the representation πiλ,ε.     

The Euclidean Bottleneck Steiner Path Problem and Other Applications of (α,β)-Pair Decomposition

We consider a geometric optimization problem that arises in network design. Given a set P of n points in the plane, source and destination points s, t∈P, and an integer k>0, one has to locate k Steiner points, such that the length of the longest edge of a bottleneck path between s and t is minimized. In this paper, we present an O(nlog² n)-time algorithm that computes an optimal solution, for any constant k. This problem was previously studied by Hou et al. (in Wireless Networks 16, 1033–1043, 2010), who gave an O(n ²logn)-time algorithm. We also study the dual version of the problem, where a value λ>0 is given (instead of k), and the goal is to locate as few Steiner points as possible, so that the length of the longest edge of a bottleneck path between s and t is at most λ. Our algorithms are based on two new geometric structures that we develop—an (α,β)-pair decomposition of P and a floor (1+ε)-spanner of P. For real numbers β>α>0, an (α,β)-pair decomposition of P is a collection $\mathcal{W}=\{(A_{1},B_{1}),\ldots,(A_{m},B_{m})\}$ of pairs of subsets of P, satisfying the following: (i) For each pair $(A_{i},B_{i}) \in\mathcal {W}$ , both minimum enclosing circles of A _i and B _i have a radius at most α, and (ii) for any p, q∈P, such that |pq|≤β, there exists a single pair $(A_{i},B_{i}) \in\mathcal{W}$ , such that p∈A _i and q∈B _i , or vice versa. We construct (a compact representation of) an (α,β)-pair decomposition of P in time O((β/α)³ nlogn). In some applications, a simpler (though weaker) grid-based version of an (α,β)-pair decomposition of P is sufficient. We call this version a weak (α,β)-pair decomposition of P. For ε>0, a floor (1+ε)-spanner of P is a (1+ε)-spanner of the complete graph over P with weight function w(p,q)=?|pq|?. We construct such a spanner with O(n/ε ²) edges in time O((1/ε ²)nlog² n), even though w is not a metric. Finally, we present two additional applications of an (α,β)-pair decomposition of P. In the first, we construct a strong spanner of the unit disk graph of P, with the additional property that the spanning paths also approximate the number of substantial hops, i.e., hops of length greater than a given threshold. In the second application, we present an O((1/ε ²)nlogn)-time algorithm for computing a one-sided approximation for distance selection (i.e., given k, $1 \le k \le{n \choose2}$ , find the k’th smallest Euclidean distance induced by P), significantly improving the running time of the algorithm of Bespamyatnikh and Segal.     

New exact solitary-wave special solutions for the nonlinear dispersive K(m, n) equations

In this paper, we study the nonlinear dispersive K(m, n) equations: u_t + (u^m)_x − (uⁿ)_xxx = 0 which exhibit solutions with solitary patterns. New exact solitary solutions are found. The two special cases, K(2, 2) and K(3, 3), are chosen to illustrate the concrete features of the decomposition method in K(m, n) equations. The nonlinear equations K(m, n) are studied for two different cases, namely when m = n being odd and even integers. General formulas for the solutions of K(m, n) equations are established.