Inertially arbitrary patterns

An n×n sign pattern matrix A is an inertially arbitrary pattern (IAP) if each non-negative triple (rst) with r+s+t=n is the inertia of a matrix with sign pattern A. This paper considers the n×n(n≥2) skew-symmetric sign pattern S_n with each upper off-diagonal entry positive, the (1,1) entry negative, the (nn) entry positive, and every other diagonal entry zero. We prove that S_n is an IAP.     

Split and balanced colorings of complete graphs

An (r, n)-split coloring of a complete graph is an edge coloring with r colors under which the vertex set is partitionable into r parts so that for each i, part i does not contain K_n in color i. This generalizes the notion of split graphs which correspond to (2, 2)-split colorings. The smallest N for which the complete graph K_N has a coloring which is not (r, n)-split is denoted by ƒ_r(n). Balanced (r,n)-colorings are defined as edge r-colorings of KN such that every subset of [N/r] vertices contains a monochromatic K_n in all colors. Then g_r(n) is defined as the smallest N such that K_N has a balanced (r, n)-coloring. The definitions imply that f_r(n) g_r(n). The paper gives estimates and exact values of these functions for various choices of parameters.     

Chapter 3:inertia preservers

Let Vdenote either the space of n×n hermitian matrices or the space of n×nreal symmetric matrices, Given nonnegative integers r,s,t such that r+S+t=n, let G( r,s,r) denote the set of all matrices in V with inertia (r,s,t). We consider here linear operators on V which map G(r,s,t) into itself.     

Large spaces of symmetric matrices of bounded rank are decomposable

Let k and n be positive integers such that k≤n. Let S_n(F) denote the space of all n×n symmetric matrices over the field F with char F≠2. A subspace L of S_n(F) is said to be a k-subspace if rank A≤k for every AεL.

Now suppose that k is even, and write k=2r. We say a k∥-subspace of S_n(F) is decomposable if there exists in Fⁿ a subspace W of dimension n-r such that x^tAx=0 for every xεWAεL.

We show here, under some mild assumptions on kn and F, that every k∥-subspace of S_n(F) of sufficiently large dimension must be decomposable. This is an analogue of a result obtained by Atkinson and Lloyd for corresponding subspaces of F^m,n.     

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 .     

Equality of higher numerical ranges of matrices and a conjecture of Kippenhahn on Hermitian pencils

Let M_n be the algebra of all n × n complex matrices. For 1 k n, the kth numerical range of A M_n is defined by W_k(A) = (1/k)∑_j^k=1x_j^*Ax_j : x₁, …, x_k is an orthonormal set in ⁿ]. It is known that tr A/n = W_n(A) W_n−1(A) W₁(A). We study the condition on A under which W_m(A) = W_k(A) for some given 1 m < k n. It turns out that this study is closely related to a conjecture of Kippenhahn on Hermitian pencils. A new class of counterexamples to the conjecture is constructed, based on the theory of the numerical range.     

Linear preservers of matrices of rank-2

Let T be a linear operator on the space of all m×n matrices over any field. we prove that if T maps rank-2 matrices to rank-2 matrices then there exist nonsingular matrices U and V such that either T(X)=UXV for all matrices X, or m=n and T(X)=UX^tV for all matrices X where X^t denotes the transpose of X.     

Discriminant preserving linear maps

Consider the n-square matrices over an infiniie field Kas an n²-dimcnsional vector space M( nK). We determine all linear maps Ton M(nK) such that discriminant TX- discriminant Xfor all Xin M(nK)     

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.     

Some peculiar boundary phenomena for extremes of rth nearest neighbor links

Let D_n,r denote the largest rth nearest neighbor link for n points drawn independently and uniformly from the unit d-cube C_d. We show that according as r < d or r>d, the limiting behavior of D_n,r, as n → ∞, is determined by the two-dimensional ‘faces’ respectively one-dimensional ‘edges’ of the boundary of C_d. If d = r, a ‘balance’ between faces and edges occurs. In case of a d-dimensional sphere (instead of a cube) the boundary dominates the asymptotic behavior of D_n,r if d 3 or if d = 2, r 3.     

On an optimal stopping problem of Gusein-Zade

We study the problem of selecting one of the r best of n rankable individuals arriving in random order, in which selection must be made with a stopping rule based only on the relative ranks of the successive arrivals. For each r up to r=25, we give the limiting (as n→∞) optimal risk (probability of not selecting one of the r best) and the limiting optimal proportion of individuals to let go by before being willing to stop. (The complete limiting form of the optimal stopping rule is presented for each r up to r=10, and for r=15, 20 and 25.) We show that, for large n and r, the optical risk is approximately (1−t^*)^r, where t^*≈0.2834 is obtained as the roof of a function which is the solution to a certain differential equation. The optimal stopping rule τ_r,n lets approximately t^*n arrivals go by and then stops ‘almost immediately’, in the sense that τ_r,n/n→t^* in probability as n→∞, r→∞     

Matrices that preserve vectors of fixed sign variation

For each k≥ 0, those nonsingular matrices that transform the set of totally nonzero vectors with k sign variations into (respectively, onto) itself are studied. Necessary and sufficient conditions are provided. The cases k=0,1,2,n-3,n-2,n-1 are completely characterized.     

Permanents of doubly stochastic matrices with fixed zero pattern

The doubly stochastic matrices with a given zero pattern which are closest in Euclidean norm to J_nn, the matrix with each entry equal to 1/n, are identified. If the permanent is restricted to matrices having a given zero pattern confined to one row or to one column, the permanent achieves a local minimum at those matrices with that zero pattern which are closest to J_nn. This need no longer be true if the zeros lie in more than one row or column.     

ContributionsChromatic Ramsey numbers

Suppose G is a graph. The chromatic Ramsey number r_c(G) of G is the least integer m such that there exists a graph F of chromatic number m for which the following is true: for any 2-colouring of the edges of F there is a monochromatic subgraph isomorphic to G. Let M_n = min[r_c(G): χ(G) = n]. It was conjectured by Burr et al. (1976) that M_n = (n − 1)² + 1. This conjecture has been confirmed previously for n 4. In this paper, we shall prove that the conjecture is true for n = 5. We shall also improve the upper bounds for M₆ and M₇.     

On the quasi-stationary distribution of a stochastic Ricker model

We model the evolution of a single-species population by a size-dependent branching process Z_t in discrete time. Given that Z_t = n the expected value of Z_t+1 may be written nexp(r − γn) where r> 0 is a growth parameter and γ > 0 is an (inhibitive) environmental parameter. For small values of γ the short-term evolution of the normed process γZ_t follows the deterministic Ricker model closely. As long as the parameter r remains in a region where the number of periodic points is finite and the only bifurcations are the period-doubling ones (r in the beginning of the bifurcation sequence), the quasi-stationary distribution of γZ_t is shown to converge weakly to the uniform distribution on the unique attracting or weakly attracting periodic orbit. The long-term behavior of γZ_t differs from that of the Ricker model, however: γZ_t has a finite lifetime a.s. The methods used rely on the central limit theorem and Markov's inequality as well as dynamical systems theory.     

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.     

Stability of Periodic Orbits and Return Trajectories of Continuous Multi-valued Maps on Intervals

Let I be a compact interval of real axis R, and(I, H) be the metric space of all nonempty closed subintervals of I with the Hausdorff metric H and f : I → I be a continuous multi-valued map. Assume that Pn =(x_0, x_1,..., xn) is a return tra jectory of f and that p ∈ [min Pn, max Pn] with p ∈ f(p). In this paper, we show that if there exist k(≥ 1) centripetal point pairs of f(relative to p)in {(x_i; x_i+1) : 0 ≤ i ≤ n-1} and n = sk + r(0 ≤ r ≤ k-1), then f has an R-periodic orbit, where R = s + 1 if s is even, and R = s if s is odd and r = 0, and R = s + 2 if s is odd and r 0. Besides,we also study stability of periodic orbits of continuous multi-valued maps from I to I.     

Zero-term rank preservers

We obtain characterizations of those linear operators that preserve zero-term rank on the m×n matrices over antinegative semirings. That is, a linear operator T preserves zero-term rank if and only if it has the form T(X)=P(B∘X)Q, where P, Q are permutation matrices and B∘X is the Schur product with B whose entries are all nonzero and not zero-divisors.     

A note on rank-additivity

A new criterion is given for rank additivity of a collection of m × n complex matrices.