Discrete Mathematics and Combinatorics Commons^™

Nested Hadamard Difference Sets, James A. Davis, Jonathan Jedwab

Department of Math & Statistics Faculty Publications

A Hadamard difference set (HDS) has the parameters (4N², 2N² − N, N² − N). In the abelian case it is equivalent to a perfect binary array, which is a multidimensional matrix with elements ±1 such that all out-of-phase periodic autocorrelation coefficients are zero. We show that if a group of the form H × Z²_p^r contains a (hp^2r, √hp^r(2√hp^r − 1), √hp^r(√hp^r − 1)) HDS (HDS), p a prime not dividing |H| …

Using The Simplex Code To Construct Relative Difference Sets In 2-Groups, James A. Davis, Surinder K. Sehgal

Department of Math & Statistics Faculty Publications

Relative Difference Sets with the parameters (2^a, 2^b, 2^a, 2^a-b) have been constructed many ways (see [2], [3], [5], [6], and [7] for examples). This paper modifies an example found in [1] to construct a family of relative difference sets in 2-groups that gives examples for b = 2 and b = 3 that have a lower rank than previous examples. The Simplex code is used in the construction.

The Link Between Scrambling Numbers And Derangements, Barry Balof, Eric Farmer, Jamie Kawabata

Mathematical Sciences Technical Reports (MSTR)

The group equation abcdef = dabecf can be reduced to the equation xcde = dxec. In general, we are interested in how many variables are needed to represent group equations in which the right side is a permutation of the variables on the left side. Scrambling numbers capture this information about a permutation. In this paper we present several facts about scrambling numbers, and expose a striking relationship between permutations that cannot be reduced and derangements.

Generalized Conjugacy Classes, Pramod N. Achar

Mathematical Sciences Technical Reports (MSTR)

Generalized conjugation is the action of a group on its underlying set given by (g,x) -> p(g)xg^-1, where p is some fixed endomorphism of G. Here we study combinatorial properties of the sizes of the orbits of the preceding action. In particular, we reduce the problem to a simpler case if p has nontrivial kernel, or if it is an inner automorphism, and we give a construction that allows a partial analysis in the general case.

Cwatsets: Weights, Cardinalities, And Generalizations, Richard Mohr

Mathematical Sciences Technical Reports (MSTR)

This report provides an upper bound on the average weight of an element in a cwatset and discusses the ratio of the cardinality of a cwatset to the cardinality of the group containing the cwatset. The concept of a generalized cwatset is also introduced.

Combinatorics And Campus Security, Arthur T. Benjamin

All HMC Faculty Publications and Research

One day I received electronic mail from our director of campus security [Gilbraith 1993]:

"I have a puzzle for you that has practical applications for me. I need to know how many different combinations there are for our combination locks. A lock has 5 buttons. In setting the combination you can use only 1button or as many as 5. Buttons may be pressed simultaneously and / or successively, but the same button cannot be used more than once in the same combination.

I had a student (obviously not a math major) email me that there are only 120 possibilities, but …

A Survey Of Hadamard Difference Sets, James A. Davis, Jonathan Jedwab

Department of Math & Statistics Faculty Publications

A (v, k, λ) difference set is a k-element subset D of a group G of order v for which the multiset {d₁d₂^-1 : d1, d₂ ∈ D, d₁ ≠ d₂} contains each nonidentity element of G exactly λ times. A difference set is called abelian, nonabelian or cyclic according to the properties of the underlying group. Difference sets are important in design theory because they are equivalent to symmetric (v, k, λ) designs with a regular automorphism group [L].

Exponent Bounds For A Family Of Abelian Difference Sets, K. T. Arasu, James A. Davis, Jonathan Jedwab, Siu Lun Ma, Robert L. Mcfarland

Department of Math & Statistics Faculty Publications

Which groups G contain difference sets with the parameters (v, k, λ)= (q³ + 2q² , q² + q, q), where q is a power of a prime p? Constructions of K. Takeuchi, R.L. McFarland, and J.F. Dillon together yield difference sets with these parameters if G contains an elementary abelian group of order q² in its center. A result of R.J. Turyn implies that if G is abelian and p is self-conjugate modulo the exponent of G, then a necessary condition for existence is that the exponent …

A Nonexistence Result For Abelian Menon Difference Sets Using Perfect Binary Arrays, K. T. Arasu, James A. Davis, Jonathan Jedwab

Department of Math & Statistics Faculty Publications

A Menon difference set has the parameters (4N², 2N²-N, N²-N). In the abelian case it is equivalent to a perfect binary array, which is a multi-dimensional matrix with elements ±1 such that all out-of-phase periodic autocorrelation coefficients are zero. Suppose that the abelian group H×K×Z_p^α contains a Menon difference set, where p is an odd prime, |K|=p^α, and p^j≡−1 (mod exp (H)) for some j. Using the viewpoint of perfect binary arrays we prove that K must be cyclic. A …

Analysis Of A Recurrence Arising From A Construction For Nonblocking Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

Define f on the integers n > 1 by the recurrence f(n) = min( n, min_m|n( 2f(m) + 3f(n/m) ). The function f has f(n) = n as its upper envelope, attained for all prime n.

The goal of this paper is to determine the corresponding lower envelope. It is shown that this has the form f(n) ~ C(log n)^{1 + 1/γ} for certain constants γ and C, in the sense that for any ε > 0, the inequality f(n) ≤ (C + ε)(log n)^{1 + 1/γ} holds for infinitely many n, while f(n) ≤ (C + ε)(log …

Analysis Of A Recurrence Arising From A Construction For Non-Blocking Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

Define f on the integers $n > 1$ by the recurrence $f( n ) = \min \{ n,\min _{m|n} 2f( m ) + 3f( n/m ) \}$. The function f has $f( n ) = n$ as its upper envelope, attained for all prime n. The goal of this paper is to determine the corresponding lower envelope. It is shown that this has the form $f( n ) \sim C( \log n )^{1 + 1/\gamma } $ for certain constants $\gamma $ and C, in the sense that for any $\varepsilon > 0$, the inequality $f( n ) \leq ( …

Research Announcement: Recursive Construction For Families Of Difference Sets, James A. Davis, Jonathan Jedwab

Department of Math & Statistics Faculty Publications

A (v, k, λ) difference set is a k-element subset D of a group G of order v for which the multiset {d₁d₂^-1 : d1, d_2, ∈ D} contains each nonzero element of G exactly λ times; n = k-λ.

Review Of “Linear Programming And Related Problems” By E. Nering And A. W. Tucker, Stephen B. Maurer

Mathematics & Statistics Faculty Works

No abstract provided.

Partial Difference Sets In P-Groups, James A. Davis

Department of Math & Statistics Faculty Publications

Most of the examples of PDS have come in p-groups, and most of these examples are in elementary abelian p-groups. In this paper, we will show an exponent bound for PDS with the same parameters as the elementary abelian case.

Average Genus Of The Cube, Jody Koenemann

Honors Theses

In recent years, there has been interest in the mathematical community in a rapidly developing branch of theoretical mathematics known as random topological graph theory. This new area of mathematics explores the different ways in which certain graphs can be imbedded in given surfaces. The random nature of the new branch results when one also imposes a random distribution on set of all imbeddings of a fixed graph, via the orientation of the edges at each vertex. Using the technique of J. Edmonds, developed in 1960, this paper explores the imbeddings for the graph Q₃ using a particular group …

Third Order Degree Regular Graphs, Leslie D. Hayes

Honors Theses

A graph G is regular of degree d if for every vertex v in G there exist exactly d vertices at distance 1 from v. A graph G is kth order regular of degree d if for every vertex v in G, there exist exactly d vertices at distance k from v. In this paper, third order regular graphs of degree 1 with small order are characterized.

A Construction Of Difference Sets In High Exponent 2-Groups Using Representation Theory, James A. Davis, Ken Smith

Department of Math & Statistics Faculty Publications

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 …

Fault-Tolerant Circuit-Switching Networks, Nicholas Pippenger, Geng Lin

All HMC Faculty Publications and Research

The authors consider fault-tolerant circuit-switching networks under a random switch failure model. Three circuit-switching networks of theoretical importance—nonblocking networks, rearrangeable networks, and superconcentrators—are studied. The authors prove lower bounds for the size (the number of switches) and depth (the largest number of switches on a communication path) of such fault-tolerant networks and explicitly construct such networks with optimal size Θ( n (log n)² ) and depth Θ( log n ).

New Constructions Of Menon Difference Sets, K. T. Arasu, James A. Davis, Jonathan Jedwab, Surinder K. Sehgal

Department of Math & Statistics Faculty Publications

Menon difference sets have parameters (4N², 2N² − N, N² − N). These have been constructed for N = 2^a3^b, 0 ⩽ a,b, but the only known constructions in abelian groups require that the Sylow 3-subgroup be elementary abelian (there are some nonabelian examples). This paper provides a construction of difference sets in higher exponent groups, and this provides new examples of perfect binary arrays.

A Note On New Semi-Regular Divisible Difference Sets, James A. Davis, Jonathan Jedwab

Department of Math & Statistics Faculty Publications

We give a construction for new families of semi-regular divisible difference sets. The construction is a variation of McFarland's scheme [5] tor noncyclic difference sets.

Rely To "Comment On 'Nonexistence Of Certain Perfect Binary Arrays' And 'Nonexistence Of Perfect Binary Arrays'", Jonathan Jedwab, James A. Davis

Department of Math & Statistics Faculty Publications

Yang's comment [C] is based on a lemma which claims to construct an s₀ x s₁ x s₂ x ... x s, perfect binary array (PBA) from an s₀s₁ x s₂ x ... x s_r PBA.

Hypergraph Representations And Orders Of Cwatsets, Julie Kerr

Mathematical Sciences Technical Reports (MSTR)

We determine upper bounds on the order of cwatsets of odd order.

Optimal Leapfrogging, Joel Auslander, Arthur T. Benjamin, Daniel S. Wilkerson

All HMC Faculty Publications and Research

No abstract provided in this article.

Nonexistence Of Certain Perfect Binary Arrays, Jonathan Jedwab, James A. Davis

Department of Math & Statistics Faculty Publications

A perfect binary array (PBA) is an r-dimensional matrix with elements ±I such that all out-of-phase periodic autocorrelation coefficients are zero. The two smallest sizes for which the existence of a PBA is undecided, 2 x 2 x 3 x 3 x 9 and 4 x 3 x 3 x 9, are ruled out using computer search and a combinatorial argument.

A Summary Of Menon Difference Sets, James A. Davis, Jonathan Jedwab

Department of Math & Statistics Faculty Publications

A (v, k, λ) difference set is a k-element subset D of a group G of order v for which the multiset {d₁d₂^-1 : d_1,d₂ ∈ D, d₁ ≠ d₂} contains each nonidentity element of G exactly λ times. A difference set is called abelian, nonabelian or cyclic if the underlying group is. Difference sets a.re important in design theory because they a.re equivalent to symmetric (v, k, λ) designs with a regular automorphism group. Abelian difference sets arise naturally in …

Almost Difference Sets And Reversible Divisible Difference Sets, James A. Davis

Department of Math & Statistics Faculty Publications

Let G be a group of order mn and N a subgroup of G of order n. If D is a k-subset of G, then D is called a (m, n, k, λ₁, λ₂) divisible difference set (DDS) provided that the differences dd^'-1 for d, d' ∈ D, d ≠ d' contain every nonidentity element of N exactly λ₁ times and every element of G - N exactly λ₂ times. Difference sets are used to generate designs, as described by [4] and [9]. D will be …

Another Way Of Counting Nᴺ, Arthur T. Benjamin, Fritz Juhnke

All HMC Faculty Publications and Research

An original combinatorial proof of a combinatorial identity is presented.

Construction Of Relative Difference Sets In P-Groups, James A. Davis

Department of Math & Statistics Faculty Publications

Jungnickel (1982) and Elliot and Butson (1966) have shown that (p^j+1,p,p^j+1,p^j) relative difference sets exist in the elementary abelian p-group case (p an odd prime) and many 2-groups for the case p = 2. This paper provides two new constructions of relative difference sets with these parameters; the first handles any p-group (including non-abelian) with a special subgroup if j is odd, and any 2-group with that subgroup if j is even. The second construction shows that if j is odd, every abelian group …

An Exponent Bound For Relative Difference Sets In P-Groups, James A. Davis

Department of Math & Statistics Faculty Publications

An exponent bound is presented for abelian (p^i+j, pⁱ, p^i+j, pⁱ) relative difference sets: this bound can be met for i≤j.

A Theorem On Reproducing Kernel Hilbert Spaces Of Pairs, Daniel Alpay

Mathematics, Physics, and Computer Science Faculty Articles and Research

In this paper we study reproducing kernel Hilbert and Banach spaces of pairs. These are a generalization of reproducing kernel Krein spaces and, roughly speaking, consist of pairs of Hilbert (or Banach) spaces of functions in duality with respect to a sesquilinear form and admitting a left and right reproducing kernel. We first investigate some properties of these spaces of pairs. It is then proved that to every function K(z, ω) analytic in z and ω* there is a neighborhood of the origin that can be associated with a reproducing kernel Hilbert space of pairs with left reproducing kernel K(z, …