Routing through a generalized switchbox

We present an algorithm for the routing problem for two-terminal nets in generalized switchboxes. A generalized switchbox is any subset R of the planar rectangular grid with no nontrivial holes, i.e., every finite face has exactly four incident vertices. A net is a pair of nodes of nonmaximal degree on the boundary of R. A solution is a set of edge-disjoint paths, one for each net. Our algorithm solves standard generalized switchbox routing problems in time O(n(log n)²) where n is the number of vertices of R, i.e., it either finds a solution or indicates that there is none. A problem is standard if deg(ν) + ter(ν) is even for all vertices ν where deg(ν) is the degree of ν and ter(ν) is the number of nets which have ν as a terminal. For nonstandard problems we can find a solution in time O(n(log n)² + |U|²) where U is the set of vertices ν with deg(ν) + ter(ν) is odd.     

ν-perfect groups

Let F_∞ be a free group on a countable set {x₁, x₂, …} and ν be a variety of groups, defined by the set of outer commutators V, in the free generators x_i's.The paper is devoted to give the complete structure of a ν-covering of ν-perfect groups. Fur thermore necessary and sufficient conditions for the universality of a ν-central extension by a group and its ν-covering group will be presented.     

Banach function subspaces of L of a vector measure and related Orlicz spaces

Given a vector measure ν with values in a Banach space X, we consider the space L¹(ν) of real functions which are integrable with respect to ν. We prove that every order continuous Banach function space Y continuously contained in L¹(ν) is generated via a certain positive map related to ν and defined on X* x M, where X* is the dual space of X and M the space of measurable functions. This procedure provides a way of defining Orlicz spaces with respect to the vector measure ν.     

The Existence of Partitioned Generalized Balanced Tournament Designs with Block Size 3

A generalized balanced tournament design, GBTD(n, k), defined on a kn-set V, is an arrangement of the blocks of a (kn, k, k – 1)-BIBD defined on V into an n × (kn – 1) array such that (1) every element of V is contained in precisely one cell of each column, and (2) every element of V is contained in at most k cells of each row. Suppose we can partition the columns of a GBTD(n, k) into k + 1 sets B1, B2,..., Bk + 1 where |Bi| = n for i = 1, 2,..., k – 2, |Bi| = n–1 for i = k – 1, k and |Bk+1| = 1 such that (1) every element of V occurs precisely once in each row and column of Bi for i = 1, 2,..., k – 2, and (2) every element of V occurs precisely once in each row and column of Bi Bk+1 for i = k – 1 and i = k. Then the GBTD(n, k) is called partitioned and we denote the design by PGBTD(n, k). The spectrum of GBTD(n, 3) has been completely determined. In this paper, we determine the spectrum of PGBTD(n,3) with, at present, a fairly small number of exceptions for n. This result is then used to establish the existence of a class of Kirkman squares in diagonal form.     

Approximation of Densities of Absolutely Continuous Components of Measures in a Hilbert Space Using the Ornstein-Uhlenbeck Semigroup

We study the behavior of measures obtained as a result of the action of the Ornstein-Uhlenbeck semigroup T _t associated with the Gaussian measure μ on an arbitrary probability measure ν in a separable Hilbert space as t → 0+. We prove that the densities of the parts of T _t ν absolutely continuous with respect to μ converge in the measure μ to the density of the part of ν absolutely continuous with respect to μ. For a finite-dimensional space, we prove the convergence of these densities μ-almost everywhere. In the infinite-dimensional case, we give sufficient conditions for almost-everywhere convergence. We also consider conditions on the absolute continuity of T _t ν with respect to μ in terms of the coefficients of the expansion of T _t ν in a series in Hermite polynomials (an analog of the Ito- Wiener expansion) and the connection with finite absolute continuity.__________Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 56, No. 12, pp. 1654 – 1664, December, 2004.     

Realizations of coupled vectors in the tensor product of representations of and

Using the realization of positive discrete series representations of in terms of a complex variable z, we give an explicit expression for coupled basis vectors in the tensor product of ν+1 representations as polynomials in ν+1 variables z₁,…,z_ν+1. These expressions use the terminology of binary coupling trees (describing the coupled basis vectors), and are explicit in the sense that there is no reference to the Clebsch–Gordan coefficients of . In general, these polynomials can be written as (terminating) multiple hypergeometric series. For ν=2, these polynomials are triple hypergeometric series, and a relation between the two binary coupling trees yields a relation between two triple hypergeometric series. The case of is discussed next. Also here the polynomials are determined explicitly in terms of a known realization; they yield an efficient way of computing coupled basis vectors in terms of uncoupled basis vectors.     

Weak Limits for Multivariate Random Sums

Let {Xi, i1} be a sequence of i.i.d. random vectors inRd, and letνp, 0<p<1, be a positive, integer valued random variable, independent ofXis. Theν-stable distributions are the weak limits of properly normalized random sums ∑νpi=1 Xiasνp ∞ andpνp ν. We study the properties ofν-stable laws through their representation via stable laws. In particular, we estimate their tail probabilities and provide conditions for finiteness of their moments.     

Orthogonal graphs of odd characteristic and their automorphisms

The (isotropic) orthogonal graph O(2ν+δ,q) over of odd characteristic, where ν1 and δ=0,1 or 2 is introduced. When ν=1, O(21+δ,q) is a complete graph. When ν2, O(2ν+δ,q) is strongly regular and its parameters are computed, as well as its chromatic number. The automorphism groups of orthogonal graphs are also determined.     

Borel Measure Extensions of Measures Defined on Sub-σ-Algebras

We develop a new approach to the measure extension problem, based on nonstandard analysis. The class of thick topological spaces, which includes all locally compact and all K-analytic spaces, is introduced in this paper, and measure extension results of the following type are obtained: If (X,  ) is a regular, Lindelöf, and thick space, σ[ ] is a σ-algebra, and ν is a finite measure on , inner regular with respect to the closed sets in , then ν has a Radon extension. The methods developed here allow us to improve on previously known extension results.     

Phase transition for dielectric breakdown model

In this paper, the phase transition for DBM when ν varies is investigated by using real-space renormalization-group method. The result demonstrates that there are phase transitions for almost all the value of ν, and we find a new result that the larger ν is, the larger the value of phase transition point q_c is.     

Quadrature formulae connected to σ-orthogonal polynomials

Let dλ(t) be a given nonnegative measure on the real line , with compact or infinite support, for which all moments exist and are finite, and μ₀>0. Quadrature formulas of Chakalov–Popoviciu type with multiple nodes

where σ=σ_n=(s₁,s₂,…,s_n) is a given sequence of nonnegative integers, are considered. A such quadrature formula has maximum degree of exactness d_max=2∑_ν=1ⁿs_ν+2n−1 if and only if

The proof of the uniqueness of the extremal nodes τ₁,τ₂,…,τ_n was given first by Ghizzetti and Ossicini (Rend. Mat. 6(8) (1975) 1–15). Here, an alternative simple proof of the existence and the uniqueness of such quadrature formulas is presented. In a study of the error term R(f), an influence function is introduced, its relevant properties are investigated, and in certain classes of functions the error estimate is given. A numerically stable iterative procedure, with quadratic convergence, for determining the nodes τ_ν, ν=1,2,…,n, which are the zeros of the corresponding σ-orthogonal polynomial, is presented. Finally, in order to show a numerical efficiency of the proposed procedure, a few numerical examples are included.     

Some Properties of Nonstar Steps in Addition Chains and New Cases Where the Scholz Conjecture Is True

Let ℓ(n) be the smallest possible length of addition chains for a positive integer n. Then Scholz conjectured that ℓ(2ⁿ − 1) ≤ n + ℓ(n) − 1, which still remains open. It is known that the Scholz conjecture is true when ν(n) ≤ 4, where ν(n) is the number of 1's in the binary representation of n. In this paper, we give some properties of nonstar steps in addition chains and prove that the Scholz conjecture is true for infinitely many new integers including the case where ν(n) = 5.     

Advanced topology on the multiscale sequence spaces

We pursue the study of the multiscale spaces S^ν introduced by Jaffard in the context of multifractal analysis. We give the necessary and sufficient condition for S^ν to be locally p-convex, and exhibit a sequence of p-norms that defines its natural topology. The strong topological dual of S^ν is identified to another sequence space depending on ν, endowed with an inductive limit topology. As a particular case, we describe the dual of a countable intersection of Besov spaces.     

An adaptive algorithm for system level diagnosis

Consider a system of n units, at most t of which are faulty. An adaptive diagnosis algorithm is presented which uses a sequence of tests to identify a fault-free unit. The algorithm requires at most 2t − ν(t) tests, where ν(t) is the number of 1's in the binary representation of t. Moreover, many of the tests can be performed simultaneously. The previously best algorithms for the same purpose required 2t − 1 tests, none of which could be performed simultaneously.     

Decomposably non-negative matrices

Let A be an mn- by - mn symmetric matrix. Partition A into m²n - by - n blocks and suppose that each of these blocks is also symmetric. Suppose that for every decomposable (rank one) tensor ν ⊗ w, we have (ν ⊗ w)^t A(ν otimes; w) ≥ 0. Here, ν is a column m-tuple and w is a column n-tuple. We study the maximum number of negative eigenvalues such a matrix can have, as well as obtaining alternative characterizations of such matrices.     

Geometric interpretations of two branching theorems of D.E. Littlewood

D.E. Littlewood proved two branching theorems for decomposing the restriction of an irreducible finite-dimensional representation of a unitary group to a symmetric subgroup. One is for restriction of a representation of U(n) to the rotation group SO(n) when the given representation τ_λ of U(n) has nonnegative highest weight λ of depth n/2. It says that the multiplicity in τ_λ|_SO(n) of an irreducible representation of SO(n) of highest weight ν is the sum over μ of the multiplicities of τ_λ in the U(n) tensor product τ_μτ_ν, the allowable μ's being all even nonnegative highest weights for U(n). Littlewood's proof is character-theoretic. The present paper gives a geometric interpretation of this theorem involving the tensor products τ_μτ_ν explicitly. The geometric interpretation has an application to the construction of small infinite-dimensional unitary representations of indefinite orthogonal groups and, for each of these representations, to the determination of its restriction to a maximal compact subgroup. The other Littlewood branching theorem is for restriction from U(2r) to the rank-r quaternion unitary group Sp(r). It concerns nonnegative highest weights for U(2r) of depth r, and its statement is of the same general kind. The present paper finds an analogous geometric interpretation for this theorem also.     

On the structure of semi-invariant polynomials in Ore extensions

Let D be an X-outer S-derivation of a prime ring R, where S is an automorphism of R. The following is proved among other things: The degree of the minimal semi-invariant polynomial of the Ore extension R[X;S,D] is ν if charR=0, and is p^kν for some k0 if charR=p2, where ν is the least integer ν1 such that S^νDS^−ν−D is X-inner. A similar result holds for cv-polynomials. These are done by introducing the new notion of k-basic polynomials for each integer k0, which enable us to analyze semi-invariant polynomials inductively.     

Degree‐ and Orbit‐Balanced Γ‐Designs When Γ Has Five Vertices

A Γ‐design of the complete graph is a set of subgraphs isomorphic to Γ (blocks) whose edge‐sets partition the edge‐set of . is balanced if the number of blocks containing x is the same number of blocks containing y for any two vertices x and y. is orbit‐balanced, or strongly balanced, if the number of blocks containing x as a vertex of a vertex‐orbit A of Γ is the same number of blocks containing y as a vertex of A, for any two vertices x and y and for every vertex‐orbit A of Γ. We say that is degree‐balanced if the number of blocks containing x as a vertex of degree d in Γ is the same number of blocks containing y as a vertex of degree d in Γ, for any two vertices x and y and for every degree d in Γ. An orbit‐balanced Γ‐design is also degree‐balanced; a degree‐balanced Γ‐design is also balanced. The converse is not always true. We study the spectrum for orbit‐balanced, degree‐balanced, and balanced Γ‐designs of when Γ is a graph with five vertices, none of which is isolated. We also study the existence of balanced (respectively, degree‐balanced) Γ‐designs of which are not degree‐balanced (respectively, not orbit‐balanced).     

q-Bessel, arbres, et chemins valués

We give interpretations for quotient J_ν+1/J_ν of q-Bessel functions. These q-analogs are related to generating function of weighted complete binary trees according to the number of leaves and to multichains on a partially ordered set, corresponding to weighted paths in the plane.Nous donnons des interprétations combinatoires du rapport J_ν+1/J_ν de q-fonctions de Bessel. Ces q-analogues énumèrent des classes d'arbres binaires complets valués suivant le nombre de feuilles et des multichaînes d'un ensemble partiellement ordonné, correspondant à des chemins valués dans le plan.     

Analysis of Carry Propagation in Addition: An Elementary Approach

Our goal in this paper is to analyze carry propagation in addition using only elementary methods (that is, those not involving residues, contour integration, or methods of complex analysis). Our results concern the length of the longest carry chain when two independent uniformly distributed n-bit numbers are added. First, we show using just first- and second-moment arguments that the expected length C_n of the longest carry chain satisfies C_n = log₂n + O(1). Second, we use a sieve (inclusion–exclusion) argument to give an exact formula for C_n. Third, we give an elementary derivation of an asymptotic formula due to Knuth, C_n = log₂n + Φ(log₂ n) + O((logn)⁴/n), where Φ(ν) is a bounded periodic function of ν, with period 1, for which we give both a simple integral expression and a Fourier series. Fourth, we give an analogous asymptotic formula for the variance V_n of the length of the longest carry chain: V_n = Ψ(log₂ n) + O((logn)⁵/n), where Ψ(ν) is another bounded periodic function of ν, with period 1. Our approach can be adapted to addition with the “end-around” carry that occurs in the sign-magnitude and 1s-complement representations. Finally, our approach can be adapted to give elementary derivations of some asymptotic formulas arising in connection with radix-exchange sorting and collision-resolution algorithms, which have previously been derived using contour integration and residues.