On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes

It is well known that the complexity, i.e. the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Θ(n²). It is also known that if the points are chosen Independently Identically Distributed uniformly from a 3-dimensional region such as a cube or sphere, then the expected complexity falls to O(n). In this paper we introduce the problem of analyzing what occurs if the points are chosen from a 2-dimensional region in 3-dimensional space. As an example, we examine the situation when the points are drawn from a Poisson distribution with rate n on the surface of a convex polytope. We prove that, in this case, the expected complexity of the resulting Voronoi diagram is O(n).     

Soliton interactions of integrable models

The solution of integrable (n+1)-dimensional KdV system in bilinear form yields a dromion solution that is localized in all directions. The interactions between two dromions are studied both in analytical and in numerical for three (n+1)-dimensional KdV-type equations (n=1, 2, 3). The same interactive properties between two dromions (solitons) are revealed for these models. The interactions between two dromions (solitons) may be elastic or inelastic for different form of solutions.     

Manifolds of idemopotent matrices

Let M_n be the set of n×n matrices and r a nonnegative integer with r ≤ n. It is known,from Lie groups, that the rank r idempotent matrices in M_n form an arcwise connected 2n (n-r)-dimensional analytic manifold. This paper provides an elementary proof of this result making it accessible to a larger audience.     

Arc-smooth generalized universal covering spaces

Let Y be a path-connected subset of a CAT(0) space Z, allowing for a map to a 1-dimensional separable metric space X, such that the nontrivial point preimages of f form a null sequence of convex subsets of Z. Such Y need not be homotopy equivalent to a 1-dimensional space.

We prove that Y admits a generalized universal covering space, which we equip with an arc-smooth structure by consistently and continuously selecting one tight representative from each path homotopy class of Y. It follows that all homotopy groups of Y vanish in dimensions greater than 1.     

On fully extended self-avoiding polygons

The paper gives recurrence relations on the number of 2n step fully extended (i.e., full-dimensional) self-avoiding polygons in n- and (n − 1)-dimensional integer lattices.     

Examples of constant rank spaces

The maximum dimension of a space of (k+1)×(k4+s-1) complex matrices of rank k is either s or s+1. Only when s divides k is it possible for the maximum to be s+1. This much is known. In this paper we produce for each k, a multiple of s, an (s+l)-dimensional space of (k+1)×(k+s-1) complex matrices whose non-zero members all have rank k. In the notation introduced by Sylvester l(k,k+1,k+s-1)=s+1 whenever s divides k.     

On some properties of the series ∑k=0 kx and the Stirling numbers of the second kind

We partially characterize the rational numbers x and integers n 0 for which the sum ∑_k=0^∞ kⁿx^k assumes integers. We prove that if ∑_k=0^∞ kⁿx^k is an integer for x = 1 − a/b with a, b> 0 integers and gcd(a,b) = 1, then a = 1 or 2. Partial results and conjectures are given which indicate for which b and n it is an integer if a = 2. The proof is based on lower bounds on the multiplicities of factors of the Stirling number of the second kind, S(n,k). More specifically, we obtain for all integers k, 2 k n, and a 3, provided a is odd or divisible by 4, where v_a(m) denotes the exponent of the highest power of a which divides m, for m and a> 1 integers.

New identities are also derived for the Stirling numbers, e.g., we show that ∑_k=0²ⁿk! S(2n, k) , for all integers n 1.     

New exact solutions of the Broer–Kaup equations in (2 + 1)-dimensional spaces

With the aid of Maple, several new kinds of exact solutions for the Broer–Kaup equations in (2 + 1)-dimensional spaces are obtained by using a new ansätz. This approach can also be applied to other nonlinear evolution equations.     

On the number of flats spanned by a set of points in PG(d, q)

It is shown that for fixed 1 r s < d and > 0, if X PG(d, q) contains (1 + )q^s points, then the number of r-flats spanned by X is at least c()q^{(r+1)(s+1−r)}, i.e. a positive fraction of the number of r-flats in PG(s + 1,q).     

On the M/G/1 queue with D-policy

This paper deals with the M/G/1 queue with D-policy, i.e., the server is turned off at the end of a busy period and turned on when the cumulative amount of work firstly exceeds some fixed value D. We first concentrate on the computation of the steady-state probabilities. The first moments and relationships among the busy period, the number of customers served and other performance measures are investigated. Some variants of the main model and the special case of the M/M/1 are also studied.     

New families of exact solitary patterns solutions for the nonlinearly dispersive R(m,n) equations

The R(m,n) equations u_tt+a(uⁿ)_xx+b(u^m)_xxtt=0 (a, b const) are investigated by using some ansatze. As a result, new exact solitary patterns solutions and solitary wave solutions are obtained. These obtained solutions show that not only the nonlinearly dispersive R(m,m) equations (m≠1) but also the linearly dispersive R(1,n) equations (m=1) possess solitary patterns solutions, which has infinite slopes or cusps and solitary wave solutions.     

The range of the p-Laplacian

We prove that for λ ≥ 0, p ≥ 3, there exists an open ball B L²(0,1) such that the problem

− (|u′|^p−2 u′)′ − λ|u|^p−2u = f, in (0,1)

, subject to certain separated boundary conditions on (0,1), has a solution for f B.     

Regular automorphisms of order p2

Let G be a group, and let α be a regular automorphism of order p² of G, where p is a prime. If G is polycyclic-by-finite and the map ϕ : G →G defined by g^ϕ= [g,α] is surjective, then G is soluble. If G is polycyclic, then C_G(α^p) and G/[G,α^p] are both nilpotent-by-finite.     

Extending shelling orders and a hierarchy of functions of unimodal simple polytopes

Let P be a simplicial d-polytope with n facets ((d − 1)-dimensional faces) in R^d. A shelling of P is an ordering of the facets of P such that the intersection of each facet F with the union of all facets that precede it the ordering is a nonempty union of (d − 2)-faces of F. The following open question was raised by Tverberg and is recorded in [4]. Suppose for some k < n, there is an ordering of k of the facets of P so that the intersection of each of these facets with the union of all of the facets that precede it in the ordering is a nonempty union of (d − 2)-faces. Can this initial “segment” be extended to a shelling of all the facets? This question is open even in the case that P is the dual of the d-dimensional hypercube. The question in this case has resurfaced several times since G. Danaraj and V. Klee (1978) in a variety of forms. It is related to the hierarchies of completely unimodal pseudo-Boolean functions studied in P.L. Hammer et al. (1988), the author (1988) and D. Wiedemann (1986). (A pseudo-Boolean function is a function mapping the vertices of the d-dimensional hypercube into the reals). In this paper, the hierarchies are compared and combined. This hierarchy is then extended to general simple polytopes, and the relationship to the above open question is explained.     

Pancyclicity mod k of claw-free graphs and K1,4-free graphs

For any natural number k, a graph G is said to be pancyclic mod k if it contains a cycle of every length modulo k. In this paper, we show that every K_1,4-free graph G with minimum degree δ(G)k+3 is pancyclic mod k and every claw-free graph G with δ(G)k+1 is pancyclic mod k, which confirms Thomassen's conjecture (J. Graph Theory 7 (1983) 261–271) for claw-free graphs.     

Constructions of (q, K, λ, t, Q) almost difference families

The concept of a (q, k, λ, t) almost difference family (ADF) has been introduced and studied by C. Ding and J. Yin as a useful generalization of the concept of an almost difference set. In this paper, we consider, more generally, (q, K, λ, t, Q)-ADFs, where K = {k₁, k₂, ..., k_r} is a set of positive integers and Q = (q₁, q₂,..., q_r) is a given block-size distribution sequence. A necessary condition for the existence of a (q, K, λ, t, Q)-ADF is given, and several infinite classes of (q, K, λ, t, Q)-ADFs are constructed.     

On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

The k-ball l-path branch weight centroid

If x is a vertex of a tree T of radius r, if k and l are integers, if 0 k r, 0 l r, and if P is an l-path with one end at x, then define β(x; k, P) to be the number of vertices of T that are reachable from x via the l-path P and that are outside of the k-ball about x. That is, β(x;k,P) = {yεV(T):y is reachable from x via P,d(x,y) > k}. Define the k-ball l-path branch weight of x, denoted β(x;k,l), to be max {β(x;k,P):P an l-path with one end at x}, and define the k-balll-path branch weight centroid of T, denoted B(T;k,l), to be the set xεV(T): β(x;k,l) β(y;k,l), yεV(T). This two-parameter family of central sets in T includes the one-parameter family of central sets called the k-nuclei introduced by Slater (1981) which has been shown to be the one parameter family of central sets called the k-branch weight centroids by Zaw Win (1993). It also includes the one-parameter family of central sets called the k-ball branch weight centroid introduced by Reid (1991). In particular, this new family contains the classical central sets, the center and the median (which Zelinka (1968) showed is the ordinary branch weight centroid). The sets obtained for particular values of k and l are examined, and it is shown that for many values they consist of one vertex or two adjacent vertices.     

On the complex zeros of Hμ(z), J(z), J(z) for real or complex order

Propositions about the nonexistence of complex zeros of the functions H_μ(z)=J_μ(z)+zJ^′_μ(z),J^′_μ(z),J^″_μ(z), where J^′_μ(z) and J^″_μ(z) are the first two derivatives of the Bessel functions J_μ(z), for μ in general complex are proved. Bounds for the purely imaginary zeros of the above functions assuming their existence are given. Thus for the range of values for which these bounds are violated there are no purely imaginary zeros of the above functions. Finally, some known results from previous work are generalized in the present paper.