Faces of faces of the tridiagonal Birkhoff polytope

The tridiagonal Birkhoff polytope, , is the set of real square matrices with nonnegative entries and all rows and columns sums equal to 1 that are tridiagonal. This polytope arises in many problems of enumerative combinatorics, statistics, combinatorial optimization, etc. In this paper, for a given a p-face of , we determine the number of faces of lower dimension that are contained in it and we discuss its nature. In fact, a 2-face of is a triangle or a quadrilateral and the cells can only be tetrahedrons, pentahedrons or hexahedrons.     

Face counting on an Acyclic Birkhoff polytope

In this paper we present some algorithms allowing an exhaustive account on the number of edges and faces of the acyclic Birkhoff polytope.     

Fibonacci numbers, alternating parity sequences and faces of the tridiagonal Birkhoff polytope

We determine the number of alternating parity sequences that are subsequences of an increasing m-tuple of integers. For this and other related counting problems we find formulas that are combinations of Fibonacci numbers. These results are applied to determine, among other things, the number of vertices of any face of the polytope of tridiagonal doubly stochastic matrices.     

On acyclic and unicyclic graphs whose minimum rank equals the diameter

The minimum rank of a graph G is defined as the smallest possible rank over all symmetric matrices governed by G. It is well known that the minimum rank of a connected graph is at least the diameter of that graph. In this paper, we investigate the graphs for which equality holds between minimum rank and diameter, and completely describe the acyclic and unicyclic graphs for which this equality holds.     

Faces of faces of the acyclic Birkhoff polytope

Given a p-face of the acyclic Birkhoff polytope ?? _n (T), where T is a tree with n vertices, we find the number of faces of lower dimension that are contained in it, and its nature is discussed.     

On the products of cross-ratios on diagonals of polygons

The purpose of this paper is to establish a conjecture of B. Grünbaum, which states that in every n-polygon P in the plane, n 5, some diagonals intersect in a pattern that defines a new n-polygon (P), such that the product of the cross-rations on the diagonals of P is equal to the product of the corresponding cross-ratios on the diagonals of (P).     

On the null-spaces of acyclic and unicyclic singular graphs

For acyclic and unicyclic graphs we determine a necessary and sufficient condition for a graph G to be singular. Further, it is shown that this characterization can be used to construct a basis for the null-space of G.     

On the fractional matching polytope of a hypergraph

For a hypergraph andb:⁺ define Conjecture. There is a matching of such that For uniform andb constant this is the main theorem of [4]. Here we prove the conjecture if is uniform or intersecting, orb is constant.The research was done while the author visited the Department of Mathematics at Rutgers University. Research supported in part by the Hungarian National Science Foundation under grant No. 1812Supported in party by NSF and AFOSR grants and by a Sloan Research Fellowship     

A remark on the faces of the cone of Euclidean distance matrices

A new characterization of the faces of the cone of Euclidean distance matrices (EDMs) was recently obtained by Tarazaga in terms of LGS(D), a special subspace associated with each EDM D. In this note we show that LGS(D) is nothing but the Gale subspace associated with EDMs.     

On the primitivity of Cayley digraphs

We give a necessary and sufficient group theoretic condition for a Cayley digraph to be primitive.     

Surjections on Grassmannians preserving pairs of elements with bounded distance

Let m and k be two fixed positive integers such that m>k?2. Let V be a left vector space over a division ring with dimension at least m+k+1. Let G_m(V) be the Grassmannian consisting of all m-dimensional subspaces of V. We characterize surjective mappings T from G_m(V) onto itself such that for any A,B in G_m(V), the distance between A and B is not greater than k if and only if the distance between T(A) and T(B) is not greater than k.     

Coefficients of ergodicity and the scrambling index

For a primitive stochastic matrix S, upper bounds on the second largest modulus of an eigenvalue of S are very important, because they determine the asymptotic rate of convergence of the sequence of powers of the corresponding matrix. In this paper, we introduce the definition of the scrambling index for a primitive digraph. The scrambling index of a primitive digraph D is the smallest positive integer k such that for every pair of vertices u and v, there is a vertex w such that we can get to w from u and v in D by directed walks of length k; it is denoted by k(D). We investigate the scrambling index for primitive digraphs, and give an upper bound on the scrambling index of a primitive digraph in terms of the order and the girth of the digraph. By doing so we provide an attainable upper bound on the second largest modulus of eigenvalues of a primitive matrix that make use of the scrambling index.     

A characterization of linear spaces based on the number of transversals

We characterize a class of linear spaces by the property that through any point outside two disjoint, but non-parallel lines there is at most one transversal.     

Even and odd diagonals in doubly stochastic matrices

The existence of even or odd diagonals in doubly stochastic matrices depends on the number of positive elements in the matrix. The optimal general lower bound in order to guarantee the existence of such diagonals is determined, as well as their minimal number for given number of positive elements. The results are related to the characterization of even doubly stochastic matrices in connection with Birkhoff's algorithm.     

Linear spaces with many projective planes

We assume that in a linear space there is a non-empty set M of points with the property that every plane containing a point of M is a projective plane. In section 3 an example is given that in general is not a projective space. But if M can be completed by two points to a generating set of P, then is a projective space.     

The co-existence of elations and homologies of prime order

N. Krier and J. C. D. S. Yaqub have proved that if a projective plane admits an involutory homology and an involutory elation, then does not belong to the Lenz-Barlotti class I₁, and belongs to the class I₂. In this paper, we find the classification of projective planes having a homology of orderp and an elation of orderq, wherep andq are primes.This is based on a part of the doctoral dissertation of A. Solai Raju. The work was supported by a Senior Research Fellowship of the CSIR, India.     

Quotients of a universal locally projective polytope

In ``Quotients of a Universal Locally Projective Polytope' (Math. Z. 247 663–674, DOI: 10.1007/s00209-003-0625-9), the authors analyse the a certain locally projective universal polytope, showing it to be finite, and enumerating its quotients. The authors have since discovered some errors in the enumeration of the quotients. This note corrects these errors. The online version of the original article can be found at     

Minimum permanents on two faces of the polytope of doubly stochastic matrices

We consider the minimum permanents and minimising matrices on the faces of the polytope of doubly stochastic matrices whose nonzero entries coincide with those of, respectively,