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 the occupation time of an iterated process having no local time

We study the asymptotic behaviour of the occupation time process ∫^t₀ I_A(W₁(L₂(s)))ds, t 0, where W₁ is a standard Wiener process and L₂ is a Wiener local time process at zero that is independent from W₁. We prove limit laws, as well as almost sure upper and lower class theorems. Possible extensions of the obtained results are also discussed.     

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.     

Full quadrature sums for pth powers of polynomials with Freud weights

In this paper, we provide a solution of the quadrature sum problem of R. Askey for a class of Freud weights. Let r> 0, b (− ∞, 2]. We establish a full quadrature sum estimate

1 p < ∞, for every polynomial P of degree at most n + rn^1/3, where W² is a Freud weight such as exp(−¦x¦), > 1, λ_jn are the Christoffel numbers, x_jn are the zeros of the orthonormal polynomials for the weight W², and C is independent of n and P. We also prove a generalisation, and that such an estimate is not possible for polynomials P of degree M = m(n) if m(n) = n + ξ_nn^1/3, where ξ_n → ∞ as n → ∞. Previous estimates could sum only over those x_jn with ¦x_jn¦ σx_1n, some fixed 0 < σ < 1.     

Least domination in a graph

The least domination number γ_L of a graph G is the minimum cardinality of a dominating set of G whose domination number is minimum. The least point covering number _L of G is the minimum cardinality of a total point cover (point cover including every isolated vertex of G) whose total point covering number is minimum. We prove a conjecture of Sampathkumar saying that in every connected graph of order n 2. We disprove another one saying that γ_{L L} in every graph but instead of it, we establish the best possible inequality . Finally, in relation with the minimum cardinality γ_t of a dominating set without isolated vertices (total dominating set), we prove that the ratio γ_L/γ_t can be in general arbitrarily large, but remains bounded by if we restrict ourselves to the class of trees.     

Homogenization of Elliptic Problems with Neumann Boundary Conditions in Non-smooth Domains

We consider a family of second-order elliptic operators {L_ε} in divergence form with rapidly oscillating and periodic coefficients in Lipschitz and convex domains in R~n. We are able to show that the uniform W~(1,p) estimate of second order elliptic systems holds for 2n/(n+1)-δ p 2n/(n-1)+ δ where δ 0 is independent of ε and the ranges are sharp for n = 2, 3. And for elliptic equations in Lipschitz domains, the W~(1,p) estimate is true for 3/2-δ p 3 + δ if n ≥ 4, similar estimate was extended to convex domains for 1 p ∞.     

The consistency of a non-linear least squares estimator from diffusion processes

Consider the following Itô stochastic differential equation dX(t) = ƒ(θ⁰, X(t)) dt + dW(t), where (W(t), t 0), is a standard Wiener process in R^N. On the basis of discrete data 0 = t₀ < t₁ < …<t_n = T; X(t₁),...,X(t_n) we would like to estimate the parameter θ⁰. We shall define the least squares estimator and show that under some regularity conditions, is strongly consistent.     

Flat portions on the boundary of the numerical ranges of certain Toeplitz matrices

We give criterions for a flat portion to exist on the boundary of the numerical range of a matrix. A special type of Teoplitz matrices with flat portions on the boundary of its numerical range are constructed. We show that there exist 2 × 2 nilpotent matrices A₁,A₂, an n  × n nilpotent Toeplitz matrix N_n, and an n  × n cyclic permutation matrix S_n(s) such that the numbers of flat portions on the boundaries of W(A₁⊕N_n) and W(A₂⊕S_n(s)) are, respectively, 2(n - 2) and 2n.     

Limiting values of the variance and the moments of the dimension of a sum or intersection of random vector subspaces

Let W be an n-dimensional vector space over a field F; for each positive integer m, let the m-tuples (U₁, …, U_m) of vector subspaces of W be uniformly distributed; and consider the statistics X_m,1 dim_F(∑_i=1^m U_i) and X_m,2 dim_F (∩_i=1^m U_i). If F is finite of cardinality q, we determine lim E(X_m,1^k), and lim E(X_m,2^k), and hence, lim var(X_m,1) and lim var(X_m,2), for any k > 0, where the limits are taken as q → ∞ (for fixed n). Further, we determine whether these, and other related, limits are attained monotonically. Analogous issues are also addressed for the case of infinite F.     

The W-convexity and normal structure in banach spaces

Let X be a Banach space, S(X) - x ε X : #x02016; = 1 be the unit sphere of X.The parameter, modulus of W^*-convexity, W^*(ε) = inf <(x − y)/2, f_x> : x, y S(X), x − y ≥ ε, f_x Δ_x , where 0 ≤ ε ≤ 2 and Δ_x S(X^*) be the set of norm 1 supporting functionals of S(X) at x, is investigated_ The relationship among uniform nonsquareness, uniform normal structure and the parameter W^*(ε) are studied, and a known result is improved. The main result is that for a Banach space X, if there is ε, where 0 < ε < 1/2, such that W^*(1 + ε) > ε/2 where W^*(1 + ε) = lim_→ε W^* (1 + ), then X has normal structure.     

An efficient algorithm for the parametric resource allocation problem

The parametric resource allocation problem asks to minimize the sum of separable single-variable convex functions containing a parameter λ, Σ_{i = 1}ⁿ (ƒ_i(x_i + λg_i(x_i)), under simple constraints Σ_{i = 1}ⁿ x_i = M, l_i≤x_i≤u_i and x_i: nonnegative integers for i = 1, 2, …, n, where M is a given positive integer, and l_i and u_i are given lower and upper bounds on x_i. This paper presents an efficient algorithm for computing the sequence of all optimal solutions when λ is continuously changed from 0 to ∞. The required time is O(G√Mlog² n + n log n + n log(M/n)), where G = Σ_{i = 1}ⁿ u_i − Σ_{i = 1n} l_i and an evaluation of ƒ_i(·) or g_i(·) is assumed to be done in constant time.     

Extremal properties of strong quadrature weights and maximal mass results for truncated strong moment problems

A bisequence of complex numbers {μ_n}_−∞^∞ determines a strong moment functional satisfying L[xⁿ] = μ_n. If is positive-definite on a bounded interval (a,b) R{0}, then has an integral representation , n=0, ±1, ±2,…, and quadrature rules {w_ni,x_ni} exist such that μ_k = ∑_i=i^n_ns_ni^kw_ni. This paper is concerned with establishing certain extremal properties of the weights w_ni and using these properties to obtain maximal mass results satisfied by distributions ψ(x) representing when only a finite bisequence of moments {μ_k}_k=−nⁿ⁻¹ is given.     

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.     

The thermal equilibrium state of semiconductor devices

The thermal equilibrium state of two oppositely charged gases confined to a bounded domain , m = 1,2 or m = 3, is entirely described by the gases' particle densities p, n minimizing the total energy (p, n). it is shown that for given P, N > 0 the energy functional admits a unique minimizer in {(p, n) ε L²(Ω) x L ²(Ω) : p, n ≥ 0, _Ωp = P, _Ωn = N} and that p, n ε C(Ω) ∩ L^∞(Ω).

The analysis is applied to the hydrodynamic semiconductor device equations. These equations in general possess more than one thermal equilibrium solution, but only the unique solution of the corresponding variational problem minimizes the total energy. It is equivalent to prescribe boundary data for electrostatic potential and particle densities satisfying the usual compatibility relations and to prescribe V^e and P, N for the variational problem.     

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 .     

Resolutions of Stanley-Reisner rings and Alexander duality

Associated to any simplicial complex Δ on n vertices is a square-free monomial ideal I_Δ in the polynomial ring A = k[x₁, …, x_n], and its quotient k[Δ] = A/I_Δ known as the Stanley-Reisner ring. This note considers a simplicial complex Δ^* which is in a sense a canonical Alexander dual to Δ, previously considered in [1, 5]. Using Alexander duality and a result of Hochster computing the Betti numbers dim_k Tor_i^A (k[Δ],k), it is shown (Proposition 1) that these Betti numbers are computable from the homology of links of faces in Δ^*. As corollaries, we prove that I_Δ has a linear resolution as A-module if and only if Δ^* is Cohen-Macaulay over k, and show how to compute the Betti numbers dim_k Tor_i^A (k[Δ],k) in some cases where Δ^* is wellbehaved (shellable, Cohen-Macaulay, or Buchsbaum). Some other applications of the notion of shellability are also discussed.     

A shortcut to asymptotics for orthogonal polynomials

We consider the asymptotic behavior of the ratios q_n+1(z)/q_n(z) of polynomials orthonormal with respect to some positive measure μ. Let the recurrence coefficients _n and β_n converge to 0 and , respectively. Then, q_n+1(z)/q_n(z) Φ(z),for n→∞ locally uniformly for , where Φ maps conformally onto the exterior of the unit disc (Nevai (1979)). We provide a new and direct proof for this and some related results due to Nevai, and apply it to convergence acceleration of diagonal Padé approximants.     

ContributionsSign-balanced covering matrices

A q × n array with entries from 0, 1,…,q − 1 is said to form a difference matrix if the vector difference (modulo q) of each pair of columns consists of a permutation of [0, 1,… q − 1]; this definition is inverted from the more standard one to be found, e.g., in Colbourn and de Launey (1996). The following idea generalizes this notion: Given an appropriate δ (-[−1, 1]^t, a λq × n array will be said to form a (t, q, λ, Δ) sign-balanced matrix if for each choice C₁, C₂,…, C_t of t columns and for each choice = (₁,…,_t) Δ of signs, the linear combination ∑_j=1^t _jC_j contains (mod q) each entry of [0, 1,…, q − 1] exactly λ times. We consider the following extremal problem in this paper: How large does the number k = k(n, t, q, λ, δ) of rows have to be so that for each choice of t columns and for each choice (₁, …, _t) of signs in δ, the linear combination ∑_j=1^t _jC_j contains each entry of [0, 1,…, q t- 1] at least λ times? We use probabilistic methods, in particular the Lovász local lemma and the Stein-Chen method of Poisson approximation to obtain general (logarithmic) upper bounds on the numbers k(n, t, q, λ, δ), and to provide Poisson approximations for the probability distribution of the number W of deficient sets of t columns, given a random array. It is proved, in addition, that arithmetic modulo q yields the smallest array - in a sense to be described.     

An extended result of Kleitman and Saks concerning binary trees

In a recent paper, D.J. Kleitman and M.E. Saks gave a proof of Huang's conjecture on alphabetic binary trees.

Given a set E = {e_i}, I = 0, 1, 2, …, m and assigned positive weights to its elements and supposing the elements are indexed such that w(e₀) ≤ w(e₁) ≤ … ≤w (e_m), where w(e_i) is the weight of e_i, we call the following sequence E^* a ‘saw-tooth’ sequence

E^*=(e₀,e_m,e₁,…,e_j,e_m−j,…).

Huang's conjecture is: E^* is the most expensive sequence for alphabetic binary trees. This paper shows that this property is true for the L-restricted alphabetic binary trees, where L is the maximum length of the leaves and log₂(m + 1) ≤L≤m.     

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.