Linear maps preserving regional eigenvalue location

Let M(n, C) be the vector space of n × n complex matrices and let G(r,s,t) be the set of all matrices in M(n, C) having r eigenvalues with positive real parts eigenvalues with negative real part and t eigenvalues with zero real part. In particularG(0,n,0) is the set of stable matrices. We investigate the set of linear operators on M(n, C) that map G(r,s,t) into itself. Such maps include, but are not always limited to similarities, transposition, and multiplication by a positive constant. The proof of our results depends on a characterization of nilpotent matrices in terms of matrices in a particular G(r,s,t), and an extension of a result about the existence of a matrix with prescribed eigenstructure and diagonal entries. Each of these results is of independent interest. Moreover, our char-acterization of nilpotent matrices is sufficiently general to allow us to determine the preservers of many other "inertia classes."     

Invariant differential operators on symplectic grassmann manifolds

LetM _2n,r denote the vector space of real or complex2n×r matrices with the natural action of the symplectic group Sp _2n , and letG=G _n,r =Sp _2n ×M _2n,r denote the corresponding semi-direct product. For any integerp with 0≤p≤n−1, letH denote the subgroupG _p,r ×Sp _2n−2p ofG. We explicitly compute the algebra of left invariant differential operators onG/H, and we show that it is a free algebra if and only ifr≤2n−2p+1. We also give orthogonal analogues of these results, generalizing those of Gonzalez and Helgason [3]. Partially supported by NSF grant DMS-9101358 This article was processed by the author using the Springer-Verlag T_EX mamath macro package 1990.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

The existence of howell designs of siden+1 and order 2n

AHowell design of side s andorder 2n, or more briefly, anH(s, 2n), is ans×s array in which each cell either is empty or contains an unordered pair of elements from some 2n-set, sayX, such that (a) each row and each column is Latin (that is, every element ofX is in precisely one cell of each row and each column) and (b) every unordered pair of elements fromX is in at most one cell of the array. Atrivial Howell design is anH(s, 0) havingX=? and consisting of ans×s array of empty cells. A necessary condition onn ands for the existence of a nontrivialH(s, 2n) is that 0<n≦s≦2n-1. AnH(n+t, 2n) is said to contain a maximum trivial subdesign if somet×t subarray is theH(t, 0). This paper describes a recursive construction for Howell designs containing maximum trivial subdesigns and applies it to settle the existence question forH(n+1, 2n)’s: forn+1 a positive integer, there is anH(n+1, 2n) if and only ifn+1 ∉ {2, 3, 5}.     

(3,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7. Revised: September 21, 1998     

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.     

Constrained Ramsey numbers of graphs

Given two graphs G and H, let f(G,H) denote the minimum integer n such that in every coloring of the edges of K_n, there is either a copy of G with all edges having the same color or a copy of H with all edges having different colors. We show that f(G,H) is finite iff G is a star or H is acyclic. If S and T are trees with s and t edges, respectively, we show that 1+s(t?2)/2≤f(S,T)≤(s?1)(t²+3t). Using constructions from design theory, we establish the exact values, lying near (s?1)(t?1), for f(S,T) when S and T are certain paths or star‐like trees. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 1–16, 2003     

The Hadamard-Fischer inequality for a class of matrices defined by eigenvalue monotonicity

The maximum dimension of a space of (k+1)×(k4+s?1) complex matrices of rank k is either s or s+1. Only when s divides k is it possible for the maximum to be s+1. This much is known. In this paper we produce for each k, a multiple of s, an (s+l)-dimensional space of (k+1)×(k+s?1) complex matrices whose non-zero members all have rank k. In the notation introduced by Sylvester l(k,k+1,k+s?1)=s+1 whenever s divides k.     

Expected Reflection Distance in G(r, 1, n) after a Fixed Number of Reflections

Extending to r > 1 a formula of the authors, we compute the expected reflection distance of a product of t random reflections in the complex reflection group G(r, 1, n). The result relies on an explicit decomposition of the reflection distance function into irreducible G(r, 1, n)-characters and on the eigenvalues of certain adjacency matrices.Received December 8, 2003     

On a particular case of the inconsistent linear matrix equation AX+YB=C

We consider the linear matrix equation AX+YB=C where A,B, and C are given matrices of dimensions (r+1)×r, s×(s+1), and (r+1)×(s+1), respectively, and rank A = r, rank B = s. We give a connection between the least-squares solution and the solution which minimizes an arbitrary norm of the residual matrix C?AX? YB.     

On the number of (r,r+1)‐ factors in an (r,r+1)‐factorization of a simple graph

For integers d≥0, s≥0, a (d, d+s)‐graph is a graph in which the degrees of all the vertices lie in the set {d, d+1, …, d+s}. For an integer r≥0, an (r, r+1)‐factor of a graph G is a spanning (r, r+1)‐subgraph of G. An (r, r+1)‐factorization of a graph G is the expression of G as the edge‐disjoint union of (r, r+1)‐factors. For integers r, s≥0, t≥1, let f(r, s, t) be the smallest integer such that, for each integer d≥f(r, s, t), each simple (d, d+s) ‐graph has an (r, r+1) ‐factorization with x (r, r+1) ‐factors for at least t different values of x. In this note we evaluate f(r, s, t). © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 257‐268, 2009     

Identity orientation of complete bipartite graphs

An identity orientation of a graph G=(V,E) is an orientation of some of the edges of E such that the resulting partially oriented graph has no automorphism other than the identity. We show that the complete bipartite graph K_s,t, with st, does not have an identity orientation if t3^s-log₃(s-1). We also show that if (r+1)(r+2)2s then K_s,3^s-r does have an identity orientation. These results improve the previous bounds obtained by Harary and Jacobson (Discuss. Math. - Graph Theory 21 (2001) 158). We use these results to determine exactly the values of t for which an identity orientation of K_s,t exists for 2s17.     

Inertially arbitrary patterns

An n×n sign pattern matrix A is an inertially arbitrary pattern (IAP) if each non-negative triple (r s t) 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 (n n) entry positive, and every other diagonal entry zero. We prove that S_n is an IAP.     

[r,s,t]-Coloring of K n,n

Let G=(V(G),E(G)) be a simple graph. Given non-negative integers r,s, and t, an [r,s,t]-coloring of G is a mapping c from V(G)∪E(G) to the color set {0,1,…,k?1} such that |c(v _i )?c(v _j )|≥r for every two adjacent vertices v _i ,v _j , |c(e _i )?c(e _j )|≥s for every two adjacent edges e _i ,e _j , and |c(v _i )?c(e _j )|≥t for all pairs of incident vertices and edges, respectively. The [r,s,t]-chromatic number χ _r,s,t (G) of G is defined to be the minimum k such that G admits an [r,s,t]-coloring. We determine χ _r,s,t (K _n,n ) in all cases.     

Sharp bounds for decompositions of graphs into complete r-partite subgraphs

If G is a graph on n vertices and r ≥ 2, we let m_r(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, E(G). In determining m_r(G), we may assume that no two vertices of G have the same neighbor set. For such reducedgraphs G, we prove that m_r(G) ≥ log₂ (n + r − 1)/r. Furthermore, for each k ≥ 0 and r ≥ 2, there is a unique reduced graph G = G(r, k) with m_r(G) = k for which equality holds. We conclude with a short proof of the known eigenvalue bound m_r(G) ≥ max{n₊ (G, n₋(G)/(r − 1)}, and show that equality holds if G = G(r, k). © 1996 John Wiley & Sons, Inc.     

The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

Rooted induced trees in triangle‐free graphs

For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceilFor a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceil$, improving a recent result by Fox, Loh and Sudakov. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 206–209, 2010     

[r,s, t]-Colorings of Graph Products

Let G =  (V, E) be a graph with vertex set V and edge set E. Given non negative integers r, s and t, an [r, s, t]-coloring of a graph G is a proper total coloring where the neighboring elements of G (vertices and edges) receive colors with a certain difference r between colors of adjacent vertices, a difference s between colors of adjacent edges and a difference t between colors of a vertex and an incident edge. Thus [r, s, t]-colorings generalize the classical colorings of graphs and can have applications in different fields like scheduling, channel assignment problem, etc. The [r, s, t]-chromatic number χ _r,s,t (G) of G is the minimum k such that G admits an [r, s, t]-coloring. In our paper we propose several bounds for the [r, s, t]-chromatic number of the cartesian and direct products of some graphs.     

Twisted inner products and contraction inequalities on spaces of contravariant and covariant tensors

Given positive integers n and p, and a complex finite dimensional vector space V, we let S_n,p(V) denote the set of all functions from V×V×?×V-(n+p copies) to C that are linear and symmetric in the first n positions, and conjugate linear symmetric in the last p positions. Letting κ=min{n,p} we introduce twisted inner products, [·,·]_s,t,1?s,t?κ, on S_n,p(V), and prove the monotonicity condition [F,F]_s,t?[F,F]_u,v is satisfied when s?u?κ,t?v?κ, and F∈S_n,p(V). Using the monotonicity condition, and the Cauchy-Schwartz inequality, we obtain as corollaries many known inequalities involving norms of symmetric multilinear functions, which in turn imply known inequalities involving permanents of positive semidefinite Hermitian matrices. New tensor and permanental inequalities are also presented. Applications to partial differential equations are indicated.