Multicolored trees in complete graphs

A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph K_2n(n > 2) with 2n ? 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a₁,…, a_k) is a color distribution for the complete graph K_n, n ≥ 5, such that , then there exist two edge‐disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph K_n with the above distribution if T is a non‐star multicolored spanning tree of K_n, then there exists a multicolored spanning tree T' of K_n such that T and T' are edge‐disjoint. Also it is shown that if K_n, n ≥ 6, is edge colored with k colors and , then there exist two edge‐disjoint multicolored spanning trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221–232, 2007     

Joint similarity problems and the generation of operator algebras with bounded length

There is a pair of commuting operators (T ₁,T ₂) on Hilbert space such that eachT ₁ andT ₂ is similar to a contraction but the pair (T ₁,T ₂) is not similar to a pair of contractions. There is a pair of commuting unitarizable representations (₁,₂) on the free group withN2 generators such that (₁,₂) is not similar to a pair of unitary representations. In connection with these examples, we introduce and study a notion of length for aC ^*-algebra (or an operator algebra) generated by two subalgebras, which is analogous to the minimum length of a word in the generators of a group.Partially supported by the N.S.F.     

Induced operators on symmetry classes of tensors

LetV be ann-dimensional inner product space,T _i ,i=1,...,k, k linear operators onV, H a subgroup ofS _m (the symmetric group of degreem), a character of degree 1 andT a linear operator onV. Denote byK(T) the induced operator ofT onV (H), the symmetry class of tensors associated withH and . This note is concerned with the structure of the setK _{, m} ^H (T₁,...,T_k) consisting of all numbers of the form traceK(T ₁ U ₁...T _k U _k ) whereU _i ,i=1,...k vary over the group of all unitary operators onV. For V=ⁿ or ⁿ, it turns out thatK _{, m} ^H (T₁,...,T_k) is convex whenm is not a multiple ofn. Form=n, there are examples which show that the convexity of _{, m} ^H (T₁,...,T_k) depends onH and .The author wishes to express his thanks to Dr. Yik-Hoi Au-Yeung for his valuable advice and encouragement.     

Lower bounds on signed edge total domination numbers in graphs

The open neighborhood N _G (e) of an edge e in a graph G is the set consisting of all edges having a common end-vertex with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge total dominating function of G. The minimum of the values , taken over all signed edge total dominating function f of G, is called the signed edge total domination number of G and is denoted by γ _st ′(G). Obviously, γ _st ′(G) is defined only for graphs G which have no connected components isomorphic to K ₂. In this paper we present some lower bounds for γ _st ′(G). In particular, we prove that γ _st ′(T) ⩾ 2 − m/3 for every tree T of size m ⩾ 2. We also classify all trees T with γ _st ′(T). Research supported by a Faculty Research Grant, University of West Georgia.     

Some localized separation axioms and their implications

In a topological spaceX, a T₂-distinct pointx means that for anyyX xy, there exist disjoint open neighbourhoods ofx andy. Similarly, T₀-distinct points and T₁distinct points are defined. In a T_i-distinct point-setA, we assume that eachxA is a T _i -distinct point (i=0, 1, 2). In the present paper some implications of these notions which localize the T _i -separation axioms (i=0, 1, 2) requirement, are studied. Suitable variants of regularity and normality in terms of T₂-distinct points are shown hold in a paracompact space (without the assumption of any separation axioms). Later T₀-distinct points are used to give two characterizations of the R _D -axiom.¹ In the end, some simple results are presented including a condition under which an almost compact set is closed and a result regarding two continuous functions from a topological space into a Hausdorff space is sharpened. A result which relates a limit pointv to an -limit point is stated.     

Computation of a lower bound of the lengths of schedules

For a graphG of strict partial ordering, the lower estimates T₁ T₂T₃T₄ of the lengths of m-processor schedules are given depending on the extent of the details known about graphG. The best estimate, T₄, is obtained if the partitions of the set of vertices ofG into levels from above and from below are known. The complexity of obtaining the estimate T₄ is equal to O(n), where n=G.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 124, pp. 35–40, 1983.     

Two results on exact boundary control of parabolic equations

(1) The known nullcontrollability result for boundary control ofu _t = u_xx + q(x)u is generalized to consider a time-dependent coefficientq. (2) For boundary control ofu _t =Au (where it is known thatC _T : (initial data) (optimal nullcontrol for timeT) exists for allT>0) it is shown that logC _T =145-1 asT 0.     

Invariant Metrics on Nilmanifolds with Positive Topological Entropy

Let T _n denote the group of real n × n upper-triangular matrices with 1s on the diagonal. This paper constructs left-invariant Riemannian and sub-Riemannian metrics on T ₃ T ₄ whose geodesic flow has a subsystem that factors onto a suspended horseshoe. As a corollary, left-invariant Riemannian metrics with positive topological entropy are constructed on all quotients DT _n where D is a discrete subgroup of T _n and n 7.     

Sufficient conditions for asymptotic optimal control

For a selected family of Lagrange-type control problems involving a nonnegative integral costJ _T (y,u) over the interval [0,T], 0<T<, with system conditions consisting of differential inequalities and/or equalities, the following material is treated: (i) a resumé of relevant necessary conditions and sufficient conditions for a pair (y _T ,u _T ) to minimizeJ _T (y,u); (ii) conditions sufficient for the convergence asT of minimizing pairs (y _T ,u _T ) over [0,T] to a limit pair (y ,u ) over the infinite-time interval [0, ); (iii) conditions sufficient for (y ,u ) to minimize the costJ (y,u) over [0, ); and (iv) conditions sufficient for the optimal cost per unit timeJ _T (y _T ,u _T )/T to have a limit asT.     

Euler Tours of Maximum Girth in K2 n +1 and K2 n ,2 n

Given an eulerian graph G and an Euler tour T of G, the girth of T, denoted by g(T), is the minimum integer k such that some segment of k+1 consecutive vertices of T is a cycle of length k in G. Let g^E(G)= maxg(T) where the maximum is taken over all Euler tours of G.We prove that g^E(K_2n,2n)=4n–4 and 2n–3g^E(K_2n+1)2n–1 for any n2. We also show that g^E(K₇)=4. We use these results to prove the following:1)The graph K_2n,2n can be decomposed into edge disjoint paths of length k if and only if k4n–1 and the number of edges in K_2n,2n is divisible by k.2)The graph K_2n+1 can be decomposed into edge disjoint paths of length k if and only if k2n and the number edges in K_2n+1 is divisible by k.     

Some spectral properties ofm-accretive differential operators

Form-accretive operatorT=T ₀+q compactness of its resolventR(z, T), zP(T) and ofR(z, T)–R(z, T ₀),zP(T)P(T ₀) under suitable assumptions onT ₀ and their perturbationq is established. This result is used in the study of spectral properties ofT andT ₀.     

Fcfs-scheduling in a hard real-time environment under rush-hour conditions

We investigate some real-time behaviour of a (discrete time) single server system with FCFS (first come first serve) task scheduling under rush-hour conditions. The main result deals with the probability distribution of a random variable SRD(T), which describes the time the system operates without violating a fixed task service time deadlineT.Relying on a simple general probability model, asymptotic formulas concerning the mean and the variance of SRD(T) are determined; for instance, if the average arrival rate is larger than the departure rate, the expectation of SRD(T) is proved to fulfilE[SRD(T)]=c ₁+O(T ^–3) forT, wherec ₁ denotes some constant. If the arrival rate equals the departure rate, we findE[SRD(T)]c ₂ T ⁱ for somei2.     

Lie Groupoids, Gerbes, and Non-Abelian Cohomology

We observe that any regular Lie groupoid G over a manifold M fits into an extension K G E of a foliation groupoid E by a bundle of connected Lie groups K. If F is the foliation on M given by the orbits of E and T is a complete transversal to F , this extension restricts to T, as an extension K _T G _T E _T of an étale groupoid E _T by a bundle of connected groups K _T . We break up the classification problem for regular Lie groupoids into two parts. On the one hand, we classify the latter extensions of étale groupoids by (non-Abelian) cohomology classes in a new ech cohomology of étale groupoids. On the other hand, given K and E and an extension K _T G _T E _T over T, we present a cohomological obstruction to the problem of whether this is the restriction of an extension K G E over M; if this obstruction vanishes, all extensions K G E over M which restrict to a given extension over the transversal together form a principal bundle over a group of bitorsors under K.     

Semigroups of quasi-compact operators

LetT ₁ andT ₂ be two quasi-compact operators on a complex Banach spaceX, whereX is the Banach space of all complex valued and continuous functions on a compact Hausdorff spaceY. LetS(I, T ₁,T ₂) denote the semigroup generated byT ₁,T ₂ and the identity operatorI. We show that under certain conditions the kernel of the semigroup is a finite group. I am grateful to Professor C. T. Taam, my advisor at The George Washington University. His support and his valuable contributions made this research possible. I am also very thankful to the referee for many important suggestions which improved the results and quality of the paper. In particular, the proof in Theorem 4 which shows the kernel of is a finite group, has been suggested by the referee.     

Embeddings and Other Mappings of Rooted Trees Into Complete Trees

Let T ⁿ be the complete binary tree of height n, with root 1 _n as the maximum element. For T a tree, define and . We disprove a conjecture of Kubicki, Lehel and Morayne, which claims that for any fixed n and arbitrary rooted trees T ₁ T ₂. We show that A(n; T) is of the form where l is the number of leaves of T, and each q _j is a polynomial. We provide an algorithm for calculating the two leading terms of q _l for any tree T. We investigate the asymptotic behaviour of the ratio A(n; T)/C(n; T) and give examples of classes of pairs of trees T ₁, T ₂ where it is possible to compare A(n; T ₁)/C(n; T ₁) and A(n; T ₂)/C(n; T ₂). By calculating these ratios for a particular class of pairs of trees, we show that the conjecture fails for these trees, for all sufficiently large n. Kubicki, Lehel and Morayne have proved the conjecture when T ₁, T ₂ are restricted to being binary trees. We also look at embeddings into other complete trees, and we show how the result can be viewed as one of many possible correlation inequalities for embeddings of binary trees. We also show that if we consider strict order-preserving maps of T ₁, T ₂ into T ⁿ (rather than embeddings) then the corresponding correlation inequalities for these maps also generalise to arbitrary trees.     

Vandermonde sets and super-Vandermonde sets

Given a set TGF(q), |T|=t, w_T is defined as the smallest positive integer k for which ∑_yTy^k≠0. It can be shown that w_Tt always and w_Tt−1 if the characteristic p divides t. T is called a Vandermonde set if w_Tt−1 and a super-Vandermonde set if w_T=t. This (extremal) algebraic property is interesting for its own right, but the original motivation comes from finite geometries. In this paper we classify small and large super-Vandermonde sets.     

Relationship between the Contact Time of Polymer Surfaces and Their Bond Strength

Films of amorphous polystyrene (PS) (mono- and polydisperse polymers) and poly(phenylene oxide) (PPO) were brought into contact at a low pressure (0.8 MPa) under temperatures T _h from 62 to 156°C. The contact time t was varied from 2 min to 96 h. Partially healed PS-PS, PPO-PPO, and PS-PPO contacts were broken at room temperature and the shear strength in the contact zone was measured. The experimental -t curves were analyzed in double logarithmic coordinates. The value of for the three interfaces investigated was within 0.07-0.32 at T _h < T _g, where is the glass transition temperature. In the same way, the data on strength development taken from the literature for a number of polymer-polymer contacts formed both above and below T _g were analyzed, and the range of variations in proved to be roughly the same (0.05-0.35). The results obtained are discussed within the framework of theories of molecular dynamics for the polymer bulk and the interface.     

Almost stable spectra and limits of similarities

Suppose that {D _n } is a sequence of invertible operators on a Hilbert space, andD _n T D _n ^–1 converges in norm toT ₀. Recently, H. Bercovici, C. Foias, and A. Tannenbaum have shown that if {D _n ^±1 n=1, 2,...} is contained in a finite dimensional subspace of operators, thenT andT ₀ must have the same spectral radius. Using this result, R. Teodorescu proved that the resolvents ofT andT ₀ have the same unbounded component. We show that in fact the spectra differ only by certain eigenvalues ofT ₀, and the spectrum ofT ₀ is obtained by filling in holes in the spectrum ofT; i.e., by adjoining (all, some, or none of the) bounded components of the resolvent ofT to the spectrum ofT.     

Idealization of Some Weak Separation Axioms

An ideal is a nonempty collection of subsets closed under heredity and finite additivity. The aim of this paper is to unify some weak separation properties via topological ideals. We concentrate our attention on the separation axioms between T ₀ and T _1/2. We prove that if (X,,I) is a semi-Alexandroff T _I -space and I is a -boundary, then I is completely codense.