Bounding the diameter of a distance-transitive graph

A graph Γ is distance-transitive if for all vertices u, v, x, y such that d(u, v) = d(x, y) there is an automorphism h of Γ such that uh = x, vh = y. We show how to find a bound for the diameter of a bipartite distance-transitive graph given a bound for the order |G_α| of the stabilizer of a vertex.     

Upper bounds for configurations and polytopes inR d

We give a new upper bound onn ^d(d+1)n on the number of realizable order types of simple configurations ofn points inR ^d , and ofn2d ² n on the number of realizable combinatorial types of simple configurations. It follows as a corollary of the first result that there are no more thann ^d(d+1)n combinatorially distinct labeled simplicial polytopes inR ^d withn vertices, which improves the best previous upper bound ofn ^{cn d/2}.Supported in part by NSF Grant DMS-8501492 and PSC-CUNY Grant 665258.Supported in part by NSF Grant DMS-8501947.     

Strengthened semidefinite programming bounds for codes

We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular ∗-representation for matrix ∗-algebras. The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inform. Theory 51:2859–2866, 2005) is located between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with O(n ⁷) variables and thus seems out of reach for interesting values of n, Schrijver’s bound can be computed via a semidefinite program of size O(n ³), a result which uses the explicit block-diagonalization of the Terwilliger algebra. We propose two strengthenings of Schrijver’s bound with the same computational complexity. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.     

The Overlay of Minimization Diagrams in a Randomized Incremental Construction

In a randomized incremental construction of the minimization diagram of a collection of n hyperplanes in ℝ ^d , for d≥2, the hyperplanes are inserted one by one, in a random order, and the minimization diagram is updated after each insertion. We show that if we retain all the versions of the diagram, without removing any old feature that is now replaced by new features, the expected combinatorial complexity of the resulting overlay does not grow significantly. Specifically, this complexity is O(n ^⌊d/2⌋log n), for d odd, and O(n ^⌊d/2⌋), for d even. The bound is asymptotically tight in the worst case for d even, and we show that this is also the case for d=3. Several implications of this bound, mainly its relation to approximate halfspace range counting, are also discussed.     

Zero Divisor Graph for the Ring of Gaussian Integers Modulo n

This article studies the zero divisor graph for the ring of Gaussian integers modulo n, Γ (? _n [i]). For each positive integer n, the number of vertices, the diameter, the girth and the case when the dominating number is 1 or 2 is found.

Complete characterizations, in terms of n, are given of the cases in which Γ (? _n [i]) is complete, complete bipartite, planar, regular or Eulerian.     

On the upper bounds of the minimum number of rows of disjunct matrices

A 0-1 matrix is d-disjunct if no column is covered by the union of any d other columns. A 0-1 matrix is (d; z)-disjunct if for any column C and any d other columns, there exist at least z rows such that each of them has value 1 at column C and value 0 at all the other d columns. Let t(d, n) and t(d, n; z) denote the minimum number of rows required by a d-disjunct matrix and a (d; z)-disjunct matrix with n columns, respectively. We give a very short proof for the currently best upper bound on t(d, n). We also generalize our method to obtain a new upper bound on t(d, n; z). The work of Y. Cheng and G. Lin is supported by Natural Science and Engineering Research Council (NSERC) of Canada, and the Alberta Ingenuity Center for Machine Learning (AICML) at the University of Alberta. The work of D.-Z. Du is partially supported by National Science Foundation under grant No.CCF0621829.     

Holder Norm Estimate for a Hilbert Transform in Hermitean Clifford Analysis

A Hilbert transform for H?lder continuous circulant (2 × 2) matrix functions, on the d-summable (or fractal) boundary Γ of a Jordan domain Ω in ?²ⁿ , has recently been introduced within the framework of Hermitean Clifford analysis. The main goal of the present paper is to estimate the H?lder norm of this Hermitean Hilbert transform. The expression for the upper bound of this norm is given in terms of the H?lder exponents, the diameter of Γ and a specific d-sum (d > d) of the Whitney decomposition of Ω. The result is shown to include the case of a more standard Hilbert transform for domains with left Ahlfors-David regular boundary.     

Constructions for Permutation Codes in Powerline Communications

A permutation array (or code) of length n and distance d is a set Γ of permutations from some fixed set of n symbols such that the Hamming distance between each distinct x, y ∈ Γ is at least d. One motivation for coding with permutations is powerline communication. After summarizing known results, it is shown here that certain families of polynomials over finite fields give rise to permutation arrays. Additionally, several new computational constructions are given, often making use of automorphism groups. Finally, a recursive construction for permutation arrays is presented, using and motivating the more general notion of codes with constant weight composition.     

Atomic decompositions of function spaces with Muckenhoupt weights,and some relation to fractal analysis

This paper deals with atomic decompositions in spaces of type B^s_p,q (?ⁿ , w), F^s_p,q (?ⁿ , w), 0 < p < ∞, 0 < q ≤ ∞, s ∈ ?, where the weight function w belongs to some Muckenhoupt class A_r. In particular, we consider the weight function w^Γ_κ (x) = dist(x, Γ)^κ, where Γ is some d ‐set, 0 < d < n, and κ > –(n – d). (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

From regular boundary graphs to antipodal distance-regular graphs

Let Γ be a regular graph with n vertices, diameter D, and d + 1 different eigenvalues λ > λ₁ > ··· > λ_d. In a previous paper, the authors showed that if P(λ) > n − 1, then D ≤ d − 1, where P is the polynomial of degree d − 1 which takes alternating values ± 1 at λ₁, …, λ_d. The graphs satisfying P(λ) = n − 1, called boundary graphs, have shown to deserve some attention because of their rich structure. This paper is devoted to the study of this case and, as a main result, it is shown that those extremal (D = d) boundary graphs where each vertex have maximum eccentricity are, in fact, 2-antipodal distance-regular graphs. The study is carried out by using a new sequence of orthogonal polynomials, whose special properties are shown to be induced by their intrinsic symmetry. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 123–140, 1998     

Constructions of Spherical 3-Designs

 Spherical t-designs are Chebyshev-type averaging sets on the d-sphere which are exact for polynomials of degree at most t. This concept was introduced in 1977 by Delsarte, Goethals, and Seidel, who also found the minimum possible size of such designs, in particular, that the number of points in a 3-design on S ^d must be at least . In this paper we give explicit constructions for spherical 3-designs on S ^d consisting of n points for d=1 and ; d=2 and ; d=3 and ; d=4 and ; and odd or even. We also provide some evidence that 3-designs of other sizes do not exist. We will introduce and apply a concept from additive number theory generalizing the classical Sidon-sequences. Namely, we study sets of integers S for which the congruence mod n, where and , only holds in the trivial cases. We call such sets Sidon-type sets of strength t, and denote their maximum cardinality by s(n, t). We find a lower bound for s(n, 3), and show how Sidon-type sets of strength 3 can be used to construct spherical 3-designs. We also conjecture that our lower bound gives the true value of s(n, 3) (this has been verified for n≤125). Received: June 19, 1996     

Sparse random graphs: Eigenvalues and eigenvectors

In this paper, we prove the semi‐circular law for the eigenvalues of regular random graph G_n,d in the case d →∞, complementing a previous result of McKay for fixed d. We also obtain a upper bound on the infinity norm of eigenvectors of Erd?s–Rényi random graph G(n,p), answering a question raised by Dekel–Lee–Linial. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Generalizations of Heilbronn’s triangle problem

For given integers d,j≥2 and any positive integers n, distributions of n points in the d-dimensional unit cube [0,1]^d are investigated, where the minimum volume of the convex hull determined by j of these n points is large. In particular, for fixed integers d,k≥2 the existence of a configuration of n points in [0,1]^d is shown, such that, simultaneously for j=2,…,k, the volume of the convex hull of any j points among these n points is Ω(1/n^{(j−1)/(1+|d−j+1|)}). Moreover, a deterministic algorithm is given achieving this lower bound, provided that d+1≤j≤k.     

Universal adjacency matrices with two eigenvalues

Consider a graph Γ on n vertices with adjacency matrix A and degree sequence (d₁,…,d_n). A universal adjacency matrix of Γ is any matrix in Span {A,D,I,J} with a nonzero coefficient for A, where and I and J are the n×n identity and all-ones matrix, respectively. Thus a universal adjacency matrix is a common generalization of the adjacency, the Laplacian, the signless Laplacian and the Seidel matrix. We investigate graphs for which some universal adjacency matrix has just two eigenvalues. The regular ones are strongly regular, complete or empty, but several other interesting classes occur.     

Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups

In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph Γ is n‐HC‐extendable if it contains a path of length n and if every such path is contained in some Hamilton cycle of Γ. Similarly, Γ is weakly n‐HP‐extendable if it contains a path of length n and if every such path is contained in some Hamilton path of Γ. Moreover, Γ is strongly n‐HP‐extendable if it contains a path of length n and if for every such path P there is a Hamilton path of Γ starting with P. These concepts are then studied for the class of connected Cayley graphs on abelian groups. It is proved that every connected Cayley graph on an abelian group of order at least three is 2‐HC‐extendable and a complete classification of 3‐HC‐extendable connected Cayley graphs of abelian groups is obtained. Moreover, it is proved that every connected Cayley graph on an abelian group of order at least five is weakly 4‐HP‐extendable. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

Polar boundary sets for superdiffusions and removable lateral singularities for nonlinear parabolic PDEs

Suppose L is a second-order elliptic differential operator in ℝ^d and D is a bounded, smooth domain in ℝ^d. Let 1 < α ≤ 2 and let Γ be a closed subset of ∂D. It is known [13] that the following three properties are equivalent: (α) Γ is ∂-polar; that is, Γ is not hit by the range of the corresponding (L, α)-superdiffusion in D; (β) the Poisson capacity of Γ is equal to 0; that is, the integral is equal to 0 or ∞ for every measure ν, where ρ(x) is the distance to the boundary and k(x, y) is the corresponding Poisson kernel; and (γ) Γ is a removable boundary singularity for the equation Lu = u^α in D; that is, if u ≥ 0 and Lu = u^α in D and if u = 0 on ∂D \ Γ, then u = 0. We investigate a similar problem for a parabolic operator in a smooth cylinder 𝒬 = ℝ₊ × D. Let Γ be a compact set on the lateral boundary of 𝒬. We show that the following three properties are equivalent: (a) Γ is 𝒢-polar; that is, Γ is not hit by the graph of the corresponding (L, α)-superdiffusion in 𝒬; (b) the Poisson capacity of Γ is equal to 0; that is, the integral is equal to 0 or ∞ for every measure ν, where k(r, x; t, y) is the corresponding (parabolic) Poisson kernel; and (c) Γ is a removable lateral singularity for the equation u˙ + Lu = u^α in 𝒬; that is, if u ≥ 0 and u˙ + Lu = u^α in 𝒬 and if u = 0 on ∂𝒬 \ Γ and on {∞} × D, then u = 0. © 1998 John Wiley & Sons, Inc.     

Bounds on Codes Derived by Counting Components in Varshamov Graphs

We are interested in improving the Varshamov bound for finite values of length n and minimum distance d. We employ a counting lemma to this end which we find particularly useful in relation to Varshamov graphs. Since a Varshamov graph consists of components corresponding to low weight vectors in the cosets of a code it is a useful tool when trying to improve the estimates involved in the Varshamov bound. We consider how the graph can be iteratively constructed and using our observations are able to achieve a reduction in the over-counting which occurs. This tightens the lower bound for any choice of parameters n, k, d or q and is not dependent on information such as the weight distribution of a code. This work is taken from the author’s thesis [10]     

Graphs of order two less than the Moore bound

The problem of determining the largest order n_d,k of a graph of maximum degree at most d and diameter at most k is well known as the degree/diameter problem. It is known that n_d,k?M_d,k where M_d,k is the Moore bound. For d=4, the current best upper bound for n_4,k is M_4,k-1. In this paper we study properties of graphs of order M_d,k-2 and we give a new upper bound for n_4,k for k?3.     

Channel assignment on Cayley graphs

We address various channel assignment problems on the Cayley graphs of certain groups, computing the frequency spans by applying group theoretic techniques. In particular, we show that if G is the Cayley graph of an n‐generated group Γ with a certain kind of presentation, then λ(G;k, 1)≤2(k+n?1). For certain values of k this bound gives the obvious optimal value for any 2n‐regular graph. A large number of groups (for instance, even Artin groups and a number of Baumslag–Solitar groups) satisfy this condition. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 169‐177, 2011     

Hypercube subgraphs with minimal detours

Define a minimal detour subgraph of the n-dimensional cube to be a spanning subgraph G of Q_n having the property that for vertices x, y of Q_n, distances are related by d_G(x, y) ≤ d_Qn(x, y) + 2. Let f(n) be the minimum number of edges of such a subgraph of Q_n. After preliminary work on distances in subgraphs of product graphs, we show that The subgraphs we construct to establish this bound have the property that the longest distances are the same as in Q_n, and thus the diameter does not increase. We establish a lower bound for f(n), show that vertices of high degree must be distributed throughout a minimal detour subgraph of Q_n, and end with conjectures and questions. © 1996 John Wiley & Sons, Inc.