Spanners of additively weighted point sets

We study the problem of computing geometric spanners for (additively) weighted point sets. A weighted point set is a set of pairs (p,r) where p is a point in the plane and r is a real number. The distance between two points (pi,ri) and (pj,rj) is defined as |pipj|−ri−rj. We show that in the case where all ri are positive numbers and |pipj|?ri+rj for all i, j (in which case the points can be seen as non-intersecting disks in the plane), a variant of the Yao graph is a (1+?)-spanner that has a linear number of edges. We also show that the Additively Weighted Delaunay graph (the face-dual of the Additively Weighted Voronoi diagram) has a spanning ratio bounded by a constant. The straight-line embedding of the Additively Weighted Delaunay graph may not be a plane graph. Given the Additively Weighted Delaunay graph, we show how to compute a plane straight-line embedding that also has a spanning ratio bounded by a constant in time.     

Repeated distances in space

Fori = 1,...,n letC(x_i, r_i) be a circle in the plane with centrex _i and radiusr _i. A repeated distance graph is a directed graph whose vertices are the centres and where (x _i, x_j) is a directed edge wheneverx _j lies on the circle with centrex _i. Special cases are the nearest neighbour graph, whenr _i is the minimum distance betweenx _i and any other centre, and the furthest neighbour graph which is similar except that maximum replaces minimum. Repeated distance graphs generalize to any dimension with spheres or hyperspheres replacing circles. Bounds are given on the number of edges in repeated distance graphs ind dimensions, with particularly tight bounds for the furthest neighbour graph in three dimensions. The proofs use extremal graph theory.Research supported by the Natural Science and Engineering Research Council grant number A3013 and the F.C.A.R. grant number EQ1678.     

The diffeomorphic types of the complements of arrangements in ??3 II

For any arrangement of hyperplanes in ℂℙ³, we introduce the soul of this arrangement. The soul, which is a pseudo-complex, is determined by the combinatorics of the arrangement of hyperplanes. In this paper, we give a sufficient combinatoric condition for two arrangements of hyperplanes to be diffeomorphic to each other. In particular we have found sufficient conditions on combinatorics for the arrangement of hyperplanes whose moduli space is connected. This generalizes our previous result on hyperplane point arrangements in ℂℙ³. This work was partially supported by NSA grant and NSF grant     

The universal Lachlan semilattice without the greatest element

We deal with some upper semilattices of m-degrees and of numberings of finite families. It is proved that the semilattice of all c.e. m-degrees, from which the greatest element is removed, is isomorphic to the semilattice of simple m-degrees, the semilattice of hypersimple m-degrees, and the semilattice of Σ ₂ ⁰ -computable numberings of a finite family of Σ ₂ ⁰ -sets, which contains more than one element and does not contain elements that are comparable w.r.t. inclusion. Supported by the Grant Council (under RF President) for Young Russian Scientists via project MK-1820.2005.1. __________ Translated from Algebra i Logika, Vol. 46, No. 3, pp. 299–345, May–June, 2007.     

Factorizations of complete multipartite graphs into generalized cubes

For a positive integer d, the usual d‐dimensional cube Q_d is defined to be the graph (K₂)^d, the Cartesian product of d copies of K₂. We define the generalized cube Q(K_k, d) to be the graph (K_k)^d for positive integers d and k. We investigate the decomposition of the complete multipartite graph K into factors that are vertex‐disjoint unions of generalized cubes Q(K_k, d_i), where k is a power of a prime, n and j are positive integers with j ≤ n, and the d_i may be different in different factors. We also use these results to partially settle a problem of Kotzig on Q_d‐factorizations of K_n. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 144–150, 2000     

An exact algorithm for the capacitated shortest spanning arborescence

We are given a complete and loop-free digraphG=(V, A), whereV={1,...,n} is the vertex set,A={(i, j) :i, j V} the arc set, andr V is a distinguishedroot vertex. For each arc (i, j) A, letc _ij be the associatedcost, and for each vertexi, letq _i 0 be the associateddemand (withq _r =0). Moreover, a nonnegativebranch capacity, Q, is defined.A Capacitated Shortest Spanning Arborescence rooted at r (CSSA _r ) is a minimum cost partial digraph such that: (i) each vertexj r has exactly one entering arc; (ii) for each vertexj r, a path fromr toj exists; (iii) for each branch leaving vertexr, the total demand of the vertices does not exceed the branch capacity,Q. A variant of theCSSA _r problem (calledD-CSSA _r ) arises when the out-degree of the root vertex is constrained to be equal to a given valueD. These problems are strongly NP-hard, and find practical applications in routing and network design. We describe a new Lagrangian lower bound forCSSA _r andD-CSSA _r problems, strengthened in a cutting plane fashion by iteratively adding violated constraints to the Lagrangian problem. We also present a new lower bound based on projection leading to the solution of min-cost flow problems. The two lower bounds are then combined so as to obtain an overall additive lower bounding procedure. The additive procedure is then imbedded in a branch-and-bound algorithm whose performance is enhanced by means of reduction procedures, dominance criteria, feasibility checks and upper bounding. Computational tests on asymmetric and symmetric instances from the literature, involving up to 200 vertices, are given, showing the effectiveness of the proposed approach.     

Determinants of the Hypergeometric Period Matrices of an Arrangement and Its Dual

We fix three natural numbers k, n, N, such that n+k+1 = N, and introduce the notion of two dual arrangements of hyperplanes. One of the arrangements is an arrangement of N hyperplanes in a k-dimensional affine space, the other is an arrangement of N hyperplanes in an n-dimensional affine space. We assign weights α ₁, . . . , α _N to the hyperplanes of the arrangements and for each of the arrangements consider the associated period matrices. The first is a matrix of k-dimensional hypergeometric integrals and the second is a matrix of n-dimensional hypergeometric integrals. The size of each matrix is equal to the number of bounded domains of the corresponding arrangement. We show that the dual arrangements have the same number of bounded domains and the product of the determinants of the period matrices is equal to an alternating product of certain values of Euler’s gamma function multiplied by a product of exponentials of the weights. Supported in part by NSF grant DMS-0244579.     

Bounds on vertex colorings with restrictions on the union of color classes

A proper coloring of a graph is a labeled partition of its vertices into parts which are independent sets. In this paper, given a positive integer j and a family ? of connected graphs, we consider proper colorings in which we require that the union of any j color classes induces a subgraph which has no copy of any member of ?. This generalizes some well‐known types of proper colorings like acyclic colorings (where j = 2 and ?is the collection of all even cycles) and star colorings (where j = 2 and ?consists of just a path on 4 vertices), etc. For this type of coloring, we obtain an upper bound of O(d^{(k ? 1)/(k ? j)}) on the minimum number of colors sufficient to obtain such a coloring. Here, d refers to the maximum degree of the graph and k is the size of the smallest member of ?. For the case of j = 2, we also obtain lower bounds on the minimum number of colors needed in the worst case. As a corollary, we obtain bounds on the minimum number of colors sufficient to obtain proper colorings in which the union of any j color classes is a graph of bounded treewidth. In particular, using O(d^8/7) colors, one can obtain a proper coloring of the vertices of a graph so that the union of any two color classes has treewidth at most 2. We also show that this bound is tight within a multiplicative factor of O((logd)^1/7). We also consider generalizations where we require simultaneously for several pairs (j_i, ?_i) (i = 1, …, l) that the union of any j_i color classes has no copy of any member of ?_i and obtain upper bounds on the corresponding chromatic numbers. © 2011 Wiley Periodicals, Inc. J Graph Theory 66: 213–234, 2011     

On the number of antipodal or strictly antipodal pairs of points in finite subsets ofR d,II

The paper is a continuation of [MM], namely containing several statements related to the concept of antipodal and strictly antipodal pairs of points in a subsetX ofR ^d , which has cardinalityn. The pointsx _i, x_jX are called antipodal if each of them is contained in one of two different parallel supporting hyperplanes of the convex hull ofX. If such hyperplanes contain no further point ofX, thenx _i, x_j are even strictly antipodal. We shall prove some lower bounds on the number of strictly antipodal pairs for givend andn. Furthermore, this concept leads us to a statement on the quotient of the lengths of longest and shortest edges of speciald-simplices, and finally a generalization (concerning strictly antipodal segments) is proved.Research (partially) supported by Hungarian National Foundation for Scientific Research, grant no. 1817     

Lacunary Quadrature Formulae and Interpolation Singularity

Birkholl quadrature formulae (q.f.), which have algebraic degree of precision (ADP) greater than the number of values used, are studied. In particular, we construct a class of quadrature rules of ADP = 2n + 2r + 1 which are based on the information {ƒ^(j)(−1), ƒ^(j)(−1), j = 0, ..., r − 1 ; ƒ(x_i), ƒ^(2m)(x_i), i = 1, ..., n}, where m is a positive integer and r = m, or r = m − 1. It is shown that the corresponding Birkhoff interpolation problems of the same type are not regular at the quadrature nodes. This means that the constructed quadrature formulae are not of interpolatory type. Finally, for each In, we prove the existence of a quadrature formula based on the information {ƒ(x_i), ƒ^(2m)(x_i), i = 1, ..., 2m}, which has algebraic degree of precision 4m + 1.     

A new approach to the dynamic maintenance of maximal points in a plane

A pointp _i=(x _i, y_i) in thex–y plane ismaximal if there is no pointp _j=(x _j, y_j) such thatx _j>x_i andy _j>y_i. We present a simple data structure, a dynamic contour search tree, which contains all the points in the plane and maintains an embedded linked list of maximal points so thatm maximal points are accessible inO(m) time. Our data structure dynamically maintains the set of points so that insertions takeO(logn) time, a speedup ofO(logn) over previous results, and deletions takeO((logn)²) time.The research of the first author was partially supported by the National Science Foundation under Grant No. DCR-8320214 and by the Office of Naval Research on Contract No. N 00014-86-K-0689. The research of the second author was partially supported by the Office of Naval Research on Contract No. N 00014-86-K-0689.     

Two-point concentration in random geometric graphs

A random geometric graph G _n is constructed by taking vertices X ₁,…,X _n ∈ℝ ^d at random (i.i.d. according to some probability distribution ν with a bounded density function) and including an edge between X _i and X _j if ‖X _i -X _j ‖ < r where r = r(n) > 0. We prove a conjecture of Penrose ([14]) stating that when r=r(n) is chosen such that nr ^d = o(lnn) then the probability distribution of the clique number ω(G _n ) becomes concentrated on two consecutive integers and we show that the same holds for a number of other graph parameters including the chromatic number χ(G _n ). The author was partially supported by EPSRC, the Department of Statistics, Bekkerla-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch fonds, and Prins Bernhard Cultuurfonds.     

Rank properties of certain semigroups

In this paper we consider certain ranks of some semigroups. These ranks are r ₁(S),r ₂(S),r ₃(S),r ₄(S) and r ₅(S) as defined below. We have r ₁≤r ₂≤r ₃≤r ₄≤r ₅. The semigroups are CL _n ,CL _m ×CL _n ,Z _n and SL _n . Here CL _n is a chain with n elements, Z _n is the zero semigroup on n elements and SL _n is the free semilattice generated by n elements and having 2 ⁿ −1 elements. We find many of the ranks for these classes of semigroups.     

Numbered distributive semilattices

In this article, we consider several definitions of a Lachlan semilattice; i.e., a semilattice isomorphic to a principal ideal of the semilattice of computably enumerable m-degrees. We also answer a series of questions on constructive posets and prove that each distributive semilattice with top and bottom is a Lachlan semilattice if it admits a Σ ₃ ⁰ -representation as an algebra but need not be a Lachlan semilattice if it admits a Σ ₃ ⁰ -representation as a poset. The examples are constructed of distributive lattices that are constructivizable as posets but not constructivizable as join (meet) semilattices. We also prove that every locally lattice poset (in particular, every lattice and every distributive semilattice) possessing a Δ ₂ ⁰ -representation is positive.     

Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements

Hyperplanes of the form xj=xi+c are called affinographic. For an affinographic hyperplane arrangement in Rn, such as the Shi arrangement, we study the function f(m) that counts integral points in n[1,m] that do not lie in any hyperplane of the arrangement. We show that f(m) is a piecewise polynomial function of positive integers m, composed of terms that appear gradually as m increases. Our approach is to convert the problem to one of counting integral proper colorations of a rooted integral gain graph.An application is to interval coloring in which the interval of available colors for vertex vi has the form [hi+1,m].A related problem takes colors modulo m; the number of proper modular colorations is a different piecewise polynomial that for large m becomes the characteristic polynomial of the arrangement (by which means Athanasiadis previously obtained that polynomial). We also study this function for all positive moduli.     

Cutting hyperplanes for divide-and-conquer

Givenn hyperplanes inE ^d, a (1/r)-cutting is a collection of simplices with disjoint interiors, which together coverE ^d and such that the interior of each simplex intersects at mostn/r hyperplanes. We present a deterministic algorithm for computing a (1/r)-cutting ofO(r ^d) size inO(nr ^d–1) time. If we require the incidences between the hyperplanes and the simplices of the cutting to be provided, then the algorithm is optimal. Our method is based on a hierarchical construction of cuttings, which also provides a simple optimal data structure for locating a point in an arrangement of hyperplanes. We mention several other applications of our result, e.g., counting segment intersections, Hopcroft's line/point incidence problem, linear programming in fixed dimension.This research was supported in part by the National Science Foundation under Grant CCR-9002352.     

Local duality for equitable partitions of a Hamming space

The Hamming space Qn is the set of binary words of length n. A partition (C₁,C₂,…,Cr) of Qn with quotient matrix B=[bij]_r×r is equitable if for all i and j, any word in the cell Ci has exactly bij neighbors in the cell Cj. In this paper, we provide an explicit formula relating the local spectrum of cells in the face to that in the orthogonal face.     

The bandwidth problem for graphs and matrices—a survey

The bandwidth problem for a graph G is to label its n vertices v_i with distinct integers f(v_i) so that the quantity max{| f(v_i) ? f(v_i)| : (v_i v_j) ∈ E(G)} is minimized. The corresponding problem for a real symmetric matrix M is to find a symmetric permutation M' of M so that the quantity max{| i ? j| : m'_ij ≠ 0} is minimized. This survey describes all the results known to the authors as of approximately August 1981. These results include the effect on bandwidth of local operations such as refinement and contraction of graphs, bounds on bandwidth in terms of other graph invariants, the bandwidth of special classes of graphs, and approximate bandwidth algorithms for graphs and matrices. The survey concludes with a brief discussion of some problems related to bandwidth.     

On the average genus of the random graph

The generalized Petersen graph GP (n, k), n ≤ 3, 1 ≥ k < n/2 is a cubic graph with vertex-set {u_j; i ? Z_n} ∪ {v_j; i ? Z_n}, and edge-set {u_iu_i, u_iv_i, v_iv_{i+k, i?}Z_n}. In the paper we prove that (i) GP(n, k) is a Cayley graph if and only if k² ? 1 (mod n); and (ii) GP(n, k) is a vertex-transitive graph that is not a Cayley graph if and only if k² ? -1 (mod n) or (n, k) = (10, 2), the exceptional graph being isomorphic to the 1-skeleton of the dodecahedon. The proof of (i) is based on the classification of orientable regular embeddings of the n-dipole, the graph consisting of two vertices and n parallel edges, while (ii) follows immediately from (i) and a result of R. Frucht, J.E. Graver, and M.E. Watkins [“The Groups of the Generalized Petersen Graphs,” Proceedings of the Cambridge Philosophical Society, Vol. 70 (1971), pp. 211-218]. © 1995 John Wiley & Sons, Inc.