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.     

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.     

Maximum number of edges in a critically k-connected graph

A k-connected graph G is said to be critically k-connected if G−v is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(n−k)+p²/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal graphs.     

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 k-spaces of real matrices

It is shown that if W is a linear subspace of real n × n matrices, such that rank (A) = k for all 0 ≠ A ∈ W, then dim W≤ n. If dim W = n.5≤ n is prime, and 2 is primitive modulo n then k =1.     

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.     

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.     

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.     

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.     

Degrees in a digraph whose nodes are graphs

By an f-graph we mean an unlabeled graph having no vertex of degree greater than f. Let D(n, f) denote the digraph whose node set is the set of f-graphs of order n and such that there is an arc from the node corresponding to graph H to the node corresponding to the graph K if and only if K is obtainable from H by the addition of a single edge. In earlier work, algorithms were developed which produce exact results about the structure of D(n, f), nevertheless many open problems remain. For example, the computation of the order and size of D(n, f) for a number of values of n and f have been obtained. Formulas for the order and size for f = 2 have also been derived. However, no closed form formulas have been determined for the order and size of D(n, f) for any value of f. Here we focus on questions concerning the degrees of the nodes in D(n,n − 1) and comment on related questions for D(n,f) for 2 f < n − 1.     

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.     

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.     

Inertially arbitrary patterns

An n×n sign pattern matrix A is an inertially arbitrary pattern (IAP) if each non-negative triple (rst) with r+s+t=n is the inertia of a matrix with sign pattern A. This paper considers the n×n(n≥2) skew-symmetric sign pattern S_n with each upper off-diagonal entry positive, the (1,1) entry negative, the (nn) entry positive, and every other diagonal entry zero. We prove that S_n is an IAP.     

Small embeddings for partial cycle systems of odd length

We prove that if m is odd then a partial m-cycle system on n vertices can be embedded in an m-cycle system on at most m((m − 2)n(n − 1) + 2n + 1) vertices and that a partial weak Steiner m-cycle system on n vertices can be embedded in an m-cycle system on m(2n + 1) vertices.     

Linear operators preserving unitarily invariant norms of matrices

Let F_{m × n} be the set of all m × n matrices over the field F = C or R Denote by U_n(F) the group of all n × n unitary or orthogonal matrices according as F = C or F-R. A norm N() on Fm ×n, is unitarily invariant if N(UAV) = N(A): for all A ∈ F _m×n U ∈ U_m(F). and V ∈ U_n(F). We characterize those linear operators TF_{m × n} → F_{m × n}which satisfy N (T(A)) = N(A)for all A ∈ F_{m × n}

for a given unitarily invariant norm N(). It is shown that the problem is equivalent to characterizing those operators which preserve certain subsets in F_{m × n} To develop the theory we prove some results concerning unitary operators on F_{m × n} which are of independent interest.     

An inequality for M-matrices

If AB are n × n M matrices with dominant principal diagonal, we show that 3[det(A + B)]^1/n ≥ (det A)^1/n + (det B)^1/n.     

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).     

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .     

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.