Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

Preservers of pairs of bivectors with bounded distance

We extend Liu’s fundamental theorem of the geometry of alternate matrices to the second exterior power of an infinite dimensional vector space and also use her theorem to characterize surjective mappings T from the vector space V of all n×n alternate matrices over a field with at least three elements onto itself such that for any pair A, B in V, rank(A-B)?2k if and only if rank(T(A)-T(B))?2k, where k is a fixed positive integer such that n?2k+2 and k?2.     

Matchings in starlike trees

Let m(G,k) be the number of k-matchings in the graph G. We write G₁ ⪯ G₂ if m(G₁, k) ≤ m(G₂, k) for all k = 1, 2,…. A tree is said to be starlike if it possesses exactly one vertex of degree greater than two. The relation T₁ ⪯ T₂ is shown to hold for various pairs of starlike trees T₁, T₂. The starlike trees (with a given number of vertices), extremal with respect to the relation ⪯, are characterized.     

On the existence of an invariant non-degenerate bilinear form under a linear map

Let V be a vector space over a field F. Assume that the characteristic of F is large, i.e. char(F)>dimV. Let T:V→V be an invertible linear map. We answer the following question in this paper. When doesVadmit a T-invariant non-degenerate symmetric (resp. skew-symmetric) bilinear form? We also answer the infinitesimal version of this question.Following Feit and Zuckerman 2, an element g in a group G is called real if it is conjugate in G to its own inverse. So it is important to characterize real elements in GL(V,F). As a consequence of the answers to the above question, we offer a characterization of the real elements in GL(V,F).Suppose V is equipped with a non-degenerate symmetric (resp. skew-symmetric) bilinear form B. Let S be an element in the isometry group I(V,B). A non-degenerate S-invariant subspace W of (V,B) is called orthogonally indecomposable with respect to S if it is not an orthogonal sum of proper S-invariant subspaces. We classify the orthogonally indecomposable subspaces. This problem is non-trivial for the unipotent elements in I(V,B). The level of a unipotent T is the least integer k such that (T-I)^k=0. We also classify the levels of unipotents in I(V,B).     

Degree conditions and degree bounded trees

We give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and A a vertex subset of G. We denote by σ_k(A) the minimum value of the degree sum in G of any k independent vertices in A and by w(G−A) the number of components in the induced subgraph G−A. Our main results are the following: (i) If σ_k(A)≥|V(G)|−1, then G contains a tree T with maximum degree at most k and A⊆V(T). (ii) If σ_k−w(G−A)(A)≥|A|−1, then G contains a spanning tree T such that d_T(x)≤k for every x∈A. These are generalizations of the result by Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Sem. Univ. Hamburg 43 (1975) 263-267] and the degree conditions are sharp.     

On exterior powers of endomorphisms

Let V be an n-dimensional vector space and T?Hom(V,V). The first result shows that if C_m(T), the mth compound of T, possesses a basis of eigenvectors, then it possesses a basis consisting of decomposable eigenvectors in the mth Grassman space over V. The paper also contains a simplified proof of a recent result of S. Belcerzyk on traces of compounds as well as conditions for the equality of fixed coefficients in the polynomials det(λA+μX) and det(λB+μX).     

Characterization of Hermitian and skew-Hermitian maps between matrix algebras

Let D be a division ring with an involution J such that D is finite-dimensional over its center Z and char D≠2. Let T:M_m(D)→M_n(D) be a Z-linear map between matrix rings over D. We show that T satisfies [T(X)]¹=T(X¹) if and only if T(X)=∑±A¹_kXA_k. Similarly, T satisfies [T(X)]¹ = ? T(X¹) if and only if T(X = ∑(A¹_kXB_k ? B¹_kXA_k). The first of these results generalizes and extends a theorem of R.D. Hill [2] on Hermitian-preserving transformations.     

Good distance graphs and the geometry of matrices

Denote by G=(V,∼) a graph which V is the vertex set and ∼ is an adjacency relation on a subset of V×V. In this paper, the good distance graph is defined. Let (V,∼) and (V^′,∼^′) be two good distance graphs, and φ:V→V^′ be a map. The following theorem is proved: φ is a graph isomorphism ⇔φ is a bounded distance preserving surjective map in both directions ⇔φ is a distance k preserving surjective map in both directions (where k<diam(G)/2 is a positive integer), etc. Let D be a division ring with an involution such that both |F∩Z_D|?3 and D is not a field of characteristic 2 with D=F, where and Z_D is the center of D. Let H_n(n?2) be the set of n×n Hermitian matrices over D. It is proved that (H_n,∼) is a good distance graph, where A∼B⇔rank(A-B)=1 for all A,B∈H_n.     

On the packing chromatic number of some lattices

For a positive integer k, a k-packing in a graph G is a subset A of vertices such that the distance between any two distinct vertices from A is more than k. The packing chromatic number of G is the smallest integer m such that the vertex set of G can be partitioned as V₁,V₂,…,V_m where V_i is an i-packing for each i. It is proved that the planar triangular lattice T and the three-dimensional integer lattice Z³ do not have finite packing chromatic numbers.     

A degree sum condition for long cycles passing through a linear forest

Let G be a (k+m)-connected graph and F be a linear forest in G such that |E(F)|=m and F has at most k-2 components of order 1, where k?2 and m?0. In this paper, we prove that if every independent set S of G with |S|=k+1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min{d-m,|V(G)|} which contains all the vertices and edges of F.     

On D. Hägele’s approach to the Bessis-Moussa-Villani conjecture

The reformulation of the Bessis-Moussa-Villani (BMV) conjecture given by Lieb and Seiringer asserts that the coefficient α_m,k(A,B) of t^k in the polynomial Tr(A+tB)^m, with A,B positive semidefinite matrices, is nonnegative for all m,k. We propose a natural extension of a method of attack on this problem due to Hägele, and investigate for what values of m,k the method is successful, obtaining a complete determination when either m or k is odd.     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).     

Trees through specified vertices

We prove a conjecture of Horak that can be thought of as an extension of classical results including Dirac’s theorem on the existence of Hamiltonian cycles. Namely, we prove for 1≤k≤n−2 if G is a connected graph with A⊂V(G) such that d_G(v)≥k for all v∈A, then there exists a subtree T of G such that V(T)⊃A and for all v∈A.     

Linear transformations which preserve fixed rank

Let M_{m, n}(F) denote the set of all m×n matrices over the algebraically closed field F. Let T denote a linear transformation, T:M_{m, n}(F)→M_{m, n}(F). Theorem: If max(m, n)?2k?2, k?1, and T preserves rank k matrices [i.e.?(A)=k implies ?(T(A))=k], then there exist nonsingular m×m and n×n matrices U and V respectively such that either (i) T:A→UAV for all A?M_{m, n}(F), or (ii) m=n and T:A→UA^tV for all A?M_n(F), where A^t denotes the transpose of A.     

Groups with the same prime graph as the orthogonal group B n (3)

Let G be a finite group. The prime graph of G is denoted by Γ(G). It is proved in [1] that if G is a finite group such that Γ(G) = Γ(B _p (3)), where p > 3 is an odd prime, then G ? B _p (3) or C _p (3). In this paper we prove the main result that if G is a finite group such that Γ(G) = Γ(B _n (3)), where n ≥ 6, then G has a unique nonabelian composition factor isomorphic to B _n (3) or C _n (3). Also if Γ(G) = Γ(B ₄(3)), then G has a unique nonabelian composition factor isomorphic to B ₄(3), C ₄(3), or ² D ₄(3). It is proved in [2] that if p is an odd prime, then B _p (3) is recognizable by element orders. We give a corollary of our result, generalize the result of [2], and prove that B _2k+1(3) is recognizable by the set of element orders. Also the quasirecognition of B _2k (3) by the set of element orders is obtained.     

Strong linear preservers of rank reverse permutability on triangular matrices

Let F be a field with ∣F∣ > 2 and T_n(F) be the set of all n × n upper triangular matrices, where n ? 2. Let k ? 2 be a given integer. A k-tuple of matrices A₁, …, A_k ∈ T_n(F) is called rank reverse permutable if rank(A₁ A₂ ? A_k) = rank(A_k A_k−1 ? A₁). We characterize the linear maps on T_n(F) that strongly preserve the set of rank reverse permutable matrix k-tuples.     

Orthogonal factorizations of graphs

Let G be a graph with vertex set V(G) and edge set E(G). Let k₁, k₂,…,k_m be positive integers. It is proved in this study that every [0,k₁+…+k_m?m+1]‐graph G has a [0, k_i]₁^m‐factorization orthogonal to any given subgraph H with m edges. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 267–276, 2002     

Bisecting a 4-connected graph with three resource sets

Let G=(V,E) be an undirected graph with a node set V and an arc set E. G has k pairwise disjoint subsets T₁,T₂,…,T_k of nodes, called resource sets, where |T_i| is even for each i. The partition problem with k resource sets asks to find a partition V₁ and V₂ of the node set V such that the graphs induced by V₁ and V₂ are both connected and |V₁∩T_i|=|V₂∩T_i|=|T_i|/2 holds for each i=1,2,…,k. The problem of testing whether such a bisection exists is known to be NP-hard even in the case of k=1. On the other hand, it is known that if G is (k+1)-connected for k=1,2, then a bisection exists for any given resource sets, and it has been conjectured that for k?3, a (k+1)-connected graph admits a bisection. In this paper, we show that for k=3, the conjecture does not hold, while if G is 4-connected and has K₄ as its subgraph, then a bisection exists and it can be found in O(|V|³log|V|) time. Moreover, we show that for an arc-version of the problem, the (k+1)-edge-connectivity suffices for k=1,2,3.     

An approximate version of the Loebl-Komlós-Sós conjecture

Loebl, Komlós, and Sós conjectured that if at least half of the vertices of a graph G have degree at least some k∈N, then every tree with at most k edges is a subgraph of G. Our main result is an approximate version of this conjecture for large enough n=|V(G)|, assumed that n=O(k).Our result implies an asymptotic bound for the Ramsey number of trees. We prove that r(Tk,Tm)?k+m+o(k+m), as k+m→∞.