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.     

Reconstructing polygons from x-rays

We present strategies for interactively reconstructing polygons from carefully chosen x-ray probes, generalizing previous results for convex polygons to a significantly larger class of objects. In particular, we show that n+h+2 parallel x-ray probes are sufficient to determine an n-gon P with h vertices on its convex hull, provided no three vertices of P are collinear. If given an upper bound n on the number of vertices of P, then 2n+2 parallel probes or 3n origin probes suffice. Further, we show that lg n–2 probes are necessary. Finally, we present verification strategies for arbitrary polygons. Interactive probing strategies have the potential to minimize radiation exposure in medical imaging.     

Wrapping polygons in polygons

This paper is developed toI ₂(2g).c-geometries, namely, point-line-plane structures where planes are generalized 2g-gons with exactly two lines on every point and any two intersecting lines belong to a unique plane.I ₂(2g).c-geometries appear in several contexts, sometimes in connection with sporadic simple groups. Many of them are homomorphic images of truncations of geometries belonging to Coxeter diagrams. TheI ₂(2g).c-geometries obtained in this way may be regarded as the standard ones. We characterize them in this paper. For everyI ₂(2g).c-geometry , we define a numberw(), which counts the number of times we need to walk around a 2g-gon contained in a plane of , building up a wall of planes around it, before closing the wall. We prove thatw()=1 if and only if is standard and we apply that result to a number of special cases.     

Enumeration of three-dimensional convex polygons

A self-avoiding polygon (SAP) on a graph is an elementary cycle. Counting SAPs on the hypercubic lattice ℤ ^d withd≥2, is a well-known unsolved problem, which is studied both for its combinatorial and probabilistic interest and its connections with statistical mechanics. Of course, polygons on ℤ ^d are defined up to a translation, and the relevant statistic is their perimeter. A SAP on ℤ ^d is said to beconvex if its perimeter is “minimal”, that is, is exactly twice the sum of the side lengths of the smallest hyper-rectangle containing it. In 1984, Delest and Viennot enumerated convex SAPs on the square lattice [6], but no result was available in a higher dimension. We present an elementar approach to enumerate convex SAPs in any dimension. We first obtain a new proof of Delest and Viennot's result, which explains combinatorially the form of the generating function. We then compute the generating function for convex SAPs on the cubic lattice. In a dimension larger than 3, the details of the calculations become very cumbersome. However, our method suggests that the generating function for convex SAPs on ℤ ^d is always a quotient ofdifferentiably finite power series.     

On hyperbolic right-angled polygons

In this paper we find conditions in order to construct hyperbolic right-angledN-gons with the lengths ofN-3 sides given.Explicit formulae for the length of a side in terms of the lengths ofN-3 non-adjacent sides are obtained.Partially supported by CICYT.     

Steiner polygons in the Steiner problem

A polygon, whose vertices are points in a given setA ofn points, is defined to be a Steiner polygon ofA if all Steiner minimal trees forA lie in it. Cockayne first found that a Steiner polygon can be obtained by repeatedly deleting triangles from the boundary of the convex hull ofA. We generalize this concept and give a method to construct Steiner polygons by repeatedly deletingk-gons,k n. We also prove the uniqueness of Steiner polygons obtained by our method.     

“Catalan traffic” and integrals on the Grassmannian of lines

We prove that certain numbers occurring in a problem of paths enumeration, studied by Niederhausen in [Catalan traffic at the beach, Eletron. J. Combin. 9 (R33) (2002) 1-17] (see also [R.P. Stanley, Catalan addendum, version of 30 October 2005. 〈http://www-math.mit.edu/∼rstan/ec/catadd.pdf〉]), are top intersection numbers in the cohomology ring of the Grassmannian of the lines in the complex projective (n+1)- space.     

On the primitivity of Cayley digraphs

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

On a problem of H. N. Gupta

It is shown that the axiom For any points x, y, z such that y is between x and z, there is a right triangle having x and z as endpoints of the hypotenuse and y as foot of the altitude to the hypotenuse, when added to three-dimensional Euclidean geometry over arbitrary ordered fields, is weaker than the axiom Every line which passes through the interior of a sphere intersects that sphere.     

Nonnegative matrix semigroups with finite diagonals

Let S be a multiplicative semigroup of matrices with nonnegative entries. Assume that the diagonal entries of the members of S form a finite set. This paper is concerned with the following question: Under what circumstances can we deduce that S itself is finite?     

On triangulations of the convex hull ofn points

A setS ofn points in Euclideand-space determines a convex hull which can be triangulated into some numberm of simplices using the points ofS as vertices. We characterize those setsS for which all triangulations minimizem. This is used to characterize sets of points maximizing the volume of the smallest non-trivial simplex. This work was supported in part by NSF Grants MCS 81-02519 and MCS 82-03347. This work supported in part by NSF Grants MCS 81-02519 and MCS 82-03347 Dedicated to Paul Erdős on his seventieth birthday     

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.     

The diameter of the acyclic Birkhoff polytope

In this work we give an interpretation of vertices and edges of the acyclic Birkhoff polytope, T_n=Ω_n(T), where T is a tree with n vertices, in terms of graph theory. We generalize a recent result relatively to the diameter of the graph G(T_n).     

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.     

On affine images of regular pentagons and pentagrams

In this paper we explore pentagons that are affine images of the regular pentagon and the regular pentagram. We obtain their characterizations in terms of two mild forms of regularity that deal with the notions of medians for a pentagon and the natural requirement that they are concurrent. Using these characterizations we show that there are various values involving the number 5 (thus related to the golden section) for which a careful selection of division points on appropriate segments determined by any pentagon will result in a pentagon that is the affine image of either a regular pentagon or a regular pentagram.     

On the addition of convex sets in the hyperbolic plane

Analogue to the definition $K + L := \bigcup_{x\in K}(x + L)$ of the Minkowski addition in the euclidean geometry it is proposed to define the (noncommutative) addition $K \vdash L := \bigcup_{0\, \leqsl\, \rho\,\leqsl\, a(\varphi),0\,\leqsl\,\varphi\,<\, 2\pi}T_{\rho}^{(\varphi)}(L)$ for compact, convex and smoothly bounded sets K and L in the hyperbolic plane $\Omega$ (Kleins model). Here $\rho = a(\varphi)$ is the representation of the boundary $\partial$ K in geodesic polar coordinates and $T_{\rho}^{(\varphi)}$ is the hyperbolic translation of $\Omega$ of length $\rho$ along the line through the origin o of direction $\varphi$. In general this addition does not preserve convexity but nevertheless we may prove as main results: (1) $o \in$ int $K, o \in$ int L and K,L horocyclic convex imply the strict convexity of $K \vdash L$, and (2) in this case there exists a hyperbolic mixed volume $V_h(K,L)$ of K and L which has a representation by a suitable integral over the unit circle.     

On homomorphisms between generalized polygons

We consider homomorphisms between abstract, topological, and smooth generalized polygons. It is shown that a continuous homomorphism is either injective or locally constant. A continuous homomorphism between smooth generalized polygons is always a smooth embedding. We apply this result to isoparametric submanifolds.Dedicated to Prof. Dr. H. R. Salzmann on the occasion of his 65th anniversary     

Enumeration of the self-avoiding polygons on a lattice by the Schwinger-Dyson equations

We show how to compute the generating function of the self-avoiding polygons on a lattice by using the statistical mechanics Schwinger-Dyson equations for the correlation functions of theN-vector spin model on that lattice.     

Cyclic polygons with given edge lengths: Existence and uniqueness

Let a₁, ..., a_n be positive numbers satisfying the condition that each of the a_i’s is less than the sum of the rest of them; this condition is necessary for the a_i’s to be the edge lengths of a (closed) polygon. It is proved that then there exists a unique (up to an isometry) convex cyclic polygon with edge lengths a₁, ..., a_n. On the other hand, it is shown that, without the convexity condition, there is no uniqueness—even if the signs of all central angles and the winding number are fixed, in addition to the edge lengths.     

On Waring's problem for many forms and Grassmann defective varieties

This paper is devoted to the classical Waring type problem for several algebraic forms. Its geometric translation in terms of Grassmann defectivity for projective varieties yields the best possible solution whenever the number of polynomials is greater than the number of variables. In particular, together with a classical theorem of Alessandro Terracini, this result gives a complete answer to Waring's problem for several ternary forms.