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.     

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→∞     

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.     

Partitioning Boolean lattices into antichains

Let f(n) be the smallest integer t such that a poset obtained from a Boolean lattice with n atoms by deleting both the largest and the smallest elements can be partitioned into t antichains of the same size except for possibly one antichain of a smaller size. In this paper, it is shown that f(n)b n²/log n. This is an improvement of the best previously known upper bound for f(n).     

On the bounded domination number of tournaments

In a simple digraph, a star of degree t is a union of t edges with a common tail. The k-domination number γ_k(G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γ_k(T)=n/(k+1) when T is a tournament with n14k lg k vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n-vertex tournament is dominated by at most lg n−lglg n+2 vertices.     

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.     

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.     

Bondage number of strong product of two paths

The bondage number b(G) of a graph G is the cardinality of a minimum set of edges whose removal from G results in a graph with a domination number greater than that of G. In this paper, we obtain the exact value of the bondage number of the strong product of two paths. That is, for any two positive integers m≥2 and n≥2, b(P_m?P_n) = 7 - r(m) - r(n) if (r(m), r(n)) = (1, 1) or (3, 3), 6 - r(m) - r(n) otherwise, where r(t) is a function of positive integer t, defined as r(t) = 1 if t ≡ 1 (mod 3), r(t) = 2 if t ≡ 2 (mod 3), and r(t) = 3 if t ≡ 0 (mod 3).     

Embedding complete trees into the hypercube

We consider embeddings of the complete t-ary trees of depth k (denotation T^k,t) as subgraphs into the hypercube of minimum dimension n. This n, denoted by dim(T^k,t), is known if max{k,t}2. First, we study the next open cases t=3 and k=3. We improve the known upper bound dim(T^k,3)2k+1 up to lim_k→∞dim(T^k,3)/k5/3 and show lim_t→∞dim(T^3,t)/t=227/120. As a co-result, we present an exact formula for the dimension of arbitrary trees of depth 2, as a function of their vertex degrees. These results and new techniques provide an improvement of the known upper bound for dim(T^k,t) for arbitrary k and t.     

Curves with degenerate general hypersurface sections

Let YPⁿ be a non-degenerate curve such that for a general degree t hypersurface S of Pⁿ, t2, the scheme Y∩S does not span Pⁿ. Here we give a lower bound for n in terms of t and some invariants of Y.     

A one-dimensional Poisson growth model with non-overlapping intervals

Suppose given a realization of a Poisson process on the line: call the points ‘germs’ because at a given instant ‘grains’ start growing around every germ, stopping for any particular grain when it touches another grain. When all growth stops a fraction e⁻¹ of the line remains uncovered. Let n germs be thrown uniformly and independently onto the circumference of a circle, and let grains grow under a similar protocol. Then the expected fraction of the circle remaining uncovered is the nth partial sum of the usual series for e⁻¹. These results, which sharpen inequalities obtained earlier, have one-sided analogues: the grains on the positive axis alone do not cover the origin with probability e^−1/2, and the conditional probability that the origin is uncovered by these positive grains, given that the germs n and n+1 coincide, is the nth partial sum of the series for e^−1/2. Despite the close similarity of these results to the rencontre, or matching, problem, we have no inclusion–exclusion derivation of them. We give explicitly the distributions for the length of a contiguous block of grains and the number of grains in such a block, and for the length of a grain. The points of the line not covered by any grain constitute a Kingman-type regenerative phenomenon for which the associated p-function p(t) gives the conditional probability that a point at distance t from an uncovered point is also uncovered. These functions enable us to identify a continuous-time Markov chain on the integers for which p(t) is a diagonal transition probability.     

Caractérisation spectrale de la forme de Jordan

Soit , où désigne l'ensemble des matrices n×n à coefficients complexes. Nous montrons qu'on peut complètement caractériser la forme de Jordan de A en examinant le polynôme caractéristique de tA+X pour tous les tC et tous les . Ceci nous permet de donner une démonstration plus élémentaire d'un théorème de Baribeau et Ransford sur les transformations holomorphes de qui préservent le spectre.

Denote by the set of complex n×n matrices, and let . We give a variational, purely spectral characterization of the Jordan form of A by examining the characteristic polynomial of the perturbed matrices tA+X for tC and . This allows us to give a more elementary proof of a theorem of Baribeau and Ransford on spectrum-preserving holomorphic maps on .     

Induced subgraphs of given sizes

We say (n, e) → (m, f), an (m, f) subgraph is forced, if every n-vertex graph of size e has an m-vertex spanned subgraph with f edges. For example, as Turán proved, (n,e)→(k,(^k₂)) for e> t_{k − 1}(n) and (n,e) (^k₂)), otherwise. We give a number of constructions showing that forced pairs are rare. Using tools of extremal graph theory we also show infinitely many positive cases. Several problems remain open.     

On the limit of a product of matrix exponentials

The existence of the limit as ε→0 exp[(A+B/ε)t] exp[-Bt/ε]is studied for n×n matrices A,B. Necessary and sufficient conditions on B that the limit exist for all A are given.     

Weak convergence to the multiple Stratonovich integral

We have considered the problem of the weak convergence, as tends to zero, of the multiple integral processes

in the space , where fL²([0,T]ⁿ) is a given function, and {η(t)}_>0 is a family of stochastic processes with absolutely continuous paths that converges weakly to the Brownian motion. In view of the known results when n2 and f(t₁,…,t_n)=1_{t1<t2<<tn}, we cannot expect that these multiple integrals converge to the multiple Itô–Wiener integral of f, because the quadratic variations of the η are null. We have obtained the existence of the limit for any {η}, when f is given by a multimeasure, and under some conditions on {η} when f is a continuous function and when f(t₁,…,t_n)=f₁(t₁)f_n(t_n)1_{t1<t2<<tn}, with f_iL²([0,T]) for any i=1,…,n. In all these cases the limit process is the multiple Stratonovich integral of the function f.     

Directed triangles in directed graphs

We show that each directed graph on n vertices, each with indegree and outdegree at least n/t, where

Full-size image

, contains a directed circuit of length at most 3.     

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.     

Oscillation theorems for second-order half-linear differential equations

Oscillation criteria for the second-order half-linear differential equation

[r(t)|ξ′(t)|⁻¹ ξ′(t)]′ + p(t)|ξ(t)|⁻¹ξ(t)=0, t t₀

are established, where > 0 is a constant and exists for t [t₀, ∞). We apply these results to the following equation:

where , D = (D₁,…, D_N), Ω_a = x ^N : |x| ≥ a} is an exterior domain, and c C([a, ∞), ), n > 1 and N ≥ 2 are integers. Here, a > 0 is a given constant.     

A reversal index for tournament matrices

Given a tournament matrix T, its reversal indexi_R(T), is the minimum k such that the reversal of the orientation of k arcs in the directed graph associated with T results in a reducible matrix. We give a formula for i_R(T) in terms of the score vector of T which generalizes a simple criterion for a tournament matrix to be irreducible. We show that i_R(T)≤[(n-1)/2] for any tournament matrix T of order n, with equality holding if and only if T is regular or almost regular, according as n is odd or even. We construct, for each k between 1 and [(n-1)/2], a tournament matrix of order n whose reversal index is k. Finally, we suggest a few problems.