On a property specific to the tent map

Let a set {X_λ; λ  Λ} of subspaces of a topological space X be a cover of X. Mathematical conditions are proposed for each subspace X_λ to define a map g_Xλ:X_λ→X which has the following property specific to the tent map known in the baker’s transformation. Namely, for any infinite sequence ω₀, ω₁, ω₂, … of X_λ, λ  Λ, we can find an initial point x₀  ω₀ such that g_ω0(x₀)ω₁,g_ω1(g_ω0(x₀))ω₂,…. The conditions are successfully applied to a closed cover of a weak self-similar set.     

A theorem of the alternatives for the equation Ax + B|x| = b

The following theorem is proved: given square matrices A, D of the same size, D nonnegative, then either the equation Ax + B|x| = b has a unique solution for each B with |B| ≤ D and for each b, or the equation Ax + B₀|x| = 0 has a nontrivial solution for some matrix B₀ of a very special form, |B₀| ≤ D; the two alternatives exclude each other. Some consequences of this result are drawn. In particular, we define a λ to be an absolute eigenvalue of A if |Ax| = λ|x| for some x ≠ 0, and we prove that each square real matrix has an absolute eigenvalue.     

On the extreme eigenvalues of hermitian (block) toeplitz matrices

We are concerned with the behavior of the minimum (maximum) eigenvalue λ₀⁽ⁿ⁾ (λ_n⁽ⁿ⁾) of an (n + 1) × (n + 1) Hermitian Toeplitz matrix T_n(ƒ) where ƒ is an integrable real-valued function. Kac, Murdoch, and Szegö, Widom, Parter, and R. H. Chan obtained that λ₀⁽ⁿ⁾ — min ƒ = O(1/n^2k) in the case where ƒ C^2k, at least locally, and ƒ — inf ƒ has a zero of order 2k. We obtain the same result under the second hypothesis alone. Moreover we develop a new tool in order to estimate the extreme eigenvalues of the mentioned matrices, proving that the rate of convergence of λ₀⁽ⁿ⁾ to inf ƒ depends only on the order ρ (not necessarily even or integer or finite) of the zero of ƒ — inf ƒ. With the help of this tool, we derive an absolute lower bound for the minimal eigenvalues of Toeplitz matrices generated by nonnegative L¹ functions and also an upper bound for the associated Euclidean condition numbers. Finally, these results are extended to the case of Hermitian block Toeplitz matrices with Toeplitz blocks generated by a bivariate integrable function ƒ.     

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ℓ.     

A two-sided estimate in the Hsu-Robbins-Erdös law of large numbers

Let X₁, X₂, … be independent identically distributed random variables. Then, Hsu and Robbins (1947) together with Erdös (1949, 1950) have proved that

,

if and only if E[X²₁] < ∞ and E[X₁] = 0. We prove that there are absolute constants C₁, C₂ (0, ∞) such that if X₁, X₂, … are independent identically distributed mean zero random variables, then

c₁λ⁻² E[X₁²·1_{|X1|λ}]S(λ)C₂λ⁻² E[X₁²·1_{|X1|λ}]

,

for every λ > 0.     

Eigenvalue interlacing and weight parameters of graphs

Eigenvalue interlacing is a versatile technique for deriving results in algebraic combinatorics. In particular, it has been successfully used for proving a number of results about the relation between the (adjacency matrix or Laplacian) spectrum of a graph and some of its properties. For instance, some characterizations of regular partitions, and bounds for some parameters, such as the independence and chromatic numbers, the diameter, the bandwidth, etc., have been obtained. For each parameter of a graph involving the cardinality of some vertex sets, we can define its corresponding weight parameter by giving some “weights” (that is, the entries of the positive eigenvector) to the vertices and replacing cardinalities by square norms. The key point is that such weights “regularize” the graph, and hence allow us to define a kind of regular partition, called “pseudo-regular,” intended for general graphs. Here we show how to use interlacing for proving results about some weight parameters and pseudo-regular partitions of a graph. For instance, generalizing a well-known result of Lovász, it is shown that the weight Shannon capacity Θ^* of a connected graph Γ, with n vertices and (adjacency matrix) eigenvalues λ₁ > λ₂ … λ_n, satisfies

where Θ is the (standard) Shannon capacity and v is the positive eigenvector normalized to have smallest entry 1. In the special case of regular graphs, the results obtained have some interesting corollaries, such as an upper bound for some of the multiplicities of the eigenvalues of a distance-regular graph. Finally, some results involving the Laplacian spectrum are derived.     

Error bounds on the power method for determining the largest eigenvalue of a symmetric, positive definite matrix

Let A be a positive definite, symmetric matrix. We wish to determine the largest eigenvalue, λ₁. We consider the power method, i.e. that of choosing a vector v₀ and setting v_k = A^kv₀; then the Rayleigh quotients R_k = (Av_k, v_k)/(v_k, v_k) usually converge to λ₁ as k → ∞ (here (u, v) denotes their inner product). In this paper we give two methods for determining how close R_k is to λ₁. They are both based on a bound on λ₁ − R_k involving the difference of two consecutive Rayleigh quotients and a quantity ω_k. While we do not know how to directly calculate ω_k, we can given an algorithm for giving a good upper bound on it, at least with high probability. This leads to an upper bound for λ₁ − R_k which is proportional to (λ₂/λ₁)^2k, which holds with a prescribed probability (the prescribed probability being an arbitrary δ > 0, with the upper bound depending on δ).     

Constructions of (q, K, λ, t, Q) almost difference families

The concept of a (q, k, λ, t) almost difference family (ADF) has been introduced and studied by C. Ding and J. Yin as a useful generalization of the concept of an almost difference set. In this paper, we consider, more generally, (q, K, λ, t, Q)-ADFs, where K = {k₁, k₂, ..., k_r} is a set of positive integers and Q = (q₁, q₂,..., q_r) is a given block-size distribution sequence. A necessary condition for the existence of a (q, K, λ, t, Q)-ADF is given, and several infinite classes of (q, K, λ, t, Q)-ADFs are constructed.     

A simple bound for the remainder of the neumann series in the case of a self-adjoint compact operator

We consider the functional equation of the second kind \gf − λK\gf = f with K a compact self-adjoint linear operator on a Hilbert space: a Fredholm integral equation of the second kind, for example. We establish the simple bound where λ is any regular value of K; ø is the solution of the equation corresponding to λ; λ₁ is the characteristic value of K smallest in absolute value; and N = 0, 1, 2, .... For \s|λ\s| < \s|λ₁\s|, this is an estimate for the remainder of the partial sums of the Neumann series.     

Flawless 0-sequences and Hilbert functions of Cohen-Macaulay integral domains

Let A = A₀A₁ be a commutative graded ring such that (i) A₀ = k a field, (ii) A = k[A₁] and (iii) dim_k A₁ < ∞. It is well known that the formal power series ∑^∞_{n = 0} (dim_kA_n)λ ⁿ is of the form (h₀ + h₁λ + + h_sλ^s)/(1 − λ)^dimA with each h_iε . We are interested in the sequence (h₀, h₁,…,h_s), called the h-vector of A, when A is a Cohen–Macaulay integral domain. In this paper, after summarizing fundamental results (Section 1), we study h-vectors of certain Gorenstein domains (Section 2) and find some examples of h-vectors arising from integrally closed level domains (Sections 3 and 4).     

3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects

We present a new data structure for a set of n convex simply-shaped fat objects in the plane, and use it to obtain efficient and rather simple solutions to several problems including (i) vertical ray shooting—preprocess a set of n non-intersecting convex simply-shaped flat objects in 3-space, whose xy-projections are fat, for efficient vertical ray shooting queries, (ii) point enclosure—preprocess a set C of n convex simply-shaped fat objects in the plane, so that the k objects containing a query point p can be reported efficiently, (iii) bounded-size range searching— preprocess a set C of n convex fat polygons, so that the k objects intersecting a “not-too-large” query polygon can be reported efficiently, and (iv) bounded-size segment shooting—preprocess a set C as in (iii), so that the first object (if exists) hit by a “not-too-long” oriented query segment can be found efficiently. For the first three problems we construct data structures of size O(λ_s(n)log³n), where s is the maximum number of intersections between the boundaries of the (xy-projections) of any pair of objects, and λ_s(n) is the maximum length of (n, s) Davenport-Schinzel sequences. The data structure for the fourth problem is of size O(λ_s(n)log²n). The query time in the first problem is O(log⁴n), the query time in the second and third problems is O(log³n + klog²n), and the query time in the fourth problem is O(log³n).

We also present a simple algorithm for computing a depth order for a set as in (i), that is based on the solution to the vertical ray shooting problem. (A depth order for , if exists, is a linear order of , such that, if K₁, K₂ and K₁ lies vertically above K₂, then K₁ precedes K₂.) Unlike the algorithm of Agarwal et al. (1995) that might output a false order when a depth order does not exist, the new algorithm is able to determine whether such an order exists, and it is often more efficient in practical situations than the former algorithm.     

The kernels of irreducible representations of the general linear group

A derivation for the kernel of the irreducible representation T_(λ) of the general linear group GL_n(C) is given. This is then applied to the problem of determining necessary and sufficient conditions under which T_(λ)(A) = T_(λ)(B), where A and B are linear transformations, not necessarily invertible. Finally, conditions are obtained under which normality of T_(λ)(A) implies normality of A.     

The space localization of unbounded boundary perturbations in nonlinear heat conduction with transfer

We consider the nonlinear parabolic equation u_t = (k(u)u_x)_x + b(u)_x, where u = u(x, t, x ε R¹, t > 0; k(u) ≥ 0, b(u) ≥ 0 are continuous functions as u ≥ 0, b (0) = 0; k, b > 0 as u > 0. At t = 0 nonnegative, continuous and bounded initial value is prescribed. The boundary condition u(0, t) = Ψ(t) is supposed to be unbounded as t → +∞. In this paper, sufficient conditions for space localization of unbounded boundary perturbations are found. For instance, we show that nonlinear equation u_t = (uⁿu_x)_x + (u^β)_x, n ≥ 0, β >; n + 1, exhibits the phenomenon of “inner boundedness,” for arbitrary unbounded boundary perturbations.     

Spectra of multilevel toeplitz matrices: Advanced theory via simple matrix relationships

We consider the eigenvalue and singular-value distributions for m-level Toeplitz matrices generated by a complex-valued periodic function ƒ of m real variables. We show that familiar formulations for ƒ L_∞ (due to Szegő and others) can be preserved so long as f L₁, and what is more, with G. Weyl's definitions just a bit changed. In contrast to other approaches, the one we follow is based on simple matrix relationships.     

On the degree of regularity of some equations

In this paper we investigate the behaviour of the solutions of equations Σ_I=1ⁿ a_ix_i = b, where Σ_i=1ⁿ, a_i = 0 and b ≠ 0, with respect to colorings of the set N of positive integers. It turns out that for any b ≠ 0 there exists an 8-coloring of N, admitting no monochromatic solution of x₃ − x₂ = x₂ − x₁ + b. For this equation, for b odd and 2-colorings, only an odd-even coloring prevents a monochromatic solution. For b even and 2-colorings, always monochromatic solutions can be found, and bounds for the corresponding Rado numbers are given. If one imposes the ordering x₁ < x₂ < x₃, then there exists already a 4-coloring of N, which prevents a monochromatic solution of x₃ − x₂ = x₂ − x₁ + b, where b ε N.     

Graphs for which the least eigenvalue is minimal, I

Let G be a connected graph whose least eigenvalue λ(G) is minimal among the connected graphs of prescribed order and size. We show first that either G is complete or λ(G) is a simple eigenvalue. In the latter case, the sign pattern of a corresponding eigenvector determines a partition of the vertex set, and we study the structure of G in terms of this partition. We find that G is either bipartite or the join of two graphs of a simple form.     

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.     

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.