On the decomposition of k-noncrossing RNA structures

A k-noncrossing RNA structure can be identified with a k-noncrossing diagram over [n], which in turn corresponds to a vacillating tableau having at most (k−1) rows. In this paper we derive the limit distribution of irreducible substructures via studying their corresponding vacillating tableaux. Our main result proves, that the limit distribution of the numbers of irreducible substructures in k-noncrossing, σ-canonical RNA structures is determined by the density function of a -distribution for some τ_k>1.     

Joint distributions of runs in a sequence of higher-order two-state Markov trials

Consider a time homogeneous {0, 1}-valued m-dependent Markov chain . In this paper, we study the joint probability distribution of number of 0-runs of length and number of 1-runs of length in n trials. We study the joint distributions based on five popular counting schemes of runs. The main tool used to obtain the probability generating function of the joint distribution is the conditional probability generating function method. Further a compact method for the evaluation of exact joint distribution is developed. For higher-order two-state Markov chain, these joint distributions are new in the literature of distributions of run statistics. We use these distributions to derive some waiting time distributions.     

On a conjecture concerningk-Hamilton-nice sequences

In this paper, we prove that a non-negative rational number sequence (a ₁,a ₂, ...,a _k+1) isk-Hamilton-nice, if (1)a _k+12, and (2) _j ^=1/h (i _j –1)k–1 implies for arbitraryi ₁,i ₂,...i _h {1,2,... ,k}. This result was conjectured by Guantao Chen and R.H. Schelp, and it generalizes several well-known sufficient conditions for graphs to be Hamiltonian.This project is supported by the National Natural Science Foundation of China.     

Dense trees: a new look at degenerate graphs

Dense trees are undirected graphs defined as natural extensions of trees. They are already known in the realm of graph coloring under the name of k-degenerate graphs. For a given integer k1, a k-dense cycle is a connected graph, where the degree of each vertex is greater than k. A k-dense forest F=(V,E) is a graph without k-dense cycles as subgraphs. If F is connected, then is a k-dense tree. 1-dense trees are standard trees. We have |E|k|V|−k(k+1)/2. If equality holds F is connected and is called a maximal k-dense tree. k-trees (a subfamily of triangulated graphs) are special cases of maximal k-dense trees.We review the basic theory of dense trees in the family of graphs and show their relation with k-trees. Vertex and edge connectivity is thoroughly investigated, and the role of maximal k-dense trees as “reinforced” spanning trees of arbitrary graphs is presented. Then it is shown how a k-dense forest or tree can be decomposed into a set of standard spanning trees connected through a common “root” of k vertices. All sections include efficient construction algorithms. Applications of k-dense trees in the fields of distributed systems and data structures are finally indicated.     

Waiting times: Positive and negative results on the Wyner-Ziv problem

Asymptotic properties of the waiting timeW _k (x,y) until an initial segment of lengthk of a sample pathx of an ergodic finite-alphabet process is seen in an independently chosen sample pathy are discussed. Wyner and Ziv have shown that for irreducible Markov chains, (1/k) logW _k (x,y) converges in probability to the entropyH of the process. In this paper, almost sure convergence toH is established for the somewhat larger class of functions of irreducible Markov chains and convergence in probability toH is established for weak Bernoulli processes. A stationary coding of an i.i.d. process is constructed for which there is a subsequencek(n) such that (1/k(n) logW _k(n )(x,y), converges in probability to +. Positive and negative results for the case when only approximate matches are required are also obtained.Partially supported by NSF Grant DMS-9024240.From 9/1 to 12/1 earch year: Mathematies Institute, POB 127, 1364 Budapest, Hungary. 011-361-1-177-175. At other times: Department of Mathematics, University of Toledo, Toledo, Ohio 43606, (419) 537-2069.     

Distributions of Numbers of Success Runs of Fixed Length in Markov Dependent Trials

Let {Z _n , n 1} be a time-homogeneous {0, 1}-valued Markov chain, and let N _n be a random variable denoting the number of runs of "1" of length k in the first n trials. In this article we conduct a systematic study of N _n by establishing formulae for the evaluation of its probability generating function, probability mass function and moments. This is done in three different enumeration schemes for counting runs of length k, the "non-overlapping", the "overlapping" and the "at least" scheme. In the special case of i.i.d. trials several new results are established.     

Distributions of numbers of failures and successes until the first consecutivek successes

Exact distributions of the numbers of failures, successes and successes with indices no less thanl (1lk–1) until the first consecutivek successes are obtained for some {0, 1}-valued random sequences such as a sequence of independent and identically distributed (iid) trials, a homogeneous Markov chain and a binary sequence of orderk. The number of failures until the first consecutivek successes follows the geometric distribution with an appropriate parameter for each of the above three cases. When the {0, 1}-sequence is an iid sequence or a Markov chain, the distribution of the number of successes with indices no less thanl is shown to be a shifted geometric distribution of orderk - l. When the {0, 1}-sequence is a binary sequence of orderk, the corresponding number follows a shifted version of an extended geometric distribution of orderk - l.This research was partially supported by the ISM Cooperative Research Program (92-ISM-CRP-16) of the Institute of Statistical Mathematics.     

Existence and Construction of H 1-Splines of Class C k on a Three Directional Mesh

Let be the uniform triangulation generated by the usual three directional mesh of the plane and let H ₁ be the regular hexagon formed by the six triangles of surrounding the origin. We study the space of piecewise polynomial functions in C ^k (R ²) with support H ₁ having a sufficiently high degree n, which are invariant with respect to the group of symmetries of H ₁ and whose sum of integer translates is constant. Such splines are called H ₁-splines. We first compute the dimension of this space in function of n and k. Then we prove the existence of a unique H ₁-spline of minimal degree for any fixed k0. Finally, we describe an algorithm computing the Bernstein–Bézier coefficients of this spline.     

Numbers of Success-Runs of Specified Length Until Certain Stopping Time Rules and Generalized Binomial Distributions of Order k

A new distribution called a generalized binomial distribution of order k is defined and some properties are investigated. A class of enumeration schemes for success-runs of a specified length including non-overlapping and overlapping enumeration schemes is rigorously studied. For each nonnegative integer less than the specified length of the runs, an enumeration scheme called -overlapping way of counting is defined. Let k and be positive integers satisfying < k. Based on independent Bernoulli trials, it is shown that the number of (– 1)-overlapping occurrences of success-run of length k until the n-th overlapping occurrence of success-run of length follows the generalized binomial distribution of order (k–). In particular, the number of non-overlapping occurrences of success-run of length k until the n-th success follows the generalized binomial distribution of order (k– 1). The distribution remains unchanged essentially even if the underlying sequence is changed from the sequence of independent Bernoulli trials to a dependent sequence such as higher order Markov dependent trials. A practical example of the generalized binomial distribution of order k is also given.     

On the Waiting Time for the First Success Run

Let k and m are positive integers with k ≥ m. The probability generating function of the waiting time for the first occurrence of consecutive k successes in a sequence of m-th order Markov dependent trials is given as a function of the conditional probability generating functions of the waiting time for the first occurrence of consecutive m successes. This provides an efficient algorithm for obtaining the probability generating function when k is large. In particular, in the case of independent trials a simple relationship between the geometric distribution of order k and the geometric distribution of order k−1 is obtained. This research was partially supported by the ISM Cooperative Research Program(2004-ISM-CRP-2006) and by a Grant-in-Aid for Scientific Research (C) of the JSPI (Grant Number 16500183)     

Existence of 1-Rotational <Emphasis Type="Italic">k</Emphasis>-Cycle Systems of the Complete Graph

We explicitly solve the existence problem for 1-rotational k-cycle systems of the complete graph K_v with v1 or k (mod 2k). For v1 (mod 2k) we have existence if and only if k is an odd composite number. For any odd k and vk (mod 2k), (except k3 and v15, 21 (mod 24)) a 1-rotational k-cycle system of K_v exists.Final version received: June 18, 2003     

On Some Properties of Randomly Indexed Sequences of Random Elements

Let be a probability space with a nonatomic measure P and let (S,ρ) be a separable complete metric space. Let {N _n ,n≥1} be an arbitrary sequence of positive-integer valued random variables. Let {F _k ,k≥1} be a family of probability laws and let X be some random element defined on and taking values in (S,ρ). In this paper we present necessary and sufficient conditions under which one can construct an array of random elements {X _n,k ,n,k≥1} defined on the same probability space and taking values in (S,ρ), and such that , and moreover as  n→∞. Furthermore, we consider the speed of convergence to X as n→∞.      

W-algebras related to parafermion algebras

We study a W-algebra of central charge 2(k−1)/(k+2), k=2,3,…, contained in the commutant of a Heisenberg algebra in a simple affine vertex operator algebra L(k,0) of type with level k. We calculate the operator product expansions of the W-algebra. We also calculate some singular vectors in the case k6 and determine the irreducible modules and Zhu's algebra. Furthermore, the rationality and the C₂-cofiniteness are verified for such k.     

On a Problem Concerning k-Subdomination Numbers of Graphs

One of numerical invariants concerning domination in graphs is the k-subdomination number of a graph G. A conjecture concerning it was expressed by J.H. Hattingh, namely that for any connected graph G with n vertices and any k with the inequality holds. This paper presents a simple counterexample which disproves this conjecture. This counterexample is the graph of the three-dimensional cube and k = 5.     

On construction ofk-wise independent random variables

A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1} ⁿ for somen. A probability space isk-wise independent if, whenY _i is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY _i 's is (mutually) independent, and it is said to be a probability spacefor p ₁,p ₂, ...,p _n ifP[Y _i =1]=p _i .We study constructions ofk-wise independent 0–1 probability spaces in which thep _i 's are arbitrary. It was known that for anyp ₁,p ₂, ...,p _n , ak-wise independent probability space of size always exists. We prove that for somep ₁,p ₂, ...,p _n [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp _i =k/n has size (n _k ). For a very large degree of independence —k=[n], for >1/2- and allp _i =1/2, we prove a lower bound on the size of . We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology.     

Differential geometry of tensor product immersions II

In the first part of this series, we prove that the tensor product immersionf ₁ f _2k of2k isometric spherical immersions of a Riemannian manifoldM in Euclidean space is of-type with k and classify tensor product immersionsf ₁ f _2k which are ofk-type. In this article we investigate the tensor product immersionsf ₁ f _2k which are of (k+1)-type. Several classification theorems are obtained.     

On the Value of a Random Minimum Weight Steiner Tree

Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1+o(1))(k-1)(log n-log k)/n when k =o(n) and n.* Research supported in part by NSF grant DSM9971788 Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting IBM T. J. Watson Research Center.     

On-line k-Truck Problem and Its Competitive Algorithms

In this paper, based on the Position Maintaining Strategy (PMS for short), on-line scheduling of k-truck problem, which is a generalization of the famous k-server problem, is originally presented by our team. We proposed several competitive algorithms applicable under different conditions for solving the on-line k-truck problem. First, a competitive algorithm with competitive ratio 2k+1/ is given for any 1. Following that, if (c+1)/(c-1) holds, then there must exist a (2k-1)-competitive algorithm for k-truck problem, where c is the competitive ratio of the on-line algorithm about the relevant k-server problem. And then a greedy algorithm with competitive ratio 1+/, where lambda is a parameter related to the structure property of a given graph, is given. Finally, competitive algorithms with ratios 1+1/ are given for two special families of graphs.     

On <Emphasis Type="Italic">k</Emphasis>-th Power of Upper Bound Graphs

We consider k-th power of upper bound graphs. According to the characterization of upper bound graphs, we obtain a characterization of k-th power of upper bound graphs. That is, for a connected upper bound graph G, G^k is an upper bound graph if and only if for any pair of A^k -simplicial vertices s₁, s₂ such that , there exists a G^k -simplicial vertex s satisfying the conditions: and . Furthermore we also get some properties on squares of upper bound graphs.AMS Subject Classification: 05C62.     

On the distribution of square-full and cube-full numbers

There are many results on the distribution of square-full and cube-full numbers. In this article the distribution of these numbers are studied in more detail. Suchk-full numbers (k=2,3) are considered which are at the same time 1-free (1k+2). At first an asymptotic result is given for the numberN _k,1(x) ofk-full and 1-free numbers not exceedingx. Then the distribution of these numbers in short intervals is investigated. We obtain different estimations of the differenceN _k,1(x+h)–N_k,1(x) in the casesk=2, 1=4,5,6,7,18 andk=3, 1=5,6,7, 18.