Eigenvalue estimates for Schrödinger operators on metric trees

We consider Schrödinger operators on radial metric trees and prove Lieb–Thirring and Cwikel–Lieb–Rozenblum inequalities for their negative eigenvalues. The validity of these inequalities depends on the volume growth of the tree. We show that the bounds are valid in the endpoint case and reflect the correct order in the weak or strong coupling limit.     

A phase transition for the heights of a fragmentation tree

We provide information about the asymptotic regimes for a homogeneous fragmentation of a finite set. We establish a phase transition for the asymptotic behavior of the shattering times, defined as the first instants when all the blocks of the partition process have cardinality less than a fixed integer. Our results may be applied to the study of certain random split trees. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 247‐274, 2011     

An improved partial SPIHT with classified weighted rate-distortion optimization for interferential multispectral image compression

Based on the property analysis of interferential multispectral images, a novel compression algorithm of partial set partitioning in hierarchical trees (SPIHT) with classified weighted rate-distortion optimization is presented.After wavelet decomposition, partial SPIHT is applied to each zero tree independently by adaptively selecting one of three coding modes according to the probability of the significant coefficients in each bitplane.Meanwhile the interferential multispectral image is partitioned into two kinds of regions in terms of luminous intensity, and the rate-distortion slopes of zero trees are then lifted with classified weights according to their distortion contribution to the constructed spectrum.Finally a global ratedistortion optimization truncation is performed.Compared with the conventional methods, the proposed algorithm not only improves the performance in spatial domain but also reduces the distortion in spectral domain.     

A Polynomial Time Approximation Scheme for the Grade of Service Steiner Minimum Tree Problem

In this paper, we present the design of a Polynomial Time Approximation Scheme (PTAS) for the Grade of Service Steiner Minimum Tree (GOSST) problem, which is known to be NP-Complete. Previous research has focused on geometric analyses and different approximation algorithms have been designed. We propose a PTAS that provides a polynomial time, near-optimal solution with performance ratio 1+. The GOSST problem has some important applications. In network design, a fundamental issue for the physical construction of a network structure is the interconnection of many communication sites with the best choice of the connecting lines and the best allocation of the transmission capacities over these lines. Good solutions should provide paths with enough communication capacities between any two sites, with the least network construction costs. Also, the GOSST problem has applications in transportation, for road constructions and some potential uses in CAD in terms of interconnecting the elements on a plane to provide enough flux between any two elements.     

A Basis for the Top Homology of a Generalized Partition Lattice

For a fixed positive integer k, consider the collection of all affine hyperplanes in n-space given by xi – xj = m, where i, j [n], i j, and m {0, 1,..., k}. Let Ln,k be the set of all nonempty affine subspaces (including the empty space) which can be obtained by intersecting some subset of these affine hyperplanes. Now give Ln,k a lattice structure by ordering its elements by reverse inclusion. The symmetric group Gn acts naturally on Ln,k by permuting the coordinates of the space, and this action extends to an action on the top homology of Ln,k. It is easy to show by computing the character of this action that the top homology is isomorphic as an Gn-module to a direct sum of copies of the regular representation, CGn. In this paper, we construct an explicit basis for the top homology of Ln,k, where the basis elements are indexed by all labelled, rooted, (k + 1)-ary trees on n-vertices in which the root has no 0-child. This construction gives an explicit Gn-equivariant isomorphism between the top homology of Ln,k and a direct sum of copies of CGn.     

The boson gas on a Cayley tree

We analyze the free boson gas on a Cayley tree using two alternative methods. The spectrum of the lattice Laplacian on a finite tree is obtained using a direct iterative method for solving the associated characteristic equation and also using a random walk representation for the corresponding fermion lattice gas. The existence of the thermodynamic limit for the pressure of the boson lattice gas is proven and it is shown that the model exhibits boson condensation into the ground state. The random walk representation is also used to derive an expression for the Bethe approximation to the infinite-volume spectrum. This spectrum turns out to be continuous instead of a dense point spectrum, but there is still boson condensation in this approximation.     

Almost sure quasilocality fails for the random-cluster model on a tree

We study the random-cluster model on a homogeneous tree, and show that the following three conditions are equivalent for a random-cluster measure: quasilocality, almost sure quasilocality, and the almost sure nonexistence of infinite clusters. As a consequence of this, we find that the plus measure for the Ising model on a tree at sufficiently low temperatures can be mapped, via a local stochastic transformation, into a measure which fails to be almost surely quasilocal.     

Spanning network games

We study fundamental properties of monotone network enterprises which contain public vertices and have positive and negative costs on edges and vertices. Among the properties studied are the nonemptiness of the core, characterization of nonredundant core constraints, ease of computation of the core and the nucleolus, and cases of decomposition of the core and the nucleolus. Received December 1994/Final version March 1998     

A composition law for Runge-Kutta methods applied to index-2 differential-algebraic equations

This paper presents a new composition law for Runge-Kutta methods when applied to index-2 differential-algebraic systems. Applications of this result to the study of the order of composite methods and of symmetric methods are given.     

Spectra of Some Interesting Combinatorial Matrices Related to Oriented Spanning Trees on a Directed Graph

The Laplacian of a directed graph G is the matrix L(G) = O(G) –, A(G) where A(G) is the adjaceney matrix of G and O(G) the diagonal matrix of vertex outdegrees. The eigenvalues of G are the eigenvalues of A(G). Given a directed graph G we construct a derived directed graph D(G) whose vertices are the oriented spanning trees of G. Using a counting argument, we describe the eigenvalues of D(G) and their multiplicities in terms of the eigenvalues of the induced subgraphs and the Laplacian matrix of G. Finally we compute the eigenvalues of D(G) for some specific directed graphs G. A recent conjecture of Propp for D(H _n ) follows, where H _n stands for the complete directed graph on n vertices without loops.