New Cyclic Difference Sets with Singer Parameters Constructed from d-Homogeneous Functions

In this paper, for a prime power q, new cyclic difference sets with Singer para- meters ((q ⁿ –1/q–1), (q ^n–1–1/q–1), (q ^n–2–1/q–1)) are constructed by using q-ary sequences (d-homogeneous functions) of period q ⁿ –1 and the generalization of GMW difference sets is proposed by combining the generation methods of d-form sequences and extended sequences. When q is a power of 3, new cyclic difference sets with Singer parameters ((q ⁿ –1/q–1), (q ^n–1–1/q–1), (q ^n–2–1/q–1)) are constructed from the ternary sequences of period q ⁿ –1 with ideal autocorrelation introduced by Helleseth, Kumar, and Martinsen.     

Cyclic Relative Difference Sets and their p-Ranks

By modifying the constructions in Helleseth et al. [10] and No [15], we construct a family of cyclic ((q ^3k –1)/(q–1), q–1, q ^3k–1, q ^3k–2) relative difference sets, where q=3 ^e . These relative difference sets are liftings of the difference sets constructed in Helleseth et al. [10] and No [15]. In order to demonstrate that these relative difference sets are in general new, we compute p-ranks of the classical relative difference sets and 3-ranks of the newly constructed relative difference sets when q=3. By rank comparison, we show that the newly constructed relative difference sets are never equivalent to the classical relative difference sets, and are in general inequivalent to the affine GMW difference sets.     

On the spectral function of the Poisson–Voronoi cells

Denote by (t)=∑_n1e^−λ_nt, t>0, the spectral function related to the Dirichlet Laplacian for the typical cell of a standard Poisson–Voronoi tessellation in . We show that the expectation E(t), t>0, is a functional of the convex hull of a standard d-dimensional Brownian bridge. This enables us to study the asymptotic behaviour of E(t), when t→0⁺,+∞. In particular, we prove that the law of the first eigenvalue λ₁ of satisfies the asymptotic relation lnP{λ₁t}−2^dω_dj_(d−2)/2^d·t^−d/2 when t→0⁺, where ω_d and j_(d−2)/2 are respectively the Lebesgue measure of the unit ball in and the first zero of the Bessel function J_(d−2)/2.     

Blocking Structures of Hermitian Varieties

Given a hermitian variety H(d,q²) and an integer k (d–1)/2, a blocking set with respect to k-subspaces is a set of points of H(d,q²) that meets all k-subspaces of H(d,q²). If H(d,q²) is naturally embedded in PG(d,q²), then linear examples for such a blocking set are the ones that lie in a subspace of codimension k of PG(d,q²). Up to isomorphism there are k+1 non-isomorphic minimal linear blocking sets, and these have different cardinalities. In this paper it is shown for 1 k< (d–1)/2 that all sufficiently small minimal blocking sets of H(d,q²) with respect to k-subspaces are linear. For 1 k< d/2–3, it is even proved that the k+1 minimal linear blocking sets are smaller than all minimal non-linear ones.AMS Classification: 1991 MSC: 51E20, 51E21     

A Construction of Difference Sets in High Exponent 2-Groups Using Representation Theory

Nontrivial difference sets in groups of order a power of 2 are part of the family of difference sets called Menon difference sets (or Hadamard), and they have parameters (2^2d+2, 2^2d+1±2 ^d , 2^2d ±2 ^d ). In the abelian case, the group has a difference set if and only if the exponent of the group is less than or equal to 2 ^d+2. In [14], the authors construct a difference set in a nonabelian group of order 64 and exponent 32. This paper generalizes that result to show that there is a difference set in a nonabelian group of order 2^2d+2 with exponent 2 ^d+3. We use representation theory to prove that the group has a difference set, and this shows that representation theory can be used to verify a construction similar to the use of character theory in the abelian case.     

Graceful Signed Graphs

A (p, q)-sigraph S is an ordered pair (G, s) where G = (V, E) is a (p, q)-graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E ⁺ and E ^– consist of m positive and n negative edges of G, respectively, where m + n = q. Given positive integers k and d, S is said to be (k, d)-graceful if the vertices of G can be labeled with distinct integers from the set {0, 1, ..., k + (q – 1)d such that when each edge uv of G is assigned the product of its sign and the absolute difference of the integers assigned to u and v the edges in E ⁺ and E ^– are labeled k, k + d, k + 2d, ..., k + (m – 1)d and –k, – (k + d), – (k + 2d), ..., – (k + (n – 1)d), respectively.In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of (k, d)-graceful graphs due to B. D. Acharya and S. M. Hegde.     

Regularized Resolvent of Sums of Commuting Operators

For B ₁ and B ₂ commuting linear operators on a Banach space such that B ₁ generates a bounded strongly continuous semigroup and –B ₂ generates an exponentially decaying strongly continuous holomorphic semigroup, it is shown that (B ₁ – B ₂)^–1 B ₂ ^–r and (B ₁ – B ₂)^–1(–B ₁)^–r are bounded and everywhere defined, for any r > 0. Density of domains may also be removed. The results are applied to various abstract Cauchy problems.     

Triangulating point sets in space

A setP ofn points inR ^d is called simplicial if it has dimensiond and contains exactlyd + 1 extreme points. We show that whenP containsn interior points, there is always one point, called a splitter, that partitionsP intod + 1 simplices, none of which contain more thandn/(d + 1) points. A splitter can be found inO(d ⁴ +nd ²) time. Using this result, we give anO(nd ⁴ log_1+1/d n) algorithm for triangulating simplicial point sets that are in general position. InR ³ we give anO(n logn +k) algorithm for triangulating arbitrary point sets, wherek is the number of simplices produced. We exhibit sets of 2n + 1 points inR ³ for which the number of simplices produced may vary between (n – 1)² + 1 and 2n – 2. We also exhibit point sets for which every triangulation contains a quadratic number of simplices.Research supported by the Natural Science and Engineering Research Council grant A3013 and the F.C.A.R. grant EQ1678.     

An exponent bound on skew Hadamard abelian difference sets

A difference setD in a groupG is called a skew Hadamard difference set (or an antisymmetric difference set) if and only ifG is the disjoint union ofD, D(^–1), and {1}, whereD(^–1)={d^–1|dD}. In this note, we obtain an exponent bound for non-elementary abelian groupG which admits a skew Hadamard difference set. This improves the bound obtained previously by Johnsen, Camion and Mann.     

Summability of orthogonal expansions of several variables

Summability of spherical h-harmonic expansions with respect to the weight function ∏_j=1^d |x_j|^2κ_j (κ_j0) on the unit sphere S^d−1 is studied. The main result characterizes the critical index of summability of the Cesàro (C,δ) means of the h-harmonic expansion; it is proved that the (C,δ) means of any continuous function converge uniformly in the norm of C(S^d−1) if and only if δ>(d−2)/2+∑_j=1^d κ_j−min_1jd κ_j. Moreover, it is shown that for each point not on the great circles defined by the intersection of the coordinate planes and S^d−1, the (C,δ) means of the h-harmonic expansion of a continuous function f converges pointwisely to f if δ>(d−2)/2. Similar results are established for the orthogonal expansions with respect to the weight functions ∏_j=1^d |x_j|^2κ_j(1−|x|²)^μ−1/2 on the unit ball B^d and ∏_j=1^d x_j^κ_j−1/2(1−|x|₁)^μ−1/2 on the simplex T^d. As a related result, the Cesàro summability of the generalized Gegenbauer expansions associated to the weight function |t|^2μ(1−t²)^λ−1/2 on [−1,1] is studied, which is of interest in itself.     

On point energies, separation radius and mesh norm for -extremal configurations on compact sets in

We investigate bounds for point energies, separation radius, and mesh norm of certain arrangements of N points on sets A from a class of d-dimensional compact sets embedded in R^d′, 1dd^′. We assume that these points interact through a Riesz potential V=|·|^-s, where s>0 and |·| is the Euclidean distance in . With and denoting, respectively, the separation radius and mesh norm of s-extremal configurations, which are defined to yield minimal discrete Riesz s-energy, we show, in particular, the following.(A) For the d-dimensional unit sphere and s<d-1, and, moreover, if sd-2. The latter result is sharp in the case s=d-2. In addition, point energies for s-extremal configurations are asymptotically equal. This observation relates to numerical experiments on observed scar defects in certain biological systems.(B) For and s>d, and the mesh ratio is uniformly bounded for a wide subclass of . We also conclude that point energies for s-extremal configurations have the same order, as N→∞.     

Comparison Theorems on Convex Hypersurfaces in Hadamard Manifolds

In a Hadamard manifold with sectional curvaturebounded from below by –k ₂ ², we give sharp upper estimates for the difference circumradius minus inradiusof a compact k ₂-convex domain, and we getalso estimates for the quotient (Total d-mean curvature)/Area of a convex domain.     

Algorithms for shortest paths and d-cycle problems

Let G be a weighted graph with n vertices and m edges. We address the d-cycle problem, i.e., the problem of finding a subgraph of minimum weight with given cyclomatic number d. Hartvigsen [Minimum path bases, J. Algorithms 15 (1993) 125–142] presented an algorithm with running time O(n²m) and O(n^2d−1m²) for the cyclomatic numbers d=1 and d2, respectively. Using a (d+1)-shortest-paths algorithm, we develop a new more efficient algorithm for the d-cycle problem with running time O(n^2d−1+n²m+n³logn).     

Combinatoriald-tori with a large symmetry group

We construct a sequence of combinatorial triangulations of thed-dimensional torus with 2 ^d+1–1 vertices and with a vertex transitive group action. This generalizes well-known constructions in the casesd=2 (7-vertex torus) andd=3.     

Note on induced subgraphs of the unit distance graphE n

The unit distance graphE ⁿ is the graph whose vertices are the points in Euclideann-space, and two vertices are adjacent if and only if the distance between them is 1. We prove that for anyn there is a finite bipartite graph which cannot be embedded inE ⁿ as an induced subgraph and that every finite graph with maximum degreed can be embedded inE ^N ,N=(d ³ –d)/2, as an induced subgraph.     

On Large Sets of v−1 L-Intersecting Steiner Triple Systems of Order v

This paper presents four new recursive constructions for large sets of v–1 STS(v). These facilitate the production of several new infinite families of such large sets. In particular, we obtain for each n2 a large set of 3 ⁿ –1 STS (3 ⁿ ) whose systems intersect in 0 or 3 blocks.     

On hyperplanes and polytopes

We call a convex subsetN of a convexd-polytopePE ^d ak-nucleus ofP ifN meets everyk-face ofP, where 0<k<d. We note thatP has disjointk-nuclei if and only if there exists a hyperplane inE ^d which bisects the (relative) interior of everyk-face ofP, and that this is possible only if [d+2/2]kd–1. Our main results are that any convexd-polytope with at most 2d–1 vertices (d3) possesses disjoint (d–1)-nuclei and that 2d–1 is the largest possible number with this property. Furthermore, every convexd-polytope with at most 2d facets (d3) possesses disjoint (d–1)-nuclei, 2d cannot be replaced by 2d+2, and ford=3, six cannot be replaced by seven.Partially supported by Hung. Nat. Found. for Sci. Research number 1238.Partially supported by the Natural Sciences and Engineering Council of Canada.Partially supported by N.S.F. grant number MCS-790251.     

On a relation between a cyclic relative difference set associated with the quadratic extensions of a finite field and the Szekeres difference sets

Letq 3 (mod 4) be a prime power and put . We consider a cyclic relative difference set with parametersq ²–1,q, 1,q–1 associated with the quadratic extension GF(q²)/GF((q). The even part and the odd part of the cyclic relative difference set taken modulon are supplementary difference sets. Moreover it turns out that their complementary subsets are identical with the Szekeres difference sets. This result clarifies the true nature of the Szekeres difference sets. We prove these results by using the theory of the relative Gauss sums.     

Curvatures and Currents for Unions of Sets with Positive Reach, II

A class of subsets of ^d which can berepresented as locally finite unions of sets with positive reach isconsidered. It plays a role in PDE's on manifolds with singularities.For such a set, the unit normal cycle (determining the d – 1curvature measures) is introduced as a (d – 1)-currentsupported by the unit normal bundle and its properties are established.It is shown that, under mild additional assumptions, the unit normalcycle (and, hence, also the curvature measures) of such a set can beapproximated by that of a close parallel body or, alternatively, by themirror image of that of the closure of the complement of the parallelbody (which has positive reach). Finally, the mixed curvature measuresof two sets of this class are introduced and a translative integralgeometric formula for curvature measures is proved.     

Testing satisfiability

Let Φ be a set of general boolean functions on n variables, such that each function depends on exactly k variables, and each variable can take a value from [1,d]. We say that Φ is ε-far from satisfiable, if one must remove at least εn^k functions in order to make the set of remaining functions satisfiable. Our main result is that if Φ is ε-far from satisfiable, then most of the induced sets of functions, on sets of variables of size c(k,d)/ε², are not satisfiable, where c(k,d) depends only on k and d. Using the above claim, we obtain similar results for k-SAT and k-NAEQ-SAT.Assume we relax the decision problem of whether an instance of one of the above mentioned problems is satisfiable or not, to the problem of deciding whether an instance is satisfiable or ε-far from satisfiable. While the above decision problems are NP-hard, our result implies that we can solve their relaxed versions, that is, distinguishing between satisfiable and ε-far from satisfiable instances, in randomized constant time.From the above result we obtain as a special case, previous results of Alon and Krivelevich, and of Czumaj and Sohler, concerning testing of graphs and hypergraphs colorability. We also discuss the difference between testing with one-sided and two-sided error.