Mixed ramsey numbers: Chromatic numbers versus graphs

For positive integers n₁, n₂, …, n_I and graphs G_I+1, G_I+2, …, G_k, 1 ≤ / < k, the mixed Ramsey number _χ(n₁, …, n₁, G_I+1, …, G_k) is define as the least positive integer p such that for each factorization K_p = F₁⊕ … ⊕ F_⊕ F_I+1⊕ … ⊕ F_k, it it follows that χ(F_i) ≥ n_i for some i, 1 ? i ? l, or G_i is a subgraph of F_i for some i, l < i ? k. Formulas are presented for maxed Ramsey numbers in which the graphs G_I+1, G_I+2, …, G_k are connected, and in which k = I+1 and G_I+1 is arbitray.     

Random suffix search trees

A random suffix search tree is a binary search tree constructed for the suffixes X_i = 0 · B_iB_i+1B_i+2… of a sequence B₁, B₂, B₃, … of independent identically distributed random b‐ary digits B_j. Let D_n denote the depth of the node for X_n in this tree when B₁ is uniform on ?_b. We show that for any value of b > 1, ??D_n = 2 log n + O(log²log n), just as for the random binary search tree. We also show that D_n/??D_n → 1 in probability. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

Extreme Value Models for Software Reliability

When a new software is produced it is usually tested for failure several times in succession (whenever a failure is detected the software is rectified and tested again for failure). Suppose X ₁,X ₂,…,X _k denote the times between failures. For the customer the main characteristic of interest is T=max(X ₁,X ₂,…,X _k ). In particular, one would be interested in t _α for which Pr{T≤t _α }=1?α for small α. In this paper we consider four models for T based on the class of extreme value distributions (Gumbel, Fre´chet, Weibull and Pareto) and provide methods for estimating t _α . In addition to numerical estimation of t _α , we perform sensitivity analysis of t _α with respect to the four models considered.     

Asymptotic expansions in the central limit theorem for compound and Markov processes

Summary For independent identically distributed bivariate random vectors (X ₁, Y ₁), (X ₂, Y ₂), ... and for large t the distribution of X ₁ +...+ X _N(t) is approximated by asymptotic expansions. Here N(t) is the counting process with lifetimes Y ₁, Y ₂,.... Similar expansions are derived for multivariate X ₁. Furthermore, local asymptotic expansions are valid for the distribution of f(X ₁)+ ...+ f(X _N ) when N is large and nonrandom, and X _i , i=1, 2,..., is a discrete strongly mixing Markov chain.     

On a Maximum Principle for Bergman Spaces with Small Exponents

We prove a stability theorem for the nullity of a linear combination c ₁ P ₁ + c ₂ P ₂ of two idempotent operators P ₁, P ₂ on a Banach space provided c ₁, c ₂ and c ₁ + c ₂ are nonzero. We then show that for c ₁ P ₁ + c ₂ P ₂ the property of being upper semi-Fredholm, lower semi-Fredholm and Fredholm, respectively, is independent of the choice of c ₁, c ₂, and that the nullity, defect and index of c ₁ P ₁ + c ₂ P ₂ are stable.     

The Structure of the Tame Kernels of Quadratic Number Fields (III)

Let F be an imaginary quadratic number field and K ₂ O _F the tame kernel of F. In this article, we determine all possible values of r ₄(K ₂ O _F ) for each type of imaginary quadratic number field F. In particular, for each type of imaginary quadratic number field we give the maximum possible value of r ₄(K ₂ O _F ) and show that each integer between the lower and upper bounds occurs as a value of the 4-rank of K ₂ O _F for infinitely many imaginary quadratic number fields F.     

Highly parity linked graphs

A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x ₁,x ₂, …, x _k ,y ₁,y ₂, …, y _k , G contains k pairwise disjoint paths P ₁, …, P _k such that P _i joins x _i and y _i for i = 1,2, …, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P ₁, …, P _k can be chosen such that the parities of their length are prescribed. Thomassen [22] was the first to prove the existence of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph. In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the Erdős-Pósa type result for parity-k-linked graphs. Research partly supported by the Japan Society for the Promotion of Science for Young Scientists, by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research and by Inoue Research Award for Young Scientists.     

On the existence of shock fronts for a Burgers equation with a singular source term

In this paper we consider the Cauchy problem for the equation ∂u/∂t + u ∂u/∂x + u/x = 0 for x > 0, t ⩾ 0, with u(x, 0) = u⁰₋(x) for x < x₀, u(x, 0) = u⁰₊(x) for x > x₀, u⁰₋(x₀) > u⁰₊(x₀). Following the ideas of Majda, 1984 and Lax, 1973, we construct, for smooth u⁰₋ and u⁰₊, a global shock front weak solution u(x, t) = u₋(x, t) for x < ϕ(t), u(x, t) = u₊(x, t) for x > ϕ(t), where u₋ and u₊ are the strong solutions corresponding (respectively) to u⁰₋ and u⁰₊ and the curve t → ϕ(t) is defined by dϕ/dt (t) = 1/2[u₋(ϕ(t), t) + u₊(ϕ(t), t)], t ⩾ 0 and ϕ(0) = x₀. © 1998 B. G. Teubner Stuttgart—John Wiley & Sons, Ltd.     

The Poincaré series of the algebras of simultaneous invariants and covariants of two binary forms

Let ? _{d 1, d 2} and 𝒞 _{d 1, d 2} be the algebras of simultaneous invariants and simultaneous covariants of the two binary forms of degrees d ₁ and d ₂. Formulas for computation of the Poincaré series 𝒫? _{d 1, d 2} (z), 𝒫𝒞 _{d 1, d 2} (z) of the algebras are found. By using these formulas, we have computed the series for d ₁, d ₂ ≤ 20.     

On regularity criterion to the 3D axisymmetric incompressible MHD equations

This paper is concerned with the regularity criterion for a class of axisymmetric solutions to 3D incompressible magnetohydrodynamic equations. More precisely, for the solutions that have the form of u = u_re_r+u_θe_θ+u_ze_z and b = b_θe_θ, we prove that if |ru(x,t)|≤C holds for ?1≤t < 0, then (u,b) is regular at time zero. This result can be thought as a generalization of recent results in for the 3D incompressible Navier‐Stokes equations. Copyright © 2016 John Wiley & Sons, Ltd.     

Modules Whose t-Closed Submodules Have a Summand as a Complement

We define and investigate T ₁₁-type modules as a generalization of t-extending modules, and modules satisfying C ₁₁ condition. A module M is said to be T ₁₁-type if every t-closed submodule of M has a complement which is a direct summand. Direct sums of T ₁₁-type modules inherit the property. Some equivalent conditions for a module M to be T ₁₁-type are given. We characterize a module M for which every direct summand satisfies T ₁₁ condition. If R _R is T ₁₁-type, then R/Z ₂(R _R ) is a C ₂ ring if and only if it is a von Neumann regular ring. Applying this result, we characterize a right t-extending (resp., finitely Σ-t-extending, or Σ-t-extending) ring R for which R/Z ₂(R _R ) is von Neumann regular.     

Best affine unbiased response decomposition

Given two linear regression models y₁=X₁β₁+u₁ and y₂=X₂β₂+u₂ where the response vectors y₁ and y₂ are unobservable but the sum y=y₁+y₂ is observable, we study the problem of decomposing y into components and , intended to be close to y₁ and y₂, respectively. We develop a theory of best affine unbiased decomposition in this setting. A necessary and sufficient condition for the existence of an affine unbiased decomposition is given. Under this condition, we establish the existence and uniqueness of the best affine unbiased decomposition and provide an expression for it.     

A spectral technique for random satisfiable 3CNF formulas

Let I be a random 3CNF formula generated by choosing a truth assignment ? for variables x₁, x_n uniformly at random and including every clause with i literals set true by ? with probability p_i, independently. We show that for any constants 0 ≤ η₂,η₃ ≤ 1 there is a constant d_min so that for all d ≥ d_min a spectral algorithm similar to the graph coloring algorithm of Alon and Kahale will find a satisfying assignment with high probability for p₁ = d/n², p₂ = η₂d/n², and p₃ = η₃d/n². Appropriately setting the η_i's yields natural distributions on satisfiable 3CNFs, not‐all‐equal‐sat 3CNFs, and exactly‐one‐sat 3CNFs. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Asymptotic behavior of the critical probability for ρ-percolation in high dimensions

We consider oriented bond or site percolation on ℤ ^d ₊. In the case of bond percolation we denote by P _p the probability measure on configurations of open and closed bonds which makes all bonds of ℤ ^d ₊ independent, and for which P _p {e is open} = 1 −P _p e {is closed} = p for each fixed edge e of ℤ ^d ₊. We take X(e) = 1 (0) if e is open (respectively, closed). We say that ρ-percolation occurs for some given 0 < ρ≤ 1, if there exists an oriented infinite path v ₀ = 0, v ₁, v ₂, …, starting at the origin, such that lim inf _{n →∞} (1/n) ∑ _i=1 ⁿ X(e _i ) ≥ρ, where e _i is the edge {v _i−1 , v _i }. [MZ92] showed that there exists a critical probability p _c = p _c (ρ, d) = p _c (ρ, d, bond) such that there is a.s. no ρ-percolation for p < p _c and that P _p {ρ-percolation occurs} > 0 for p > p _c . Here we find lim _{d →∞} d ^1/ρ p _c (ρd, bond) = D ₁ , say. We also find the limit for the analogous quantity for site percolation, that is D ₂ = lim _{d →∞} d ^1/ρ p _c (ρ, d, site). It turns out that for ρ < 1, D ₁ < D ₂ , and neither of these limits equals the analogous limit for the regular d-ary trees. Received: 7 January 1999 / Published online: 14 June 2000     

Convexity of the permanent for doubly stochastic matrices

Let Ω _n denote the set of all n×n doubly stochastic matrices and let J_n denote the n×n matrix all of whose entries are 1/n. Lih and Wang conjectuted that per[(1?i)J_n +iA≤(1?i)perJ_n 1i perA for all A∈Ω _n and all t∈[0,1/2], and proved their conjecture for n=3. In this paper we propose a similar conjecture asserting that for any A∈Ω _n \{J_n }, the permanent function is strietly convex on the straight line segment joining J_n and (J_n +A)/2, and prove it for the case n=3.     

Partitions of a graph into paths with prescribed endvertices and lengths

For a graph G, let σ₂(G) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| = n = Σ^k_{i = 1} a_i and σ₂(G) ≥ n + k − 1, then for any k vertices v₁, v₂,…, v_k in G, there exist vertex‐disjoint paths P₁, P₂,…, P_k such that |V(P_i)| = a_i and v_i is an endvertex of P_i for 1 ≤ i ≤ k. In this paper, we verify the conjecture for the cases where almost all a_i ≤ 5, and the cases where k ≤ 3. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 163–169, 2000     

On Ramsey Numbers for Trees Versus Wheels of Five or Six Vertices

 For given two graphs G dan H, the Ramsey number R(G,H) is the smallest positive integer n such that every graph F of order n must contain G or the complement of F must contain H. In [12], the Ramsey numbers for the combination between a star S _n and a wheel W _m for m=4,5 were shown, namely, R(S _n ,W ₄)=2n−1 for odd n and n≥3, otherwise R(S _n ,W ₄)=2n+1, and R(S _n ,W ₅)=3n−2 for n≥3. In this paper, we shall study the Ramsey number R(G,W _m ) for G any tree T _n . We show that if T _n is not a star then the Ramsey number R(T _n ,W ₄)=2n−1 for n≥4 and R(T _n ,W ₅)=3n−2 for n≥3. We also list some open problems. Received: October, 2001 Final version received: July 11, 2002 RID="*" ID="*" This work was supported by the QUE Project, Department of Mathematics ITB Indonesia Acknowledgments. We would like to thank the referees for several helpful comments.     

Edge-disjoint paths and cycles in n-edge-connected graphs

We consider finite undirected loopless graphs G in which multiple edges are possible. For integers k,l ≥ 0 let g(k, l) be the minimal n ≥ 0 with the following property: If G is an n-edge-connected graph, s₁, ?,s_k, t₁, ?,t_k are vertices of G, and f₁, ?,f_l, g₁, ?,g_l, are pairwise distinct edges of G, then for each i = 1, ?, k there exists a path P_i in G, connecting s_i and t_i and for each i = 1, ?,l there exists a cycle C_i in G containing f_i and g_i such that P₁, ?,P_k, C₁, ?, C_l are pairwise edge-disjoint. We give upper and lower bounds for g(k, l).     

Mutually orthogonal graph squares

A decomposition ??={G₁, G₂,…,G_s} of a graph G is a partition of the edge set of G into edge‐disjoint subgraphs G₁, G₂,…,G_s. If G_i?H for all i∈{1, 2, …, s}, then ?? is a decomposition of G by H. Two decompositions ??={G₁, G₂, …, G_n} and ?={F₁, F₂,…,F_n} of the complete bipartite graph K_n,n are orthogonal if |E(G_i)∩E(F_j)|=1 for all i,j∈{1, 2, …, n}. A set of decompositions {??₁, ??₂, …, ??_k} of K_{n, n} is a set of k mutually orthogonal graph squares (MOGS) if ??_i and ??_j are orthogonal for all i, j∈{1, 2, …, k} and i≠j. For any bipartite graph G with n edges, N(n, G) denotes the maximum number k in a largest possible set {??₁, ??₂, …, ??_k} of MOGS of K_{n, n} by G. El‐Shanawany conjectured that if p is a prime number, then N(p, P_{p+ 1})=p, where P_{p+ 1} is the path on p+ 1 vertices. In this article, we prove this conjecture. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 369–373, 2009