Characteristic sequences of non-associative algebras

Abstract

In this paper, we provide the complete characterization of integer sequences that are characteristic sequences for general non-associative algebras, i.e., we determine the set of combinatorial properties which hold for all characteristic sequences and construct corresponding algebras for integer sequences satisfying them. The obtained information on characteristic sequences is then applied to investigate the realizability problem for the length function. In particular, we determine certain segment of values which are not realizable as values of the length function.     

Some Enumeration Problems on Central Configurations at the Bifurcation Points

In “Counting central configurations at the bifurcation points,” we proposed an algorithm to rigorously count central configurations in some cases that involve one parameter. Here, we improve our algorithm to consider three harder cases: the planar \((3+1)\)-body problem with two equal masses; the planar 4-body problem with two pairs of equal masses which have an axis of symmetry containing one pair of them; the spatial 5-body problem with three equal masses at the vertices of an equilateral triangle and two equal masses on the line passing through the center of the triangle and being perpendicular to the plane containing it.While all three problems have been studied in two parameter cases, numerical observations suggest new results at some points on the bifurcation curves. Applying the improved version of our algorithm, we count at those bifurcation points. As a result, for the \((3+1)\)-body problem, we identify three points on the bifurcation curve where there are 8 central configurations, which adds to the known results of \(8,9,10\) ones. For our 4-body case, at the bifurcation points, there are 3 concave central configurations, which adds to the known results of \(2,4\) ones. For our 5-body case, at the bifurcation point, there is 1 concave central configuration, which adds to the known results of \(0,2\) ones.     

Center conditions and bifurcation of limit cycles at degenerate singular points in a quintic polynomial differential system

The center problem and bifurcation of limit cycles for degenerate singular points are far to be solved in general. In this paper, we study center conditions and bifurcation of limit cycles at the degenerate singular point in a class of quintic polynomial vector field with a small parameter and eight normal parameters. We deduce a recursion formula for singular point quantities at the degenerate singular points in this system and reach with relative ease an expression of the first five quantities at the degenerate singular point. The center conditions for the degenerate singular point of this system are derived. Consequently, we construct a quintic system, which can bifurcates 5 limit cycles in the neighborhood of the degenerate singular point. The positions of these limit cycles can be pointed out exactly without constructing Poincaré cycle fields. The technique employed in this work is essentially different from more usual ones. The recursion formula we present in this paper for the calculation of singular point quantities at degenerate singular point is linear and then avoids complex integrating operations.     

On the coordinatization of oriented matroids

Several important and hard realizability problems of combinatorial geometry can be reduced to the realizability problem of oriented matroids. In this paper we describe a method to find a coordinatization for a large class of realizable cases. This algorithm has been used successfully to decide several geometric realizability problems. It is shown that all realizations found by our algorithm fulfill the isotopy property.     

Möbius geometry of three-dimensional Wintgen ideal submanifolds in \mathbb{S}^5

Wintgen ideal submanifolds in space forms are those ones attaining equality at every point in the socalled DDVV inequality which relates the scalar curvature,the mean curvature and the normal scalar curvature.This property is conformal invariant;hence we study them in the framework of Mbius geometry,and restrict to three-dimensional Wintgen ideal submanifolds in S5.In particular,we give Mbius characterizations for minimal ones among them,which are also known as(3-dimensional)austere submanifolds(in 5-dimensional space forms).     

Mustafin varieties

A Mustafin variety is a degeneration of projective space induced by a point configuration in a Bruhat-Tits building. The special fiber is reduced and Cohen-Macaulay, and its irreducible components form interesting combinatorial patterns. For configurations that lie in one apartment, these patterns are regular mixed subdivisions of scaled simplices, and the Mustafin variety is a twisted Veronese variety built from such a subdivision. This connects our study to tropical and toric geometry. For general configurations, the irreducible components of the special fiber are rational varieties, and any blow-up of projective space along a linear subspace arrangement can arise. A detailed study of Mustafin varieties is undertaken for configurations in the Bruhat-Tits tree of PGL(2) and in the 2-dimensional building of PGL(3). The latter yields the classification of Mustafin triangles into 38 combinatorial types.     

On the combinatorial classification of nondegenerate configurations in the plane

We classify nondegenerate plane configurations by attaching, to each such configuration of n points, a periodic sequence of permutations of {1, 2, …, n} which satisfies some simple conditions; this classification turns out to be appropriate for questions involving convexity. In 1881 Perrin stated that every sequence satisfying these conditions was the image of some plane configuration. We show that this statement is incorrect by exhibiting a counterexample, for n = 5, and prove that for n ? 5 every sequence essentially distinct from this one is realized geometrically by giving a complete classification of configurations in these cases; there is 1 combinatorial equivalence class for n = 3, 2 for n = 4, and 19 for n = 5. We develop some basic notions of the geometry of “allowable sequences” in the course of proving this classification theorem. Finally, we state some results and an open problem on the realizability question in the general case.     

Symmetric (41,16,6)-designs with a nontrivial automorphism of odd order

If a symmetric (41,16,6)-design has an automorphism σ of odd prime order q then q = 3 or 5. In the case q = 5 we determine all such designs and find a total of 419 nonisomorphic ones, of which 15 are self-dual. When q = 3 a combinatorial explosion occurs and the complete classification becomes impracticable. However, we give a characterization in the particular case when σ has order 3 and fixes 11 points, and find that there are 3,076 nonisomorphic designs with this property, all of them being non self-dual. The other remaining possibility is that σ, of order 3, fixes 5 points. In this case there are 960 orbit matrices (up to isomorphism and duality) and all but one of them yield designs. Here an incomplete investigation shows that in total there are at least 112,000 nonisomorphic designs. © 1993 John Wiley & Sons, Inc.     

Optimal Synthesis in the Reeds and Shepp Problem with Onesided Variation of Velocity

We consider a time-optimal problem for the Reeds and Shepp model describing a moving point on a plane, with a onesided variation of the speed and a free final direction of the velocity. Using the Pontryagin Maximum Principle, we obtain all possible types of extremal and, analyzing them and discarding nonoptimal ones, construct the optimal synthesis.     

Computing Approximate Solutions of the Maximum Covering Problem with GRASP

We consider the maximum covering problem, a combinatorial optimization problem that arises in many facility location problems. In this problem, a potential facility site covers a set of demand points. With each demand point, we associate a nonnegative weight. The task is to select a subset of p > 0 sites from the set of potential facility sites, such that the sum of weights of the covered demand points is maximized. We describe a greedy randomized adaptive search procedure (GRASP) for the maximum covering problem that finds good, though not necessarily optimum, placement configurations. We describe a well-known upper bound on the maximum coverage which can be computed by solving a linear program and show that on large instances, the GRASP can produce facility placements that are nearly optimal.     

Suballowable sequences and geometric permutations

We define suballowable sequences of permutations as a generalization of allowable sequences. We give a characterization of allowable sequences in the class of suballowable sequences, prove a Helly-type result on sets of permutations which form suballowable sequences, and show how suballowable sequences are related to problems of geometric realizability. We discuss configurations of points and geometric permutations in the plane. In particular, we find a characterization of pairwise realizability of planar geometric permutations, give two necessary conditions for realizability of planar geometric permutations, and show that these conditions are not sufficient.     

Finding squares and rectangles in sets of points

A number of problems concerning sets of points in the plane are studied, e.g. establishing whether it contains a subset of size 4, which are the vertices of a square or rectangle. Both the problems of finding axis-parallel squares and rectangles, and arbitrarily oriented squares and rectangles are studied. Efficient algorithms are obtained for all of them. Furthermore, we investigate the generalizations tod-dimensional space, where the problem is to find hyperrectangles and hypercubes. Also, upper and lower bounds are given for combinatorial problems on the maxium number of subsets of size 4, of which the points are the vertices of a square or rectangle. Then we state an equivalence between the problem of finding rectangles, and the problem of findingK _{2, 2} subgraphs in bipartite graphs. Thus we immediately have an efficient algorithm for this graph problem.This work was partially supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). Work of the second author was also supported by the Dutch Organisation for Scientific Research (N.W.O.).     

Enumerating Order Types for Small Point Sets with Applications

Order types are a means to characterize the combinatorial properties of a finite point configuration. In particular, the crossing properties of all straight-line segments spanned by a planar n-point set are reflected by its order type. We establish a complete and reliable data base for all possible order types of size n=10 or less. The data base includes a realizing point set for each order type in small integer grid representation. To our knowledge, no such project has been carried out before.We substantiate the usefulness of our data base by applying it to several problems in computational and combinatorial geometry. Problems concerning triangulations, simple polygonalizations, complete geometric graphs, and k-sets are addressed. This list of applications is not meant to be exhaustive. We believe our data base to be of value to many researchers who wish to examine their conjectures on small point configurations.     

Column generation decomposition with the degenerate constraints in the subproblem

In this paper, we propose a new Dantzig–Wolfe decomposition for degenerate linear programs with the non degenerate constraints in the master problem and the degenerate ones in the subproblem. We propose three algorithms. The first one, where some set of variables of the original problem are added to the master problem, corresponds to the Improved Primal Simplex algorithm (IPS) presented recently by Elhallaoui et al. [7]. In the second one, some extreme points of the subproblem are added as columns in the master problem. The third algorithm is a mixed implementation that adds some original variables and some extreme points of a subproblem to the master problem. Experimental results on some degenerate instances show that the proposed algorithms yield computational times that are reduced by an average factor ranging from 3.32 to 13.16 compared to the primal simplex of CPLEX.     

The Fermat–Torricelli Problem, Part I: A Discrete Gradient-Method Approach

We give a discrete geometric (differential-free) proof of the theorem underlying the solution of the well known Fermat–Torricelli problem, referring to the unique point having minimal distance sum to a given finite set of non-collinear points in d-dimensional space. Further on, we extend this problem to the case that one of the given points is replaced by an affine flat, and we give also a partial result for the case where all given points are replaced by affine flats (of various dimensions), with illustrative applications of these theorems.     

On the intersection of a Hermitian curve with a conic

Let ${\mathcal{H}}${\mathcal{H}} be a Hermitian curve and let Γ be a conic of PG(2, q ²). In this paper we determine the possible intersection configurations between Γ and H{\mathcal{H}} under the hypotheses that Γ and H{\mathcal{H}} either share two points with the same tangent lines or contain a common Baer subconic. Moreover, the intersection configurations between a degenerate Hermitian curve and a conic sharing a Baer subconic are also determined.     

On the Sylvester–Gallai and the orchard problem for pseudoline arrangements

We study a non-trivial extreme case of the orchard problem for 12 pseudolines and we provide a complete classification of pseudoline arrangements having 19 triple points and 9 double points. We have also classified those that can be realized with straight lines. They include new examples different from the known example of Böröczky. Since Melchior’s inequality also holds for arrangements of pseudolines, we are able to deduce that some combinatorial point-line configurations cannot be realized using pseudolines. In particular, this gives a negative answer to one of Grünbaum’s problems. We formulate some open problems which involve our new examples of line arrangements.     

Neighborly combinatorial 3-manifolds with dihedral automorphism group

It is well known that for anyn≧5 the boundary complex of the cyclic 4-polytopeC(n, 4) is a neighborly combinatorial 3-sphere admitting a vertex transitive action of the dihedral groupD _n of order 2n. In this paper we present a similar series of neighborly combinatorial 3-manifolds withn≧9 vertices, each homeomorphic to the “3-dimensional Klein bottle”. Forn=9 andn=10 these examples have been observed. before by A. Altshuler and L. Steinberg. Moreover we give a computer-aided enumeration of all neighborly combinatorial 3-manifolds with such a symmetry and with at most 19 vertices. It turns out that there are only four other types, one with 10, 15, 17, 19 vertices. We also discuss the more general case of manifolds with cyclic automorphism groupC _n.     

On Construction of Optimal A2-Codes

§ 1.Ｉｎｔｒｏｄｕｃｔｉｏｎ　Ｔｈｅａｕｔｈｅｎｔｉｃａｔｉｏｎｃｏｄｅｓｗｉｔｈａｒｂｉｔｒａｔｉｏｎ (Ａ2 ｃｏｄｅｓ)ａｒｅｉｎｔｒｏｄｕｃｅｄｂｙＳｉｍｍｏｎｓ[1]ａｎｄｓｔｕｄｉｅｄｉｎｍａｎｙｐａｐｅｒｓ (ｆｏｒｅｘａｍｐｌｅ ,[1— 8] ) .Ｏｎｅｏｆｔｈｅｍｏｓｔｉｍｐｏｒｔａｎｔｐｒｏｂｌｅｍｓｉｎｔｈｅｓｔｕｄｙｏｆａｕｔｈｅｎｔｉｃａｔｉｏｎｃｏｄｅｓｉｓｔｏｆｉｎｄｌｏｗｅｒｂｏｕｎｄｓｏｎｃｈｅａｔｉｎｇｐｒｏｂａｂｉｌｉｔｉｅｓａｎｄｏｎｔｈｅｎｕｍｂｅｒｓｏｆｅｎｃｏｄｉ…     

Affine Reductive Spaces of Small Dimension and Left A-Loops

In this paper we determine the at least 4-dimensional affine reductive homogeneous manifolds for an at most 9-dimensional simple Lie group or an at most 6-dimensional semi-simple Lie group. Those reductive spaces among them which admit a sharply transitive differentiable section yield local almost differentiable left A-loops. Using this we classify all global almost differentiable left A-loops L having either a 6-dimensional semi-simple Lie group or the group as the group topologically generated by their left translations. Moreover, we determine all at most 5-dimensional left A-loops L with as the group topologically generated by their left translations.