On Hadamard embeddability

Given any k vectors of dimension nk which are mutually orthogonal, it is well known that this matrix can be completed to an n×n orthogonal matrix. Hadamard matrices form a subclass of orthogonal matrices. By contrast it is shown that it is possible to construct Hadamard submatrices with 2t+2 rows that cannot be completed to a Hadamard matrix of order 4t for infinitely many values of t. Some familiarity with Hasse–Minkowski invariants is assumed. A large number of unsolved problems in this area are pointed out.     

On embeddability and stresses of graphs

Gluck has proven that triangulated 2-spheres are generically 3-rigid. Equivalently, planar graphs are generically 3-stress free. We show that already the K ₅-minor freeness guarantees the stress freeness. More generally, we prove that every K _r+2-minor free graph is generically r-stress free for 1≤r≤4. (This assertion is false for r≥6.) Some further extensions are discussed. Supported by an I.S.F. grant.     

On the embeddability of polar spaces

We show that every nondegenerate polar space of rank at least 4 with at least three points on each line can be embedded in a projective space. Together with some results from [9] and [12], this provides a particularly elementary proof that any such polar space is of classical type. Our methods involve the use of geometric hyperplanes and work equally well for spaces of finite or infinite rank.     

On convex decompositions of a planar point set

Let P be a planar point set in general position. Neumann-Lara et al. showed that there is a convex decomposition of P with at most elements. In this paper, we improve this upper bound to .     

On the embeddability of Skeleta of spheres

We consider a generalization of the van Kampen-Flores Theorem and relate it to the long-standing g-conjecture for simplicial spheres.     

On strong embeddability and finite decomposition complexity

The strong embeddability is a notion of metric geometry, which is an intermediate property lying between coarse embeddability and property A. In this paper, we study the permanence properties of strong embeddability for metric spaces. We show that strong embeddability is coarsely invariant and it is closed under taking subspaces, direct products, direct limits and finite unions. Furthermore, we show that a metric space is strongly embeddable if and only if it has weak finite decomposition complexity with respect to strong embeddability.     

On empty convex polygons in a planar point set

Let P be a set of n points in general position in the plane. Let X_k(P) denote the number of empty convex k-gons determined by P. We derive, using elementary proof techniques, several equalities and inequalities involving the quantities X_k(P) and several related quantities. Most of these equalities and inequalities are new, except for a few that have been proved earlier using a considerably more complex machinery from matroid and polytope theory, and algebraic topology. Some of these relationships are also extended to higher dimensions. We present several implications of these relationships, and discuss their connection with several long-standing open problems, the most notorious of which is the existence of an empty convex hexagon in any point set with sufficiently many points.     

On embedding an outer-planar graph in a point set

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog³n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n²) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n²) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.     

On the Frattini normal embeddability of products ofp-groups

ItH _i is a finite non-abelianp-group with center of orderp, for 1≦j≦R, then the direct product of theH _i does not occur as a normal subgroup contained in the Frattini subgroup of any finitep-group. If the Frattini subgroup Φ of a finitep-groupG is cyclic or elementary abelian of orderp ², then the centralizer of Φ inG properly contains Φ. Non-embeddability properties of products of groups of order 16 are established.     

On the number of rectangulations of a planar point set

We investigate the number of different ways in which a rectangle containing a set of n noncorectilinear points can be partitioned into smaller rectangles by n (nonintersecting) segments, such that every point lies on a segment. We show that when the relative order of the points forms a separable permutation, the number of rectangulations is exactly the (n+1)st Baxter number. We also show that no matter what the order of the points is, the number of guillotine rectangulations is always the nth Schröder number, and the total number of rectangulations is O(n²⁰/n⁴).     

On the distance and multidistance graph embeddability problem

The notions of the distance and multidistance embeddability of a graph in ?^d are natural generalizations of the notion of a distance graph in ?^d. Results on the complexity of the computational problem of verifying distance graph embeddability are briefly surveyed, and new progress in solving this and related problems is described.     

On the finite embeddability property for residuated ordered groupoids

The finite embeddability property (FEP) for integral, commutative residuated ordered monoids was established by W. J. Blok and C. J. van Alten in 2002. Using Higman's finite basis theorem for divisibility orders we prove that the assumptions of commutativity and associativity are not required: the classes of integral residuated ordered monoids and integral residuated ordered groupoids have the FEP as well. The same holds for their respective subclasses of (bounded) (semi-)lattice ordered structures. The assumption of integrality cannot be dropped in general--the class of commutative, residuated, lattice ordered monoids does not have the FEP--but the class of -potent commutative residuated lattice ordered monoids does have the FEP, for any .

     

On the structure of the set bases of a degenerate point

Consider an extreme point (EP)x ⁰ of a convex polyhedron defined by a set of linear inequalities. If the basic solution corresponding tox ⁰ is degenerate,x ⁰ is called a degenerate EP. Corresponding tox ⁰, there are several bases. We will characterize the set of all bases associated withx ⁰, denoted byB ⁰. The setB ⁰ can be divided into two classes, (i) boundary bases and (ii) interior bases. For eachB ⁰, there is a corresponding undirected graphG ⁰, in which there exists a tree which connects all the boundary bases. Some other properties are investigated, and open questions for further research are listed, such as the connection between the structure ofG ⁰ and cycling (e.g., in linear programs).