First passage time for some stationary processes

For a 1-dependent stationary sequence {X_n} we first show that if u satisfies p₁=p₁(u)=P(X₁>u)0.025 and n>3 is such that 88np₁³1, then

P{max(X₁,…,X_n)u}=ν·μⁿ+O{p₁³(88n(1+124np₁³)+561)}, n>3,

where

ν=1−p₂+2p₃−3p₄+p₁²+6p₂²−6p₁p₂,μ=(1+p₁−p₂+p₃−p₄+2p₁²+3p₂²−5p₁p₂)⁻¹

with

p_k=p_k(u)=P{min(X₁,…,X_k)>u}, k1

and

|O(x)||x|.

From this result we deduce, for a stationary T-dependent process with a.s. continuous path {Y_s}, a similar, in terms of P{max_0skTY_s<u}, k=1,2 formula for P{max_0stY_su}, t>3T and apply this formula to the process Y_s=W(s+1)−W(s), s0, where {W(s)} is the Wiener process. We then obtain numerical estimations of the above probabilities.     

Maximal IM-unextendable graphs

A graph G is maximal IM-unextendable if G is not induced matching extendable and, for every two nonadjacent vertices x and y, G+xy is induced matching extendable. We show in this paper that a graph G is maximal IM-unextendable if and only if G is isomorphic to M_r(K_s(K_n1K_n2K_nt)), where M_r is an induced matching of size r, r1, t=s+2, and each n_i is odd.     

A note on linearization of actions of finitely semisimple Hopf algebras on local algebras

Let H be a Hopf algebra over a field k and let H A → A, h a → h.a, be an action of H on a commutative local Noetherian kalgebra (A, m). We say that this action is linearizable if there exists a minimal system x₁, …, x_n of generators of the maximal ideal m such that h.x_i ε kx₁ + …+ kx_n for all h ε H and i = 1, …, n. In the paper we prove that the actions from a certain class are linearizable (see Theorem 4), and we indicate some consequences of this fact.     

The smallest degree sum that yields potentially kCℓ-graphic sequences

Gould et al. (Combinatorics, Graph Theory and Algorithms, Vol. 1, 1999, pp. 387–400) considered a variation of the classical Turán-type extremal problems as follows: For a given graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(H,n) has a realization G containing H as a subgraph. In this paper, for given integers k and ℓ, ℓ7 and 3kℓ, we completely determine the smallest even integer σ(_kC_ℓ,n) such that each n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(_kC_ℓ,n) has a realization G containing a cycle of length r for each r, krℓ.     

On meromorphic solutions of a certain type of nonlinear differential equations

We consider transcendental meromorphic solutions with N(r,f) = S(r,f) of the following type of nonlinear differential equations:f~n + Pn-2(f) = p1(z)e~(α1(z)) +p2(z)e~(α2(z)),where n≥ 2 is an integer, Pn-2(f) is a differential polynomial in f of degree not greater than n-2 with small functions of f as its coefficients, p1(z), p2(z) are nonzero small functions of f, and α1(z), α2(z)are nonconstant entire functions. In particular, we give out the conditions for ensuring the existence of meromorphic solutions and their possible forms of the above equation. Our results extend and improve some known results obtained most recently.     

Embeddings of the base and bundle isomorphisms

Let π_i :E_i→M, i=1,2, be oriented, smooth vector bundles of rank k over a closed, oriented n-manifold with zero sections s_i :M→E_i. Suppose that U is an open neighborhood of s₁(M) in E₁ and F :U→E₂ a smooth embedding so that π₂Fs₁ :M→M is homotopic to a diffeomorphism f. We show that if k>[(n+1)/2]+1 then E₁ and the induced bundle f^*E₂ are isomorphic as oriented bundles provided that f have degree +1; the same conclusion holds if f has degree −1 except in the case where k is even and one of the bundles does not have a nowhere-zero cross-section. For n≡0(4) and [(n+1)/2]+1<kn we give examples of nonisomorphic oriented bundles E₁ and E₂ of rank k over a homotopy n-sphere with total spaces diffeomorphic with orientation preserved, but such that E₁ and f^*E₂ are not isomorphic oriented bundles. We obtain similar results and counterexamples in the more difficult limiting case where k=[(n+1)/2]+1 and M is a homotopy n-sphere.     

A special k-coloring for a connected k-chromatic graph

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices x_o and x_p in any color class there exist vertices x₁, x₂, …, x_p-1 of the same class with dist(x_i, x_i+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.

We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1.     

An extremal problem on potentially Kr,s-graphic sequences

We consider a variation of a classical Turán-type extremal problem (F. Chung, R. Graham, Erd s on Graphs: His Legacy of Unsolved Problems, AK Peters Ltd., Wellesley, 1998, Chapter 3) as follows: Determine the smallest even integer σ(K_r,s,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(K_r,s,n) is potentially K_r,s-graphic, where K_r,s is a r×s complete bipartite graph, i.e., π has a realization G containing K_r,s as its subgraph. In this paper, we first give sufficient conditions for a graphic sequence being potentially K_r,s-graphic, and then we determine σ(K_r,r,n) for r=3,4.     

Almost perfect matchings in random uniform hypergraphs

We consider the following model H_r(n, p) of random r-uniform hypergraphs. The vertex set consists of two disjoint subsets V of size | V | = n and U of size | U | = (r − 1)n. Each r-subset of V × (_r−1^U) is chosen to be an edge of H ε H_r(n, p) with probability p = p(n), all choices being independent. It is shown that for every 0 < < 1 if P = (C ln n)/n^r−1 with C = C() sufficiently large, then almost surely every subset V₁ V of size | V₁ | = (1 − )n is matchable, that is, there exists a matching M in H such that every vertex of V₁ is contained in some edge of M.     

Aspects of semiorders within interval orders

Let s_k(n) be the largest integer such that every n-point interval order with no antichain of more than k points includes an s_k(n)-point semiorder. When k = 1, s₁(n) = n since all interval orders with no two-point antichains are chains. Given (c₁,...,c₅) = (1, 2, 3, 4), it is shown that s₂(n) = c_n for n 4, s₃(n) = c_n for n 5, and for all positive n, s₂ (n+4) =s₂(n)+3, s₃(n+5) = s₃(n)+3. Hence s₂ has a repeating pattern of length 4 [1, 2, 3, 3; 4, 5, 6, 6; 7, 8, 9, 9;...], and s₃ has a repeating pattern of length 5 [1, 2, 3, 3, 4; 4, 5, 6, 6, 7; 7, 8, 9, 9, 10;...].

Let s(n) be the largest integer such that every n-point interval order includes an s(n)-point semiorder. It was proved previously that for even n from 4 to 14, and that s(17) = 9. We prove here that s(15) = s(16) = 9, so that s begins 1, 2, 3, 3, 4, 4,..., 8, 8, 9, 9, 9. Since s(n)/n→0, s cannot have a repeating pattern.     

Intersections of nest algebras in finite dimensions

If are maximal nests on a finite-dimensional Hilbert space H, the dimension of the intersection of the corresponding nest algebras is at least dim H. On the other hand, there are three maximal nests whose nest algebras intersect in the scalar operators. The dimension of the intersection of two nest algebras (corresponding to maximal nests) can be of any integer value from n to n(n+1)/2, where n=dim H. For any two maximal nests there exists a basis {f₁,f₂,…,f_n} of H and a permutation π such that and where M_i=  span{f₁,f₂,…,f_i} and N_i= span{f_π(1),f_π(2),…,f_π(i)}. The intersection of the corresponding nest algebras has minimum dimension, namely dim H, precisely when π(j)=n−j+1,1jn. Those algebras which are upper-triangular matrix incidence algebras, relative to some basis, can be characterised as intersections of certain nest algebras.     

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .     

ContributionsFinitary bases and formal generating functions

Let k be a nonzero, commutative ring with 1, and let R be a k-algebra with a countably-infinite ordered free k-basis B = [p_n: n 0]. We characterize and analyze those bases from which one can construct a k-algebra of ‘formal B-series’ of the form f=∑c_n p_n, with c_n ε k, showing inter alia that many classical polynomial bases fail to have this property.     

Convex 4-valent polytopes

Let {p_k}_k≥3 be a sequence of nonnegative integers which satisfies 8 + Σ_k≥3 (k-4) p_k = 0 and p₄ ≥ p₃. Then there is a convex 4-valent polytope P in E³ such that P has exactly p_k k-gons as faces. The inequality p₄ ≥ p₃ is the best possible in the sense that for c < 1 there exist sequences that are not 4-realizable that satisfy both 8 + Σ_{k ≥3} (k - 4) p_k = 0 and p₄ > cp₃. When Σ_{k ≥ 5} p_k ≠ 1, one can make the stronger statement that the sequence {p_k} is 4-reliazable if it satisfies 8 + Σ_{k ≥ 3} (k - 4) p_k = 0 and p₄ ≥ 2Σ_{k ≥ 5} p_k + max{k ¦ p_k ≠ 0}.     

A sufficient and necessary condition for an OWA bag mapping having the self-identity

A mapping ƒ : _n=1^∞Iⁿ → I is called a bag mapping having the self-identity if for every (x₁,…,x_n) ε _i=1^∞Iⁿ we have (1) ƒ(x₁,…,x_n) = ƒ(x_i1,…,x_in) for any arrangement (i₁,…,i_n) of {1,…,n}; monotonic; (3) ƒ(x₁,…,x_n, ƒ(x₁,…,x_n)) = ƒ(x₁,…,x_n). Let {ω_i,n : I = 1,…,n;n = 1,2,…} be a family of non-negative real numbers satisfying Σ_i=1ⁿω_i,n = 1 for every n. Then one calls the mapping ƒ : _i=1^∞Iⁿ → I defined as follows an OWA bag mapping: for every (x₁,…,x_n) ε _i=1^∞Iⁿ, ƒ(x₁,…,x_n) = Σ_i=1ⁿω_i,ny_i, where y_i is the it largest element in the set {x₁,…,x_n}. In this paper, we give a sufficient and necessary condition for an OWA bag mapping having the self-identity.     

On oscillation of second order neutral type delay differential equations

Oscillation criteria are obtained by using the so called H-method for the second order neutral type delay differential equations of the form

(r(t)ψ(x(t))z^′(t))^′+q(t)f(x(σ(t)))=0, tt₀,

where z(t)=x(t)+p(t)x(τ(t)), r, p, q, τ, σ, C([t₀,∞),R) and f,ψC(R,R).

The results of the paper contains several results obtained previously as special cases. Furthermore, we are also able to fix an error in a recent paper related to the oscillation of second order nonneutral delay differential equations.     

Subsets of an interval whose product is a power

We form squares from the product of integers in a short interval [n, n + t_n], where we include n in the product. If p is prime, p|n, and (₂^p) > n, we prove that p is the minimum t_n. If no such prime exists, we prove t_n √5n when n> 32. If n = p(2p − 1) and both p and 2p − 1 are primes, then t_n = 3p> 3 √n/2. For n(n + u) a square > n², we conjecture that a and b exist where n < a < b < n + u and nab is a square (except n = 8 and N = 392). Let g₂(n) be minimal such that a square can be formed as the product of distinct integers from [n, g₂(n)] so that no pair of consecutive integers is omitted. We prove that g₂(n) 3n − 3, and list or conjecture the values of g₂(n) for all n. We describe the generalization to kth powers and conjecture the values for large n.     

Length-bounded disjoint paths in planar graphs

The following problem is considered: given: an undirected planar graph G=(V,E) embedded in , distinct pairs of vertices {r₁,s₁},…,{r_k,s_k} of G adjacent to the unbounded face, positive integers b₁,…,b_k and a function ; find: pairwise vertex-disjoint paths P₁,…,P_k such that for each i=1,…,k, P_i is a r_i−s_i-path and the sum of the l-length of all edges in P_i is at most b_i. It is shown that the problem is NP-hard in the strong sense. A pseudo-polynomial-time algorithm is given for the case of k=2.     

The game of n-times nim

The following game is considered. The first player can take any number of stones, but not all the stones, from a single pile of stones. After that, each player can take at most n-times as many as the previous one. The player first unable to move loses and his opponent wins. Let f₁,f₂,… be an initial sequence of stones in increasing order, such that the second player has a winning strategy when play begins from a pile of size f_i. It is proved that there exist constants c=c(n) and k₀=k₀(n) such that f_k+1=f_k+f_k−c for all k>k₀, and lim_n→∞ c(n)/(nlogn)=1.     

On the Equation n_1n_2= n_3n_4 Restricted to Factor Closed Sets

We study the number of solutions N(B,F) of the diophantine equation n_1n_2 = n_3 n_4,where 1 ≤ n_1 ≤ B,1 ≤ n_3 ≤ B,n_2,n_4 ∈ F and F[1,B] is a factor closed set.We study more particularly the case when F={m = p_1~(ε1)···p_k~(εk),ε_j∈{0,1},1 ≤ j ≤ k},p_1,...,p_k being distinct prime numbers.