An embedding theorem for finite planar spaces

LetS be a finite planar space such that any two distinct planes intersect in a line. We show thatk≤n ²+1 for anyk-cap ofS, wheren is the order ofS. Moreover, if a (n ²+1)-cap exists inS, a necessary and sufficient condition is provided forS to be embeddable in a 3-dimensional projective space. Work supported by the National Research Project “Strutture geometriche, Combinatoria e loro applicazioni” of the italian M.U.R.S.T.     

New examples of Lagrangian rigidity

Letn=4 or 8. We prove that any Lagrangian embedding ofS ^{n − 1} ×S ¹ into ℂ ⁿ has a trivial linking class. We deduce that every embedding ofS ³ ×S ⁴ into ℂ⁴ is isotopic to a Lagrangian embedding. This is false ifn = 8.     

Illuminating high-dimensional convex sets

A setL of points in thed-spaceE ^d is said toilluminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d if for every setS _i inF and every pointx in the boundary ofS _i there is a pointv inL such thatv illuminatesx, i.e. the line segment joiningv tox intersects the union of the elements ofF in exactly {x}.The problem we treat is the size of a setS needed to illuminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d . We also treat the problem of putting these convex sets in mutually disjoint convex polytopes, each one having at most a certain number of facets.     

Improved heuristics for the minimum weight triangulation problem

Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n ³) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases.     

ON STABLE LINE SEGMENTS IN ALL TRIANGULATIONS OF A PLANAR POINT SET

Abstract. Let S be a set of finite plauar points. A llne segment L(p, q) with p, q E Sis called a stable line segment of S, if there is no Line segment with two endpoints in S intersecting L(p, q). In this paper, some geometric properties of the set of all stable line segments     

On permutation properties in groups and semigroups

A semigroupS satisfiesPPn, thepermutation property of degree n (n≥2) if every product ofn elements inS remains invariant under some nontrivial permutation of its factors. It is shown that a semigroup satisfiesPP3 if and only if it contains at most one nontrivial commutator. Further a regular semigroup is a semilattice ofPP3 right or left groups, and a subdirect product ofPP3 semigroups of a simple type. A negative answer to a question posed by Restivo and Reutenauer is provided by a suitablePP3 group.     

Teoremi di normalizzazione per l'omotopia regolare dei grafi

Given a metric compact spaceS and a finite graphG we show that:

A combinatorial proof of the Borsuk-Ulam antipodal point theorem

We give a proof of Tucker’s Combinatorial Lemma that proves the fundamental nonexistence theorem: There exists no continuous map fromB ⁿ toS ^{n − 1} that maps antipodal points of∂B ⁿ to antipodal points ofS ^{n − 1}.     

Halfspace range search: An algorithmic application ofk-sets

Given a fixed setS ofn points inE ³ and a query plane, the halfspace range search problem asks for the retrieval of all points ofS on a chosen side of. We prove that withO(n(logn)⁸ (loglogn)⁴) storage it is possible to solve this problem inO(k+logn) time, wherek is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the total number ofj-sets (j=1, ...,k) realized by a set ofn points inE ³ isO(nk ⁵); ak-set is any subset ofS of sizek which can be separated from the rest ofS by a plane.Supported in part by NSF grants MCS 83-03925 and the Office of Naval Research and the Defense Advanced Research Projects Agency under contract N00014-83-K-0146 and ARPA Order No. 4786.Supported in part by Joint Services Electronics Program under Contract N00014-79-C-0424.     

On the number of halving planes

LetS ³ be ann-set in general position. A plane containing three of the points is called a halving plane if it dissectsS into two parts of equal cardinality. It is proved that the number of halving planes is at mostO(n ^2.998).As a main tool, for every setY ofn points in the plane a setN of sizeO(n ⁴) is constructed such that the points ofN are distributed almost evenly in the triangles determined byY.Research supported partly by the Hungarian National Foundation for Scientific Research grant No. 1812     

Permutability of normal extensions of a semilattice

LetS be a semigroup;S is said to bepermutable if, for some integern, every product ofn elements ofS can be re-ordered. We prove that every normal extension of a semilattice by an inverse permutable semigroupsis permutable. Also, some properties of permutable groups are extended to inverse semigroups.     

Theories of linear order

LetT be a complete theory of linear order; the language ofT may contain a finite or a countable set of unary predicates. We prove the following results. (i) The number of nonisomorphic countable models ofT is either finite or 2^ω. (ii) If the language ofT is finite then the number of nonisomorphic countable models ofT is either 1 or 2^ω. (iii) IfS ₁(T) is countable then so isS _n(T) for everyn. (iv) In caseS ₁(T) is countable we find a relation between the Cantor Bendixon rank ofS ₁(T) and the Cantor Bendixon rank ofS _n(T). (v) We define a class of modelsL, and show thatS ₁(T) is finite iff the models ofT belong toL. We conclude that ifS ₁(T) is finite thenT is finitely axiomatizable. (vi) We prove some theorems concerning the existence and the structure of saturated models. Most of the results in this paper appeared in the author’s Master of Science thesis which was prepared at the Hebrew University under the supervision of Professor H. Gaifman.     

Simplicial algorithm to solve the nonlinear complementarity problem onS n×R + m

In this paper, a simplicial algorithm is developed to solve the nonlinear complementarity problem onS ⁿ×R ₊ ^m . Furthermore, a condition for convergence is formulated. The triangulation which underlies the algorithm is a combination of the V-triangulation ofS ⁿ and the K-triangulation ofR ₊ ^m . Therefore, we will call it the VK-triangulation.The author wishes to thank Professor G. van der Laan for his valuable comments.     

Su una condizione di finitezza per semigruppi finitamente generati

We prove that a finitely generated semigroupS is finite if and only if there exists an integern such that in each sequence ofn elements ofS there exist two different non empty factors with the same value inS. We prove this result using only elementary facts concerning the canonical form of an element of a finitely generated semigroup.     

Spherical complexes and radial projections of polytopes

Using the techniques of Gale diagrams a simple criterion is given for determining when a given spherical complex onS ⁿ⁻¹ ⊂E ⁿ is the radial projection, from the centre ofS ⁿ⁻¹, of a convex polytope. Previously a criterion was known only for the casen=2.     

Homomorphisms of extensions of a semigroup within a variety

LetV be a semigroup variety containing all commutative semigroups such that the law of exponents (xy) ⁿ =xⁿyⁿ fails inV for everyn > 1. For every semigroupS V such that the reflection of the semigroup obtained fromS by an adding unity has only one idempotent there exists a semigroupT V extendingS without non-trivial endomorphisms. In more general, the full subcategory ofV formed by all extensions ofS withinV is universal.Presented by B. M. Schein.     

On the homotopy type of principal classical group bundles over spheres

The total spaces of principalSU(n−1) bundles overS ²ⁿ⁻¹ are classified. The classification ofSp(n−1) bundles overS ⁴ⁿ−1, is studied as well. As an intermediate step the homotopy equivalences ofSU andSp are classified.     

Conjecture of Li and Praeger concerning the isomorphisms of Cayley graphs of A5

LetG be a finite group, andS a subset ofG \ |1| withS =S ⁻¹. We useX = Cay(G,S) to denote the Cayley graph ofG with respect toS. We callS a Cl-subset ofG, if for any isomorphism Cay(G,S) ≈ Cay(G,T) there is an α∈ Aut(G) such thatS ^α =T. Assume that m is a positive integer.G is called anm-Cl-group if every subsetS ofG withS =S ⁻¹ and | S | ≤m is Cl. In this paper we prove that the alternating groupA ₅ is a 4-Cl-group, which was a conjecture posed by Li and Praeger.     

A completion problem for finite affine planes

A partial affine plane (PAP) of ordern is ann ²-setS of points together with a collection ofn-subsets ofS called lines such that any two lines meet in at most one point. We obtain conditions under which a PAP with nearlyn ²+n lines can be completed to an affine plane by adding lines. In particular, we make use of Bruck’s completion condition for nets to show that certain PAP’s with at leastn ²+n−√n can be completed and that forn≠3 any PAP withn ²+n−2 lines can be completed.