Finding all essential terms of a characteristic maxpolynomial

Let us denote ab=max(a,b) and ab=a+b for and extend this pair of operations to matrices and vectors in the same way as in linear algebra. We present an O(n²(m+n log n)) algorithm for finding all essential terms of the max-algebraic characteristic polynomial of an n×n matrix over with m finite elements. In the cases when all terms are essential, this algorithm also solves the following problem: Given an n×n matrix A and k{1,…,n}, find a k×k principal submatrix of A whose assignment problem value is maximum.     

Partitions of finite affine geometries into caps

In a finite geometry of order q² we define a (q^mq^r)-affine cap to be a set of cardinality q^m which is a disjoint union ot q^m affine subgeometrics AG(r,q). such that no three points are coliinear unless contained in the same AG(r,q).

Given a PG(n,q²), where n = 2t + 1 or 2t + 2, and an n + 1 by n + 1 Hermitian matrix H over Gh(q²) with minimal polynomial (x - λ)^{n + 1}. we show that H induces a partition of the AG(n, q²) obtained by deleting a distinguished hyperplane from the PG, into (qⁿ,q^{l + 1})-affine caps; these caps can be viewed as the "large points" of an AG (n,q) with a natural incidence relation. It is also shown that H induces another partition of AG(n,q²), into q^{n - l 1}-caps, constituting the "large points" of an affine geometry AG(n + t + 1,q).

Also, the collineation C of PG(n, q²) given by x^c = H^Tx induces collineations on the AG(n,q) and AG(n + t + 1,q).     

Continuous bottleneck tree partitioning problems

We study continuous partitioning problems on tree network spaces whose edges and nodes are points in Euclidean spaces. A continuous partition of this space into p connected components is a collection of p subtrees, such that no pair of them intersect at more than one point, and their union is the tree space. An edge-partition is a continuous partition defined by selecting p−1 cut points along the edges of the underlying tree, which is assumed to have n nodes. These cut points induce a partition into p subtrees (connected components). The objective is to minimize (maximize) the maximum (minimum) “size” of the components (the min–max (max–min) problem). When the size is the length of a subtree, the min–max and the max–min partitioning problems are NP-hard. We present O(n² log(min(p,n))) algorithms for the edge-partitioning versions of the problem. When the size is the diameter, the min–max problems coincide with the continuous p-center problem. We describe O(n log³ n) and O(n log² n) algorithms for the max–min partitioning and edge-partitioning problems, respectively, where the size is the diameter of a component.     

Recognizing Knödel graphs

Knödel graphs form a class of bipartite incident-graph of circulant digraphs. This class has been extensively studied for the purpose of fast communications in networks, and it has deserved a lot of attention in this context. In this paper, we show that there exists an O(n log⁵ n)-time algorithm to recognize Knödel graphs of order 2n. The algorithm is based on a characterization of the cycles of length six in these graphs (bipartite incident-graphs of circulant digraphs always have cycles of length six). A consequence of our result is that the circulant digraphs whose chords are the power of two minus one can be recognized in O(n log⁵ n) time.     

Almost resolvable maximum packings of complete graphs with 5-cycles

Let X be the vertex set of K_nA k-cycle packing of K_n is a triple (X,C,L), where C is a collection of edge disjoint k-cycles of K_n and L is the collection of edges of K_n not belonging to any of the k-cycles in C. A k-cycle packing (X,C,L) is called resolvable if C can be partitioned into almost parallel classes. A resolvable maximum k-cycle packing of K_n, denoted by k-RMCP(n), is a resolvable k-cycle packing of K_n, (X,C,L), in which the number of almost parallel classes is as large as possible. Let D(n, k) denote the number of almost parallel classes in a k-RMCP(n). D(n, k) for k = 3, 4 has been decided. When n ≡ k (mod 2k) and k ≡ 1 (mod 2) or n ≡ 1 (mod 2k) and k ∈{6, 8, 10, 14}∪{m: 5≤m≤49, m ≡ 1 (mod 2)}, D(n, k) also has been decided with few possible exceptions. In this paper, we shall decide D(n, 5) for all values of n≥5.     

The Best Lower Bound for the Permanent of a Correlation Matrix of Rank Two

If 1≤k≤n, then Cor(n,k) denotes the set of all n×n real correlation matrices of rank not exceeding k. Grone and Pierce have shown that if A∈Cor (n, n-1), then per(A)≥n/(n-1). We show that if A∈Cor(n,2), then , and that this inequality is the best possible.     

Cartographic line simplification and polygon CSG formulæ in O(n log n) time

A constructive solid geometry (CSG) conversion for a polygon takes a list of vertices and produces a formula representing the polygon as an intersection and union of primitive halfspaces. The cartographers' favorite line simplification algorithm recursively selects from a list of data points those to be used to represent a linear feature, such as a coastline, on a map. By using a data structure that maintains convex hulls of polygonal lines under splits, both were known to have O(n log n) time solutions in the worst-case. This paper shows that both are easier than sorting by presenting an O(n log^* n) algorithm for maintaining convex hulls under splits at extreme points. It opens the question of whether there are practical, linear-time solutions to these problems.     

Holes in random graphs

It is shown that for every >0 with the probability tending to 1 as n→∞ a random graph G(n,p) contains induced cycles of all lengths k, 3 ≤ k ≤ (1 − )n log c/c, provided c(n) = (n − 1)p(n)→∞.     

Approximating geometric bottleneck shortest paths

In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: given two points p and q of S and a real number L, compute (or approximate) a shortest path between p and q in the subgraph of the complete graph on S consisting of all edges whose lengths are less than or equal to L. We present efficient algorithms for answering several query problems of this type. Our solutions are based on Euclidean minimum spanning trees, spanners, and the Delaunay triangulation. A result of independent interest is the following. For any two points p and q of S, there is a path between p and q in the Delaunay triangulation, whose length is less than or equal to 2π/(3cos(π/6)) times the Euclidean distance |pq| between p and q, and all of whose edges have length at most |pq|.     

On the problem op n-stationary centers

Among the various problems of celestial mechanics related to the n-body problem, a certain amount of interest attaches to the specific situation wherein a passive gravitational point mass M moves under the assumption that the relative disposition of the other active gravitational masses experiences no large changes.

If the attracting masses are regarded as points and if changes in the relative disposition of the attracting bodies are neglected, one arrives at the problem of the motion of the point M in a field produced by n-stationary attracting centers (the point M here represents the (n+l)-th body).

In addition to the problem of central motion (n = 1), soluble dynamics problems of this category include Euler's case [1] of two (n= 2) stationary Newtonian attracting centers.

This problem, which for a long time was of solely theoretical Interest as an example of an integrable Liouville system [2], has recently been attracting attention in connection with the mechanics of artificial satellites, particularly after it was shown that the potential of an oblate spheroid can be approximated by the potential of two specifically chosen stationary Newtonian attracting centers [3 and 4].

The solution of the problem for n-attracting centers for n ≥ 3 is unknown, except for a single special case of three centers pointed out by Lagrange and considered In greater detail by J.A. Serre [5].

We shall concern ourselves here with problems on the existence of periodic trajectories in the case of n-attracting centers. An arbitrary and not necessarily Newtonian gravitational law will be assumed.

Our analysis is based on the theory of quasiindices of singular force field points as set forth in [60].     

Similarity over SL(n, F)

Let F be a finite field. It is shown that if AB axe n × n matrices with entries from F which are similar over GL(n, F), then AB are similar over SL(n, F), provided that some elementary divisor of xl- A is irreducible over F. The result remains true if F is any field such that any element of F may be represented as the norm of an element of any finite algebraic extension of F.     

Efficient text fingerprinting via Parikh mapping

We consider the problem of fingerprinting text by sets of symbols. Specifically, if S is a string, of length n, over a finite, ordered alphabet Σ, and S′ is a substring of S, then the fingerprint of S′ is the subset φ of Σ of precisely the symbols appearing in S′. In this paper we show efficient methods of answering various queries on fingerprint statistics. Our preprocessing is done in time O(n|Σ|lognlog|Σ|) and enables answering the following queries:

(1)Given an integer k, compute the number of distinct fingerprints of size k in time O(1).

(2)Given a set φΣ, compute the total number of distinct occurrences in S of substrings with fingerprint φ in time O(|Σ|logn).

     

On parallel rectilinear obstacle- avoiding paths

We give improved space and processor complexities for the problem of computing, in parallel, a data structure that supports queries about shortest rectilinear obstacle-avoiding paths in the plane, where the obstacles are disjoint rectangles. That is, a query specifies any source and destination in the plane, and the data structure enables efficient processing of the query. We now can build the data structure with O(n²/log n) CREW PRAM processors, as opposed to the previous O(n²), and with O(n²) space, as opposed to the previous O(n²(log n)²). The time complexity remains unchanged, at O((log n)²). As before, the data structure we compute enables a query to be processed in O(log n) time, by one processor for obtaining a path length, or by O(k/log n) processors for retrieving a shortest path itself, where k is the number of segments on that path. The new ideas that made our improvement possible include a new partitioning scheme of the recursion tree, which is used to schedule the computations performed on that tree. Since a number of other related shortest paths problems are solved using this technique as a subroutine our improvement translates into a similar improvement in the complexities of these problems as well.     

Baxter permutations

Chung et al. (1978) have proved that the number of Baxter permutations on [n] is

Viennot (1981) has then given a combinatorial proof of this formula, showing this sum corresponds to the distribution of these permutations according to their number of rises.

Cori et al. (1986), by making a correspondence between two families of planar maps, have shown that the number of alternating Baxter permutations on [2n+δ] is c_n+δc_n where c_n = (2n)!/(n + 1)!n! is the nth Catalan number.

In this paper, we establish a new one-to-one correspondence between Baxter permutations and three non-intersecting paths, which unifies Viennot (1981) and Cori et al. (1986). Moreover, we obtain more precise results for the enumeration of (alternating or not) Baxter permutations according to various parameters. So, we give a combinatorial interpretation of Mallows's formula (1979).     

On the generalized Erdös-Szekeres Conjecture — a new upper bound

We prove the following result: For every two natural numbers n and q, n q + 2, there is a natural number E(n, q) satisfying the following:

1. (1) Let S be any set of points in the plane, no three on a line. If |S| E(n, q), then there exists a convex n-gon whose points belong to S, for which the number of points of S in its interior is 0 (mod q).

2. (2) For fixed q, E(n,q) 2^c(q)·n, c(q) is a constant depends on q only.

Part (1) was proved by Bialostocki et al. [2] and our proof is aimed to simplify the original proof. The proof of Part (2) is completely new and reduces the huge upper bound of [2] (a super-exponential bound) to an exponential upper bound.     

Popular distances in 3-space

Let m(n) denote the smallest integer m with the property that any set of n points in Euclidean 3-space has an element such that at most m other elements are equidistant from it. We have that cn^1/3 log log n m(n) n^3/5 β(n), where c> 0 is a constant and β(n) is an extremely slowly growing function, related to the inverse of the Ackermann function.     

Minimal enclosing parallelepiped in 3D

We investigate the problem of finding a minimal volume parallelepiped enclosing a given set of n three-dimensional points. We give two mathematical properties of these parallelepipeds, from which we derive two algorithms of theoretical complexity O(n⁶). Experiments show that in practice our quickest algorithm runs in O(n²) (at least for n10⁵). We also present our application in structural biology.     

Computing rectangle enclosures

The rectangle enclosure problem is the problem of determining the subset of n iso-oriented planar rectangles that enclose a query rectangle Q. In this paper, we use a three layered data structure which is a combination of Range and Priority search trees and answers both the static and dynamic cases of the problem. Both the cases use O(n> log² n) space. For the static case, the query time is O(log² n log log n + K). The dynamic case is supported in O(log³ n + K) query time using O(log³ n) amortized time per update. K denotes the size of the answer. For the d-dimensional space the results are analogous. The query time is O(log^2d-2 n log log n + K) for the static case and O(log^2d-1 n + K) for the dynamic case. The space used is O(n> log^2d-2 n) and the amortized time for an update is O(log^2d-1 n). The existing bounds given for a class of problems which includes the present one, are O(log^2d n + K) query time, O(log^2d n) time for an insertion and O(log^2d-1 n) time for a deletion.     

Generalization of Erdős-Kac theorem

Let ω(n) is the number of distinct prime factors of the natural number n,we consider two cases where \ell is even and odd natural numbers, and then we prove a more general form of the classical Erdős-Kac theorem.