Further results on irregular, critical perfect systems of difference sets II: systems without splits

An (m, n; u, v; c)-system is a collection of components, m of valency u−1 and n of valency v−1, whose difference sets form a perfect system with threshold c. If there is an (m, n; 3, 6; c)-system, then m2c−1; and if there is a (2c−1, n; 3, 6; c)-system, then 2c−1n. For all sufficiently large c, there are (2c−1, n; 3, 6; c)-systems with a split at 3c+6n−1 at least when n=1, 5, 6 and 7, but such systems do not exist for n=2, 3 or 4.

We describe here a general method of construction for (2c−1, n; 3, 6; c)-systems and use it to show that there are such systems for 2n4 and certain values of c depending on n. We also discuss the limitations of this method.     

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.     

Hamiltonian cycles in n-factor-critical graphs

A graph G is said to be n-factor-critical if G−S has a 1-factor for any SV(G) with |S|=n. In this paper, we prove that if G is a 2-connected n-factor-critical graph of order p with , then G is hamiltonian with some exceptions. To extend this theorem, we define a (k,n)-factor-critical graph to be a graph G such that G−S has a k-factor for any SV(G) with |S|=n. We conjecture that if G is a 2-connected (k,n)-factor-critical graph of order p with , then G is hamiltonian with some exceptions. In this paper, we characterize all such graphs that satisfy the assumption, but are not 1-tough. Using this, we verify the conjecture for k2.     

Embedding of circulant graphs and generalized Petersen graphs on projective plane

Both the circulant graph and the generalized Petersen graph are important types of graphs in graph theory. In this paper, the structures of embeddings of circulant graph C(2n + 1; {1, n}) on the projective plane are described, the number of embeddings of C(2n + 1; {1, n}) on the projective plane follows, then the number of embeddings of the generalized Petersen graph P(2n +1, n) on the projective plane is deduced from that of C(2n +1; {1, n}), because C(2n + 1;{1, n}) is a minor of P(2n + 1, n), their structures of embeddings have relations. In the same way, the number of embeddings of the generalized Petersen graph P(2n, 2) on the projective plane is also obtained.     

On the multisearching problem for hypercubes

In this paper we give improved bounds for the multisearch problem on a hypercube. This is a parallel search problem where the elements in the structure S to be searched are totally ordered, but where it is not possible to compare in constant time any two given queries q and q′. More precisely, we are given on a n-processor hypercube a sorted n-element sequence S, and a set Q of n queries, and we need to find for each query q Q its location in the sorted S. We present an improved algorithm for the multisearch problem, one that takes O(log n(log log n)³) time on a n-processor hypercube. This problem is fundamental in computational geometry, for example it models planar point location in a slab. We give as application a trapezoidal decomposition algorithm with the same time complexity on a n log n-processor hypercube. The hypercube model for which we claim our bounds is the standard one, SIMD, with O(1) memory registers per processor, and with one-port communication. Each register can store O(log n) bits, so that a processor knows its ID.     

Subsets of an interval whose product is a power

We form squares from the product of integers in a short interval [n, n + t_n], where we include n in the product. If p is prime, p|n, and (₂^p) > n, we prove that p is the minimum t_n. If no such prime exists, we prove t_n √5n when n> 32. If n = p(2p − 1) and both p and 2p − 1 are primes, then t_n = 3p> 3 √n/2. For n(n + u) a square > n², we conjecture that a and b exist where n < a < b < n + u and nab is a square (except n = 8 and N = 392). Let g₂(n) be minimal such that a square can be formed as the product of distinct integers from [n, g₂(n)] so that no pair of consecutive integers is omitted. We prove that g₂(n) 3n − 3, and list or conjecture the values of g₂(n) for all n. We describe the generalization to kth powers and conjecture the values for large n.     

Label placement by maximum independent set in rectangles

Motivated by the problem of labeling maps, we investigate the problem of computing a large non-intersecting subset in a set of n rectangles in the plane. Our results are as follows. In O(n log n) time, we can find an O(log n)-factor approximation of the maximum subset in a set of n arbitrary axis-parallel rectangles in the plane. If all rectangles have unit height, we can find a 2-approximation in O(n log n) time. Extending this result, we obtain a (1 + 1/k)-approximation in time O(n log n + n^2k−1) time, for any integer k ≥ 1.     

On the orders of directly indecomposable groups

We investigate the set of those integers n for which directly indecomposable groups of order n exist. For even n such groups are easily constructed. In contrast, we show that the density of the set of odd numbers with this property is zero. For each n we define a graph whose connected components describe uniform direct decompositions of all groups of order n. We prove that for almost all odd numbers (i.e., with the exception of a set of density zero) this graph has a single ‘big’ connected component and all other vertices are isolated. We also give an asymptotic formula for the number of isolated vertices of the graph, i.e., for the number of prime divisors q of n such that every group of order n has a cyclic direct factor of order q.     

Non-hyperbolic closed characteristics on non-degenerate star-shaped hypersurfaces in ℝ<Superscript>2<Emphasis Type="Italic">n</Emphasis></Superscript>

In this paper, we prove that for every index perfect non-degenerate compact star-shaped hypersurface ∑ ⊂ R²ⁿ, there exist at least n non-hyperbolic closed characteristics with even Maslovtype indices on ∑ when n is even. When n is odd, there exist at least n closed characteristics with odd Maslov-type indices on ∑ and at least (n-1) of them are non-hyperbolic. Here we call a compact star-shaped hypersurface ∑ ⊂ R²ⁿ index perfect if it carries only finitely many geometrically distinct prime closed characteristics, and every prime closed characteristic (τ, y) on ∑ possesses positive mean index and whose Maslov-type index i(y, m) of its m-th iterate satisfies i(y, m) ≠-1 when n is even, and i(y, m) ∉ {-2, -1, 0} when n is odd for all m ∈ N.     

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.     

Dynamic motion planning in low obstacle density environments

A fundamental task for an autonomous robot is to plan its own motions. Exact approaches to the solution of this motion planning problem suffer from high worst-case running times. The weak and realistic low obstacle density (L.O.D.) assumption results in linear complexity in the number of obstacles of the free space (Van der Stappen et al., 1997). In this paper we address the dynamic version of the motion planning problem in which a robot moves among polygonal obstacles which move along polylines. The obstacles are assumed to move along constant complexity polylines, and to respect the low density property at any given time. We will show that in this situation a cell decomposition of the free space of size O(n²(n) log² n) can be computed in O(n²(n) log² n) time. The dynamic motion planning problem is then solved in O(n²(n) log³ n) time. We also show that these results are close to optimal.     

On the sum powers of matrices

A theorem of Lagrange says that every natural number is the sum of 4 squares. M. Newman proved that every integral n by n matrix is the sum of 8 (-1)ⁿ squares when n is at least 2. He asked to generalize this to the rings of integers of algebraic number fields. We show that an n by n matrix over a a commutative R with 1 is the sum of squares if and only if its trace reduced modulo 2Ris a square in the ring R/2R. It this is the case (and n is at least 2), then the matrix is the sum of 6 squares (5 squares would do when n is even). Moreover, we obtain a similar result for an arbitrary ring R with 1. Answering another question of M. Newman, we show that every integral n by n matrix is the sum of ten k-th powers for all sufficiently large n. (depending on k).     

Partitioning Boolean lattices into antichains

Let f(n) be the smallest integer t such that a poset obtained from a Boolean lattice with n atoms by deleting both the largest and the smallest elements can be partitioned into t antichains of the same size except for possibly one antichain of a smaller size. In this paper, it is shown that f(n)b n²/log n. This is an improvement of the best previously known upper bound for f(n).     

Aspects of semiorders within interval orders

Let s_k(n) be the largest integer such that every n-point interval order with no antichain of more than k points includes an s_k(n)-point semiorder. When k = 1, s₁(n) = n since all interval orders with no two-point antichains are chains. Given (c₁,...,c₅) = (1, 2, 3, 4), it is shown that s₂(n) = c_n for n 4, s₃(n) = c_n for n 5, and for all positive n, s₂ (n+4) =s₂(n)+3, s₃(n+5) = s₃(n)+3. Hence s₂ has a repeating pattern of length 4 [1, 2, 3, 3; 4, 5, 6, 6; 7, 8, 9, 9;...], and s₃ has a repeating pattern of length 5 [1, 2, 3, 3, 4; 4, 5, 6, 6, 7; 7, 8, 9, 9, 10;...].

Let s(n) be the largest integer such that every n-point interval order includes an s(n)-point semiorder. It was proved previously that for even n from 4 to 14, and that s(17) = 9. We prove here that s(15) = s(16) = 9, so that s begins 1, 2, 3, 3, 4, 4,..., 8, 8, 9, 9, 9. Since s(n)/n→0, s cannot have a repeating pattern.     

Graphs with prescribed local connectivities

A graph G is locally n-connected (locally n-edge connected) if the neighborhood of each vertex of G is n-connected (n-edge connected). The local connectivity (local edge-connectivity) of G is the maximum n for which G is locally n-connected (locally n-edge connected). It is shown that if k and m are integers with O k < m, then a graph exists which has connectivity m and local connectivity k. Furthermore, such a graph with smallest order is determined. Corresponding results are obtained involving the local connectivity and the local edge-conectivity.     

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.     

Enumeration of irreducible binary words

Overlap free words over two letters are called irreducible binary words. Let d(n) denote the number of irreducible binary words of length n. In this paper we show that there are positive constants C₁ and C₂ such that C₁n^1.155<d(n)<C₂n^1.587 holds for all n>0.     

Sperner systems containing at most k sets of every cardinality

We prove using a direct construction that one can choose n − 2 subsets of an n-element set with different cardinality such that none of them contains any other. As a generalization, we prove that if for any j we can have at most k subsets containing exactly j elements (k> 1), then for n 5 we can choose at most k(n − 3) subsets from an n-element set such that they form a Sperner system. Moreover, we prove that this can be achieved if n is large enough, and give a construction for n 8k − 4.     

Commuting pairs and triples of matrices and related varieties

In this note, we show that the set of all commuting d-tuples of commuting n×n matrices that are contained in an n-dimensional commutative algebra is a closed set, and therefore, Gerstenhaber's theorem on commuting pairs of matrices is a consequence of the irreduciblity of the variety of commuting pairs. We show that the variety of commuting triples of 4×4 matrices is irreducible. We also study the variety of n-dimensional commutative subalgebras of M_n(F), and show that it is irreducible of dimension n²−n for n4, but reducible, of dimension greater than n²−n for n7.     

All trees are 1-embeddable and all except stars are 2-embeddable

A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))=. It is known that all trees T with n (≥2) vertices and T K_1,n−1 are embeddable. We say that G is 1-embeddable if, for every edge e, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e};and that it is 2-embeddable if,for every pair e₁, e₂ of edges, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e₁, e₂}. We prove here that all trees with n (3) vertices are 1-embeddable; and that all trees T with n (4) vertices and T K_1,n−1 are 2-embeddable. In a certain sense, this result is sharp.