Packing Steiner trees: polyhedral investigations

LetG=(V, E) be a graph andT⊆V be a node set. We call an edge setS a Steiner tree forT ifS connects all pairs of nodes inT. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graphG=(V, E) with edge weightsw _e , edge capacitiesc _e ,e∈E, and node setT ₁,…,T _N , find edge setsS ₁,…,S _N such that eachS _k is a Steiner tree forT _k , at mostc _e of these edge sets use edgee for eache∈E, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper (in this issue).     

Some mutually disjoint steiner systems

A t-design λ; t-d-n is a system of subsets of size d (called blocks) from an n-set S, such that each t-subset from S is contained in precisely λ blocks. A Steiner system S(l, m, n) is a t-design with parameters 1; l-m-n. Two Steiner systems (or t-designs) are disjoint if they share no blocks. A search has been conducted which resulted in discovering 9 mutually disjoint S(5, 8, 24)'s, 24 mutually disjoint S(4, 7, 23)'s, 60 mutually disjoint S(3, 6, 22)'s, and 197 mutually disjoint S(2, 5, 21)'s. Taking unions of several mutually disjoint Steiner systems will then produce t-designs (with varying λ's) on 21, 22, 23, and 24 points.     

Ordering Trees with Nearly Perfect Matchings by Algebraic Connectivity

Let T2k＋1 be the set of trees on 2k＋1 vertices with nearly perfect matchings and α（T） be the algebraic connectivity of a tree T. The authors determine the largest twelve values of the algebraic connectivity of the trees in T2k＋1. Specifically, 10 trees T2,T3,... ,T11 and two classes of trees T（1） and T（12） in T2k＋1 are introduced. It is shown in this paper that for each tree T^′1,T^″1∈T（1）and T^′12,T^″12∈T（12） and each i,j with 2≤i〈j≤11,α（T^′1）=α（T^″1）〉α（Tj）〉α（T^′12）=α（T^″12）.It is also shown that for each tree T with T∈T2k＋1／（T（1）∪{T2,T3,…,T11}∪T（12））,α（T^′12）〉α（T）.     

On a question of A. E. Nussbaum on measurability of families of closed linear operators in a Hilbert space

The purpose of this note is to answer a question A. E. Nussbaum formulated in 1964 about the possible equivalence between weak measurability of a family of densely defined, closed operators {T(t)} _t∈ℝ in a separable complex Hilbert space H\mathcal{H} on one hand, and the notion of measurability of the 2 × 2 operator-valued matrix of projections {(P(Γ(T(t))) _j,k )_1⩽j,k⩽2} _t∈ℝ onto the graph Γ(T(t)) of T(t) on the other, in the negative.     

Partitioning the planes of AG2m(2) into 2-designs

A t-design S_λ(t, k, v) is an arrangement of v elements in blocks of k elements each such that every t element subset is contained in exactly λ blocks. A t-design S_λ(t, k, v) is called t′-resolvable if the blocks can be partitioned into families such that each family is the block system of a S_λ(t′, k, v). It is shown that the S₁(3, 4, 2^2m) design of planes on an even dimensional affine space over the field of two elements is 2-resolvable. Each S₁(2, 4, 2^2m) given by the resolution is itself 1-resolvable. As a corollary it is shown that every odd dimensional projective space over the field of two elements admits a 1-packing of 1-spreads, i.e. a partition of its lines into families of mutually disjoint lines whose union covers the space. This 1-packing may be generated from any one of its spreads by repeated application of a fixed collineation.     

Eine charakterisierung des steinersystems S(5, 8, 24)

S(5, 8, 24) is characterized as the unique Steiner system S(t, k, n) satisfying n = (t + 1)(k ? t + 1) and k ? t + 2 ? 4.     

The nonlinear version of Pazy’s local existence theorem

LetX be a real Banach space,U ⊂X a given open set,A ⊂X×X am-dissipative set andF:C(0,a;U) →L ^∞(0,a;X) a continuous mapping. Assume thatA generates a nonlinear semigroup of contractionsS(t): {ie221-2}) → {ie221-3}), strongly continuous at the origin, withS(t) compact for allt>0. Then, for eachu ₀ ∈ {ie221-4}) ∩U there existsT ∈ ]0,a] such that the following initial value problem: (du(t))/(dt) ∈Au(t) +F(u)(t),u(0)=u ₀, has at least one integral solution on [0,T]. Some extensions and applications are also included.     

On Hong’s conjecture for power LCM matrices

A set S={x ₁,...,x _n } of n distinct positive integers is said to be gcd-closed if (x _i , x _j ) ∈ S for all 1 ⩽ i, j ⩽ n. Shaofang Hong conjectured in 2002 that for a given positive integer t there is a positive integer k(t) depending only on t, such that if n ⩽ k(t), then the power LCM matrix ([x _i , x _j ] ^t ) defined on any gcd-closed set S={x ₁,...,x _n } is nonsingular, but for n ⩾ k(t) + 1, there exists a gcd-closed set S={x ₁,...,x _n } such that the power LCM matrix ([x _i , x _j ] ^t ) on S is singular. In 1996, Hong proved k(1) = 7 and noted k(t) ⩾ 7 for all t ⩾ 2. This paper develops Hong’s method and provides a new idea to calculate the determinant of the LCM matrix on a gcd-closed set and proves that k(t) ⩾ 8 for all t ⩾ 2. We further prove that k(t) ⩾ 9 iff a special Diophantine equation, which we call the LCM equation, has no t-th power solution and conjecture that k(t) = 8 for all t ⩾ 2, namely, the LCM equation has t-th power solution for all t ⩾ 2.     

Steinberg triality groups acting on 2 ? (<Emphasis Type="Italic">v,k</Emphasis>, 1) designs

A 2 - (υ, k, 1) design D = (ℙ,ℙ, ℬ) is a system consisting of a finite set ℙ of υ points and a collection ℬ of ℙ-subsets of ℙ, called blocks, such that each 2-subset of ℙ is contained in precisely one block. Let G be an automorphism group of a 2-(υ, k, 1) design. Delandtsheer proved that if G is block-primitive and D is not a projective plane, then G is almost simple, that is, T ⩽ G ⩽ Aut(T), where T is a non-abelian simple group. In this paper, we prove that T is not isomorphic to ³ D ₄(q). This paper is part of a project to classify groups and designs where the group acts primitively on the blocks of the design.     

Non-uniform Turán-type problems

Given positive integers n,k,t, with 2?k?n, and t<2^k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T_?r(n,k,t) and T_r(n,k,t), where T_?r(n,k,t) (T_r(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T_?r(n,k,t)=(1+o(1))T_r(n,k,t) for fixed r,k,t with and n→∞.     

Intersections among Steiner systems

A Steiner system S(l, m, n) is a system of subsets of size m (called blocks) from an n-set S, such that each d-subset from S is contained in precisely one block. Two Steiner systems have intersection k if they share exactly k blocks. The possible intersections among S(5, 6, 12)'s, among S(4, 5, 11)'s, among S(3, 4, 10)'s, and among S(2, 3, 9)'s are determined, together with associated orbits under the action of the automorphism group of an initial Steiner system. The following are results: (i) the maximal number of mutually disjoint S(5, 6, 12)'s is two and any two such pairs are isomorphic; (ii) the maximal number of mutually disjoint S(4, 5, 11)'s is two and any two such pairs are isomorphic; (iii) the maximal number of mutually disjoint S(3, 4, 10)'s is five and any two such sets of five are isomorphic; (iv) a result due to Bays in 1917 that there are exactly two non-isomorphic ways to partition all 3-subsets of a 9-set into seven mutually disjoint S(2, 3, 9)'s.     

Weakly Singular Integral Operators in Weighted L∞–Spaces

We study integral operators on (−1, 1) with kernels k(x, t) which may have weak singularities in (x, t) with x ∈N₁, t ∈N₂, or x=t, where N₁,N₂ are sets of measure zero. It is shown that such operators map weighted L^∞–spaces into certain weighted spaces of smooth functions, where the degree of smoothness is the higher the smoother the kernel k(x, t) as a function in x is. The spaces of smooth function are generalizations of the Ditzian-Totik spaces which are defined in terms of the errors of best weighted uniform approximation by algebraic polynomials.     

Riesz basis, Paley-Wiener class and tempered splines

The Marcinkiewicz-Zygmund inequality and the Bernstein inequality are established on ∮2m(T,R)∩L2(R) which is the space of polynomial splines with irregularly distributed nodes T={tj}j∈Z, where {tj}j∈Z is a real sequence such that {eitξ}j∈Z constitutes a Riesz basis for L2([-π,π]). From these results, the asymptotic relation E(f,Bπ,2)2=lim E(f,∮2m(T,R)∩L2(R))2 is proved, where Bπ,2 denotes the set of all functions from L2(R) which can be continued to entire functions of exponential type ≤π, i.e. the classical Paley-Wiener class.     

On set systems with a threshold property

For n,k and t such that 1<t<k<n, a set F of subsets of [n] has the (k,t)-threshold property if every k-subset of [n] contains at least t sets from F and every (k-1)-subset of [n] contains less than t sets from F. The minimal number of sets in a set system with this property is denoted by m(n,k,t). In this paper we determine m(n,4,3)exactly for n sufficiently large, and we show that m(n,k,2) is asymptotically equal to the generalized Turán number T_k-1(n,k,2).     

Modular curves and bases for the spaces of cuspidal modular forms

Let Γ⊂SL ₂(ℝ) be a Fuchsian group of the first kind. For a character χ of Γ→ℂ^× of finite order, we define the usual space S _m (Γ,χ) of cuspidal modular forms of weight m≥0. For each ξ in the upper half–plane and m≥3, we construct cuspidal modular forms Δ _k,m,ξ,χ ∈S _m (Γ,χ) (k≥0) which represent the linear functionals f?\fracd^kfdz^k|_z=xf\mapsto\frac{d^{k}f}{dz^{k}}|_{z=\xi} in terms of the Petersson inner product. We write their Fourier expansion and use it to write an expression for the Ramanujan Δ-function. Also, with the aid of the geometry of the Riemann surface attached to Γ, for each non-elliptic point ξ and integer m≥3, we construct a basis of S _m (Γ,χ) out of the modular forms Δ _k,m,ξ ,χ (k≥0). For Γ=Γ ₀(N), we use this to write a matrix realization of the usual Hecke operators T _p for S _m (N,χ).     

Ergodic averages on circles

LetT ₁ andT ₂ be commuting invertible ergodic measure preserving flows on a probability space (X, A, μ). For t = (u,ν) ∈ ℝ², letT ^t =T ₁ ^u T ₂ ^v . LetS ¹ denote the unit circle in ℝ² and σ the rotation invariant unit measure on it. Then, forf∈Lp(X) withp>2, the averagesA _t f(x) = ∫ _s ¹ f(T ^ts x)σ(ds) conver the integral off for a. e.x, ast tends to 0 or infinity. This extends a result of R. Jones [J], who treated the case of three or more dimensions.     

Three classes of smooth Banach submanifolds in B(E,F)

Let E, F be two Banach spaces, and B(E, F), Φ(E, F), SΦ(E, F) and R(E,F) be the bounded linear, Fredholm, semi-Frdholm and finite rank operators from E into F, respectively. In this paper, using the continuity characteristics of generalized inverses of operators under small perturbations, we prove the following result Let ∑ be any one of the following sets {T ∈ Φ(E, F) IndexT =const, and dim N(T) = const.}, {T ∈ SΦ(E, F) either dim N(T) = const. ＜ ∞ or codim R(T) = const.＜ ∞} and {T ∈ R(E, F) RankT =const.＜∞}. Then ∑ is a smooth submanifold of B(E, F) with the tangent space TA∑ = {B ∈ B(E,F) BN(A) (∪) R(A)} for any A ∈ ∑. The result is available for the further application to Thom's famous results on the transversility and the study of the infinite dimensional geometry.     

A problem on semigroups satisfying permutation identities

Let σ be a nontrivial permutation of ordern. A semigroupS is said to be σ-permutable ifx ₁ x ₂ ...x _n =x _σ(1) x _σ(2) ...x _σ(n) , for every (x ₁ ,x ₂,...,x _n )∈S ⁿ . A semigroupS is called(r,t)-commutative, wherer,t are in ℕ^*, ifx ₁ ...x _r x _r+1 ...x _r+t =x _r+1 ...x _r+t x ₁ ...x _r , for every (x ₁ ,x ₂,...,x _r+t ∈S ^r+t . According to a result of M. Putcha and A. Yaqub ([11]), if σ is a fixed-point-free permutation andS is a σ-permutable semigroup then there existsk ∈ ℕ^* such thatS is (1,k)-commutative. In [8], S. Lajos raises up the problem to determine the leastk=k(n) ∈ ℕ^* such that, for every fixed-point-free permutation σ of ordern, every σ-permutable semigroup is also (1,k)-commutative. In this paper this problem is solved for anyn less than or equal to eight and also whenn is any odd integer. For doing this we establish that if a semigroup satisfies a permutation identity of ordern then inevitably it also satisfies some permutation identities of ordern+1.     

Probabilities of high excursions of Gaussian fields

Let {ξ(t), t ∈ T} be a differentiable (in the mean-square sense) Gaussian random field with E ξ(t) ≡ 0, D ξ(t) ≡ 1, and continuous trajectories defined on the m-dimensional interval T ì \mathbbR^m T \subset {\mathbb{R}^m} . The paper is devoted to the problem of large excursions of the random field ξ. In particular, the asymptotic properties of the probability P = P{−v(t) < ξ(t) < u(t), t ∈ T}, when, for all t ∈ T, u(t), v(t) ⩾ χ, χ → ∞, are investigated. The work is a continuation of Rudzkis research started in [R. Rudzkis, Probabilities of large excursions of empirical processes and fields, Sov. Math., Dokl., 45(1):226–228, 1992]. It is shown that if the random field ξ satisfies certain smoothness and regularity conditions, then P = e^−Q  + Qo(1), where Q is a certain constructive functional depending on u, v, T, and the matrix function R(t) = cov(ξ′(t), ξ′(t)).     

Wavelet expansions of fractal measures

Let μ be a measure on ℝⁿ that satisfies the estimate μ(B _r(x))≤cr ^α for allx ∈ ℝⁿ and allr ≤ 1 (B _r(x) denotes the ball of radius r centered atx. Let ϕ _j,k ^(ɛ) (x)=2 ^nj2ϕ^(ɛ)(2 ^j x-k) be a wavelet basis forj ∈ ℤ, κ ∈ ℤⁿ, and ∈ ∈E, a finite set, and letP _j (T)=Σ_ɛ,k <T,ϕ _j,k ^(ɛ) >ϕ _j,k ^(ɛ) denote the associated projection operators at levelj (T is a suitable measure or distribution). Iff ∈Ls ^p(dμ) for 1 ≤p ≤ ∞, we show thatP _j(f dμ) ∈ L^p(dx) and ||P _j (fdμ)||L _p(dx)≤c2 ^{j((n-α)/p′))}||f||L _p(dμ) for allj ≥ 0. We also obtain estimates for the limsup and liminf of ||P _j (fdμ)||L _p(dx) under more restrictive hypotheses. Communicated by Guido Weiss