The k Most Frequent Distances in the Plane

   Abstract. A new upper bound is shown for the number of incidences between n points and n families of concentric circles in the plane. As a consequence, it is shown that the number of the k most frequent distances among n points in the plane is f _n (k)=O(n ^1.4571 k ^.6286 ) improving on an earlier bound of Akutsu, Tamaki, and Tokuyama.     

On k -diameter of k -connected graphs

Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d _k (G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d _k (G). For a fixed positive integer d, some conditions to insure d _k (G)⩽d are given in this paper. In particular, if d⩾3 and the sum of degrees of any s (s=2 or 3) nonadjacent vertices is at least n+(s−1)k+1−d, then d _k (G)⩽d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible. Supported by NNSF of China (19971086).     

Distinct Distances in the Plane

It is shown that every set of n points in the plane has an element from which there are at least cn ^6/7 other elements at distinct distances, where c>0 is a constant. This improves earlier results of Erdős, Moser, Beck, Chung, Szemerédi, Trotter, and Székely. Received November 15, 2000, and in revised form December 13, 2000. Online publication April 6, 2001.     

(k,+)-distance-hereditary graphs

In this work we introduce, characterize, and provide algorithmic results for (k,+)-distance-hereditary graphs, k0. These graphs can be used to model interconnection networks with desirable connectivity properties; a network modeled as a (k,+)-distance-hereditary graph can be characterized as follows: if some nodes have failed, as long as two nodes remain connected, the distance between these nodes in the faulty graph is bounded by the distance in the non-faulty graph plus an integer constant k. The class of all these graphs is denoted by DH(k,+). By varying the parameter k, classes DH(k,+) include all graphs and form a hierarchy that represents a parametric extension of the well-known class of distance-hereditary graphs.     

On products of k atoms

Let H be an atomic monoid. For k ? \Bbb Nk \in {\Bbb N} let V_k (H){\cal V}_k (H) denote the set of all m ? \Bbb Nm \in {\Bbb N} with the following property: There exist atoms (irreducible elements) u ₁, …, u _k , v ₁, …, v _m ∈ H with u ₁· … · u _k = v ₁ · … · v _m . We show that for a large class of noetherian domains satisfying some natural finiteness conditions, the sets V_k (H){\cal V}_k (H) are almost arithmetical progressions. Suppose that H is a Krull monoid with finite cyclic class group G such that every class contains a prime (this includes the multiplicative monoids of rings of integers of algebraic number fields). We show that, for every k ? \Bbb Nk \in {\Bbb N}, max V_2k+1 (H) = k |G|+ 1{\cal V}_{2k+1} (H) = k \vert G\vert + 1 which settles Problem 38 in [4].     

About Distances between Points on the Plane

Mathematical Notes -     

Point Sets with Many k -Sets

For any n , k , n\geq 2k>0 , we construct a set of n points in the plane with k -sets. This improves the bounds of Erdős, Lovász, et al. As a consequence, we also improve the lower bound for the number of halving hyperplanes in higher dimensions. Received September 10, 1999, and in revised form January 27, 2000.     

Existence of solutions to (k, n − k − 2) discrete boundary value problems

We provide general existence criteria to solutions for a class of higher-order discrete boundary value problems. Our results supplement as well as improve several recent results established in the literature.     

The Typical Growth of the k th Excess in a Random Integer Partition

 For a partition , of a positive integer n chosen uniformly at random from the set of all such partitions, the kth excess is defined by if . We prove a bivariate local limit theorem for as . The whole range of possible values of k is studied. It turns out that ρ and η _k are asymptotically independent and both follow the doubly exponential (extreme value) probability law in a suitable neighbourhood of .     

From Rectangular Bands to k -Primal Algebras

\noindent We begin by giving a new proof that every finite rectangular band is naturally dualisable. Motivated by the dualising structure arising from this proof, we call an algebra k-primal if it is (isomorphic to) a product of k independent primal algebras. For each k \geq 2 we exhibit a strong duality between the quasi-variety generated by a k -primal algebra and the topological quasi-variety \lilcat D _k of Boolean topological k -dimensional diagonal algebras. The category \lilcat D ₂ is the category of compact, totally disconnected rectangular bands. This duality extends Hu's duality for varieties generated by a primal algebra to the k -dimensional case. We find that Hu's ``uniqueness principle' for such varieties also extends to the k -dimensional case, namely, we show that a quasi-variety is equivalent as a category to the quasi-variety generated by a k -primal algebra if and only if it is itself generated by a k -primal algebra. June 18, 1999     

Maximum planar sets that determine k distances

Maximum planar sets that determine k distances are identified for k 5. Evidence is presented for the conjecture that all maximum sets for k 7 are subsets of the triangular lattice.     

The k-Client Problem

Virtually all previous research in online algorithms has focused on single-threaded systems where only a single sequence of requests compete for system resources. To model multithreaded online systems, we define and analyze the k-client problem, a dual of the well-studied k-server problem. In the basic k-client problem, there is a single server and k clients, each of which generates a sequence of requests for service in a metric space. The crux of the problem is deciding which client's request the single server should service rather than which server should be used to service the current request. We also consider variations where requests have nonzero processing times and where there are multiple servers as well as multiple clients.We evaluate the performance of algorithms using several cost functions including maximum completion time and average completion time. Two of the main results we derive are tight bounds on the performance of several commonly studied disk scheduling algorithms and lower bounds of on the competitive ratio of any online algorithm for the maximum completion time and average completion time cost functions when k is a power of 2. Most of our results are essentially identical for the maximum completion time and average completion time cost functions.     

On the largest kth eigenvalues of trees with n≡0 (mod k)

We consider the only remaining unsolved case n≡0 (mod k) for the largest kth eigenvalue of trees with n vertices. In 1995, Jia-yu Shao gave complete solutions for the cases k=2,3,4,5,6 and provided some necessary conditions for extremal trees in general cases (cf. [Linear Algebra Appl. 221 (1995) 131]). We further improve Shao's necessary condition in this paper, which can be seen as the continuation of [Linear Algebra Appl. 221 (1995) 131].     

Order restricted inference for sequential k-out-of-n systems

Sequential order statistics have been introduced to model sequential k-out-of-n systems which, as an extension of k-out-of-n systems, allow the failure of some components of the system to influence the remaining ones. Based on an independent sample of vectors of sequential order statistics, the maximum likelihood estimators of the model parameters of a sequential k-out-of-n system are derived under order restrictions. Special attention is paid to the simultaneous maximum likelihood estimation of the model parameters and the distribution parameters for a flexible location-scale family. Furthermore, order restricted hypothesis tests are considered for making the decision whether the usual k-out-of-n model or the general sequential k-out-of-n model is appropriate for a given data.     

Size of k-uniform hypergraph with diameter d

In this paper, we estimate the size of k-uniform hypergraph with diameter d, and give its minimum and maximum.     

The bandwidth of a tree with k leaves is at most

The bandwidth B(G) of a finite simple graph G is the minimum of the quantity max{ƒ(x)-ƒ(y) : xy E(G)} taken over all injective integer labellings ƒ of G. We prove that if a tree T has k leaves then B(T) [k/2]. This improves the previously known upper bound B(T) V(T)/2.     

The Cardinality of Sets of k -Independent Vectors over Finite Fields

A set of vectors is k-independent if all its subsets with no more than k elements are linearly independent. We obtain a result concerning the maximal possible cardinality Ind _q (n, k) of a k-independent set of vectors in the n-dimensional vector space F _q ⁿ over the finite field F _q of order q. Namely, we give a necessary and sufficient condition for Ind _q (n, k) = n + 1. We conclude with some pertinent remarks re applications of our results to codes, graphs and hypercubes.     

Faster algorithms for string matching with k mismatches

The string matching with mismatches problem is that of finding the number of mismatches between a pattern P of length m and every length m substring of the text T. Currently, the fastest algorithms for this problem are the following. The Galil–Giancarlo algorithm finds all locations where the pattern has at most k errors (where k is part of the input) in time O(nk). The Abrahamson algorithm finds the number of mismatches at every location in time . We present an algorithm that is faster than both. Our algorithm finds all locations where the pattern has at most k errors in time . We also show an algorithm that solves the above problem in time O((n+(nk³)/m)logk).     

Flag-transitive 2-(v, k, λ) symmetric designs with (k, λ) = 1 and alternating socle

Consider the flag-transitive 2-(v, k, λ) symmetric designs with (k, λ) = 1. We prove that if {D} is a nontrivial 2-(v, k, λ) symmetric design with (k, λ) = 1 and G≤Aut({D}) is flag-transitive with Soc(G) = A_n for n≥5, then {D} is the projective space PG₂(3,2) and G = A₇.     

Minimal least eigenvalue of connected graphs of order n and size m = n + k (5≤k≤8)

The least eigenvalue of a connected graph is the least eigenvalue of its adjacency matrix. We characterize the connected graphs of order n and size n + k (5≤k≤8 and n>k + 5) with the minimal least eigenvalue.