Affine and combinatorial binary m-spaces

Let V(n) denote the n-dimensional vector space over the 2-element field. Let a(m, r) (respectively, c(m, r)) denote the smallest positive integer such that if n ? a(m, r) (respectively, n ? c(m, r)), and V(n) is arbitrarily partitioned into r classes C_i, 1 ? i ? r, then some class C_i must contain an m-dimensional affine (respectively, combinatorial) subspace of V(n). Upper bounds for the functions a(m, r) and c(m, r) are investigated, as are upper bounds for the corresponding “density functions” $\text{a}\text{(m, ?)}$ and $\text{c}\text{(m, ?)}$.     

Subspaces of matrices with special rank properties

Let K be a field and let M_m×n(K) denote the space of m×n matrices over K. We investigate properties of a subspace M of M_m×n(K) of dimension n(m-r+1) in which each non-zero element of M has rank at least r and enumerate the number of elements of a given rank in M when K is finite. We also provide an upper bound for the dimension of a constant rank r subspace of M_m×n(K) when K is finite and give non-trivial examples to show that our bound is optimal in some cases. We include a similar a bound for the maximum dimension of a constant rank subspace of skew-symmetric matrices over a finite field.     

The enumeration problem for color critical linear hypergraphs

Denote by S(m, n, r) the number of non-isomorphic r-critical linear n-graphs on m vertices. It is shown that for n ≥ 3, r ≥ 3 there exists a constant c > 1 depending only on n and r such that S(m, n, r) > c^m for all sufficiently large m.     

Rectangular arrays

In this paper we studied m×n arrays with row sums $\text{nr}\text{(n,m)}$ and column sums $\text{mr}\text{(n,m)}$ where (n,m) denotes the greatest common divisor of m and n. We were able to show that the function H_m,n(r), which enumerates m×n arrays with row sums and column sums $\text{nr}\text{(m,n)}$ and $\text{mr}\text{(n,m)}$ respectively, is a polynomial in r of degree (m?1)(n?1). We found simple formulas to evaluate these polynomials for negative values, ?r, and we show that certain small negative integers are roots of these polynomials. When we considered the generating function G_m,n(y) = Σ_r?0H_m,n(r)y^r, it was found to be rational of degree less than zero. The denominator of G_m,n(y) is of the form (1?y)^(m?1)(n?1)+3, and the coefficients of the numerator are non-negative integers which enjoy a certain symmetric relation.     

A linear-algebra problem from algebraic coding theory

Given an m×n matrix M over E=GF(q^t) and an ordered basis A={z₁,…,z_t} for field E over K=GF(q), expand each entry of M into a t×1 vector of coordinates of this entry relative to A to obtain an mt×n matrix M¹ with entries from the field K. Let r=rank(M) and r¹=rank(M¹). We show that r?r¹?min{rt,n}, and we determine the number b(m,n,r,r¹,q,t) of m×n matrices M of rank r over GF(q^t) with associated mt×n matrix M¹ of rank r¹ over GF (q).     

Hua operators and Poisson transform for bounded symmetric domains

Let Ω be a bounded symmetric domain of non-tube type in Cn with rank r and S its Shilov boundary. We consider the Poisson transform Psf(z) for a hyperfunction f on S defined by the Poisson kernel Ps(z,u)=s(h(z,z)^n/r/²|h(z,u)^n/r|), (z,u)×Ω×S, s∈C. For all s satisfying certain non-integral condition we find a necessary and sufficient condition for the functions in the image of the Poisson transform in terms of Hua operators. When Ω is the type I matrix domain in Mn,m(C) (n?m), we prove that an eigenvalue equation for the second order Mn,n-valued Hua operator characterizes the image.     

A common property of R(E, F) and B(ℝ n , ℝ m ) and a new method for seeking a path to connect two operators

Given two Banach spaces E, F, let B(E, F) be the set of all bounded linear operators from E into F, and R(E, F) the set of all operators in B(E, F) with finite rank. It is well-known that B(? ⁿ ) is a Banach space as well as an algebra, while B(? ⁿ , ? ^m ) for m ≠ n, is a Banach space but not an algebra; meanwhile, it is clear that R(E, F) is neither a Banach space nor an algebra. However, in this paper, it is proved that all of them have a common property in geometry and topology, i.e., they are all a union of mutual disjoint path-connected and smooth submanifolds (or hypersurfaces). Let Σ _r be the set of all operators of finite rank r in B(E, F) (or B(? ⁿ , ? ^m )). In fact, we have that 1) suppose Σ _r ∈ B(? ⁿ , ? ^m ), and then Σ _r is a smooth and path-connected submanifold of B(? ⁿ , ? ^m ) and dimΣ _r = (n + m)r ? r ², for each r ∈ [0, min{n,m}; if m ≠ n, the same conclusion for Σ _r and its dimension is valid for each r ∈ [0, min{n, m}]; 2) suppose Σ _r ∈ B(E, F), and dimF = ∞, and then Σ _r is a smooth and path-connected submanifold of B(E, F) with the tangent space T _A Σ _r = {B ∈ B(E, F): BN(A) ? R(A)} at each A ∈ Σ _r for 0 ? r ? ∞. The routine methods for seeking a path to connect two operators can hardly apply here. A new method and some fundamental theorems are introduced in this paper, which is development of elementary transformation of matrices in B(? ⁿ ), and more adapted and simple than the elementary transformation method. In addition to tensor analysis and application of Thom’s famous result for transversility, these will benefit the study of infinite geometry.     

Poisson structures on affine spaces and flag varieties. I. Matrix affine Poisson space

The standard Poisson structure on the rectangular matrix variety Mm,n(C) is investigated, via the orbits of symplectic leaves under the action of the maximal torus T⊂GLm+n(C). These orbits, finite in number, are shown to be smooth irreducible locally closed subvarieties of Mm,n(C), isomorphic to intersections of dual Schubert cells in the full flag variety of GLm+n(C). Three different presentations of the T-orbits of symplectic leaves in Mm,n(C) are obtained: (a) as pullbacks of Bruhat cells in GLm+n(C) under a particular map; (b) in terms of rank conditions on rectangular submatrices; and (c) as matrix products of sets similar to double Bruhat cells in GLm(C) and GLn(C). In presentation (a), the orbits of leaves are parametrized by a subset of the Weyl group Sm+n, such that inclusions of Zariski closures correspond to the Bruhat order. Presentation (b) allows explicit calculations of orbits. From presentation (c) it follows that, up to Zariski closure, each orbit of leaves is a matrix product of one orbit with a fixed column-echelon form and one with a fixed row-echelon form. Finally, decompositions of generalized double Bruhat cells in Mm,n(C) (with respect to pairs of partial permutation matrices) into unions of T-orbits of symplectic leaves are obtained.     

Betti and Tachibana numbers

The Tachibana numbers t _r (M), the Killing numbers k _r (M), and the planarity numbers p _r (M) are considered as the dimensions of the vector spaces of, respectively, all, coclosed, and closed conformal Killing r-forms with 1 ≤ r ≤ n ? 1 “globally” defined on a compact Riemannian n-manifold (M,g), n >- 2. Their relationship with the Betti numbers b _r (M) is investigated. In particular, it is proved that if b _r (M) = 0, then the corresponding Tachibana number has the form t _r (M) = k _r (M) + p _r (M) for t _r (M) > k _r (M) > 0. In the special case where b ₁(M) = 0 and t ₁(M) > k ₁(M) > 0, the manifold (M,g) is conformally diffeomorphic to the Euclidean sphere.     

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.     

On the polynomial of a path

Let A(P_n) be the adjacency matrix of the path on n vertices. Suppose that r(λ) is a polynomial of degree less than n, and consider the matrix M = r(A>/(P_n)). We determine all polynomials for which M is the adjacency matrix of a graph.     

On upper domination Ramsey numbers for graphs

The classical Ramsey number r(m,n) can be defined as the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, β(B)⩾m or β(R)⩾n, where β(G) denotes the independence number of a graph G. We define the upper domination Ramsey number u(m,n) as the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, Γ(B)⩾m or Γ(R)⩾n, where Γ(G) is the maximum cardinality of a minimal dominating set of a graph G. The mixed domination Ramsey number v(m,n) is defined to be the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, Γ(B)⩾m or β(R)⩾n. Since β(G)⩽Γ(G) for every graph G, u(m,n)⩽v(m,n)⩽r(m,n). We develop techniques to obtain upper bounds for upper domination Ramsey numbers of the form u(3,n) and mixed domination Ramsey numbers of the form v(3,n). We show that u(3,3)=v(3,3)=6, u(3,4)=8, v(3,4)=9, u(3,5)=v(3,5)=12 and u(3,6)=v(3,6)=15.     

The packing problem for projective geometries over GF(3) with dimension greater than five

An (n, d) set in the projective geometry PG(r, q) is a set of n points, no d of which are dependent. The packing problem is that of finding n(r, q, d), the largest size of an (n, d) set in PG(r, q). The packing problem for PG(r, 3) is considered. All of the values of n(r, 3, d) for r ? 5 are known. New results for r = 6 are n(6, 3, 5) = 14 and 20 ? n(6, 3, 4) ? 31. In general, upper bounds on n(r, q, d) are determined using a slightly improved sphere-packing bound, the linear programming approach of coding theory, and an orthogonal (n, d) set with the known extremal values of n(r, q, d)—values when r and d are close to each other. The BCH constructions and computer searches are used to give lower bounds. The current situation for the packing problem for PG(r, 3) with r ? 15 is summarized in a final table.     

A criterion for generating full matrix algebras

Let M_n(F) be the algebra of n×n matrices over a field F, and let A∈M_n(F) have characteristic polynomial c(x)=p₁(x)p₂(x)?p_r(x) where p₁(x),…,p_r(x) are distinct and irreducible in F[x]. Let X be a subalgebra of M_n(F) containing A. Under a mild hypothesis on the p_i(x), we find a necessary and sufficient condition for X to be M_n(F).     

Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic

It was proved that the complexity of square root computation in the Galois field GF(3^s), s = 2^kr, is equal to O(M(2^k)M(r)k + M(r) log₂r) + 2^kkr^1+o(1), where M (n) is the complexity of multiplication of polynomials of degree n over fields of characteristics 3. The complexity of multiplication and division in the field GF(3^s) is equal to O(M(2^k)M(r)) and O(M(2^k)M(r)) + r^1+o(1), respectively. If the basis in the field GF(3^r) is determined by an irreducible binomial over GF(3) or is an optimal normal basis, then the summands 2^kkr^1+o(1) and r^1+o(1) can be omitted. For M(n) one may take n log₂nψ(n) where ψ(n) grows slower than any iteration of the logarithm. If k grow and r is fixed, than all the estimates presented here have the form O_r (M (s) log ₂s) = s (log ₂s)²ψ(s).     

On bi-regular cages of even girth at least 8

Let r, m, 2 ≤ r < m and g ≥ 3 be three positive integers. A graph with a prescribed degree set r, m and girth g having the least possible number of vertices is called a bi-regular cage or an (r, m; g)-cage, and its order is denoted by n(r, m; g). In this paper we provide upper bounds on n(r, m; g) for some related values of r, m and even girth g at least 8. Moreover, if r ? 1 is a prime power and m ≥ 5, we construct the smallest currently known (r, m; 8)-graphs. Also, if r = 3 and m ≥ 7 is not divisible by 3, we prove that ${n(3,m; 8) \ge \lceil 25m/3\rceil + 7}$ . Finally, we construct a family of (3, m; 8)-graphs of order 9m + 3 which are cages for m = 4,5,7.     

Linear maps preserving M–P inverses of matrices between matrix spaces over fields

Suppose F is a field of characteristic not 2. Let n and m be two arbitrary positive integers with n≥2. We denote by M _n (F) and S _n (F) the space of n×n full matrices and the space of n×n symmetric matrices over F, respectively. All linear maps from S _n (F) to M _m (F) preserving M–P inverses of matrices are characterized first, and thereby all linear maps from S _n (F) (M _n (F)) to S _m (F) (M _m (F)) preserving M–P inverses of matrices are characterized, respectively.     

Distance-restricted matching extension in planar triangulations

A graph G is said to have property E(m,n) if it contains a perfect matching and for every pair of disjoint matchings M and N in G with |M|=m and |N|=n, there is a perfect matching F in G such that M⊆F and N∩F=0?. In a previous paper (Aldred and Plummer 2001) [2], an investigation of the property E(m,n) was begun for graphs embedded in the plane. In particular, although no planar graph is E(3,0), it was proved there that if the distance among the three edges is at least two, then they can always be extended to a perfect matching. In the present paper, we extend these results by considering the properties E(m,n) for planar triangulations when more general distance restrictions are imposed on the edges to be included and avoided in the extension.     

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 structure of the 3-separations of 3-connected matroids

Tutte defined a k-separation of a matroid M to be a partition (A,B) of the ground set of M such that |A|,|B|k and r(A)+r(B)−r(M)<k. If, for all m<n, the matroid M has no m-separations, then M is n-connected. Earlier, Whitney showed that (A,B) is a 1-separation of M if and only if A is a union of 2-connected components of M. When M is 2-connected, Cunningham and Edmonds gave a tree decomposition of M that displays all of its 2-separations. When M is 3-connected, this paper describes a tree decomposition of M that displays, up to a certain natural equivalence, all non-trivial 3-separations of M.