Bipartite graph matching for points on a line or a circle

Given two sets of M points on a line or on a circle, a minimal matching between them is found in O(M log M) time. The circular case, where the distance between two points is the length of the shortest arc connecting them, is shown to have the same complexity as the simpler linear case. Finding the shift of one of the sets, linear or circular, that minimizes the cost of matching is also discussed.     

Zero-one laws for random graphs with vertices in a Boolean cube

We study the limit probabilities of first-order properties for random graphs with vertices in a Boolean cube. We find sufficient conditions for a sequence of random graphs to obey the zero-one law for first-order formulas of bounded quantifier depth. We also find conditions implying a weakened version of the zero-one law.     

Three dimensional line stochastic matrices and extreme points

Several properties of the extreme points of the convex set of three dimensional line stochastic matrices of order n are presented. The existence of many different classes of extremal configurations is established. These extremal matrices exhibit a large variety of patterns with some unexpected configurations. Latin squares of special types are used in some of the existence results. Furthermore, three questions raised by Brualdi and Csima are answered concerning the extreme points of three dimensional plane stochastic matrices of order n.     

Tensor product Gauss-Lobatto points are Fekete points for the cube

Tensor products of Gauss-Lobatto quadrature points are frequently used as collocation points in spectral element methods. Unfortunately, it is not known if Gauss-Lobatto points exist in non-tensor-product domains like the simplex. In this work, we show that the -dimensional tensor-product of Gauss-Lobatto quadrature points are also Fekete points. This suggests a way to generalize spectral methods based on Gauss-Lobatto points to non-tensor-product domains, since Fekete points are known to exist and have been computed in the triangle and tetrahedron. In one dimension this result was proved by Fejér in 1932, but the extension to higher dimensions in non-trivial.

     

On reconstructive sets of vertices in the Boolean cube

The notion of reconstructive set is introduced in terms of the Fourier transform. We characterize the reconstructive linear subspaces and give some necessary and sufficient conditions for the reconstructiveness of a sphere. We also give a necessary condition for two concentric spheres to be reconstructive.     

Stability of inflectional elasticae centered at vertices or inflection points

Stability conditions for inflectional Euler’s elasticae centered at vertices or inflection points are obtained. Theoretical results are compared with experimental data for elastic rods.     

Distribution of points on the circle

In connection with the proof of his celebrated “2.4-Theorem”, Freiman proved that if α₁,…,αN are real numbers such that each interval [u,u+1/2) contains at most n of the αj mod 1, then . Freiman's result was extended by Moran and Pollington, and recently by Lev. This paper contains further extensions.     

Testing the relative positions of several points on a circle

This note introduces a programming technique that serves to facilitate the examination of the relative positions of several points on a circle, or—more generally—the relative positions of several entities that belong to a cyclic structure. The basic idea is to employ a function of the numerical representations of the individual positions which is invariant under rotation with regard to sign. The nature of the numerical representation makes it natural to introduce the term: cut-point-independent test procedure.     

On the index of boundary points of four-dimensional lattices admissible for a cube

Let Γ be a four-dimensional lattice of general position that is admissible for a cube. Assume that this lattice contains at least one point that belongs to the boundary of this cube. We prove that the index of the set of such points can be equal only to 0, 1, or 2. Bibliography: 5 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 322, 2005, pp. 176–185.     

On the gap structure of sequences of points on a circle

Considerable mathematical effort has gone into studying sequences of points in the interval [0, 1) which are evenly distributed, in the sense that certain intervals contain roughly the correct percentages of the first n points. This paper explores the related notion in which a sequence is evenly distributed if its first n points split a given circle into intervals which are roughly equal in length, regardless of their relative positions. The sequence x_k=(log₂ (2k−1) mod 1) was introduced in this context by De Bruijn and Erdös. We will see that the gap structure of this sequence is uniquely optimal in a certain sense, and optimal under a wide class of measures.     

Distance matrices,dimension, and conference graphs

We define the dimension of a distance matrix and its associated metric space, and use this to give necessary and sufficient conditions for a metric space to be isometrically embeddable into suitable real inner product spaces and Euclidean spheres. Also, for certain distance matrices C with irrational entries, we derive the bound w ≤ 2f+ 1 for the size w of C in terms of its dimension f. This result is applied to improve a bound by Larman, Rogers, and Seidel on two-distance sets in Euclidean space, and to characterize certain regular graphs as conference graphs.     

On the number of singularities,zero curvature points and vertices of a simple convex space curve

We prove a generalization of the 4 vertex theorem forC ³ closed simple convex space curves including singular and zero curvature points.Work partially supported by CNPq. The second author is also grateful to the Universidade Federal de Viçosa (Brasil) for hospitality during the production of this work.     

Cubic graphs on twelve vertices and the line graph of a finite affine plane

It is shown by Rao and Rao that certain geometric properties characterize the line graph of a BIB design with parameters b, v, r, k, 1, provided r - 2k + 1 < 0. If r = k + 1, and $\text{k \#\&62; 2}$, a characterization of the line graph of a finite affine plane is obtained. If r - 2k + 1 = 0, the only possible value for k is 2 and consequently r = k + 1 resulting in the case of the line graph of a finite affine plane. It is shown here that if r = k + 1 and k = 2, there are exactly seven other non-isomorphic graphs with those properties which are not the line graph of a finite affine plane and these are the only cubic graphs on twelve vertices with no quadrilaterals.     

Vandermonde matrices on the circle: Spectral properties and conditioning

Summary We study Vandermonde matrices whose nodes are given by a Van der Corput sequence on the unit circle. Our primary interest is in the singular values of these matrices and the respective (spectral) condition numbers. Detailed information about multiplicities and eigenvectors, however, is also obtained. Two applications are given to the theory of polynomials.Dedicated to R. S. Varga on the occasion of his sixtieth birthdayResearch of A. C. supported by the Fundación Andes, Chile, and by the German Academic Exchange Service (DAAD), Federal Republic of GermanyResearch of W. G. supported, in part, by the National Science Foundation, USA, (Grant CCR-8704404)Research of S. R. supported by the Fondo Nacional de Desarollo Cientßfico y Tecnológico (FONDECYT), Chile, (Grant 237/89), by the Universidad Técnica F. Santa Marßa, Valparaßso, Chile, (Grant 89.12.06), and by the German Academic Exchange Service (DAAD), Federal Republic of Germany