Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
-
- Difference set (8)
- Difference sets (8)
- Abelian group (6)
- Perfect binary array (5)
- Abelian 2-groups (3)
-
- Abelian difference sets (3)
- Combinatorics (3)
- Combinatronics (3)
- Hadamard difference set (3)
- Nonabelian group (3)
- Abelian groups (2)
- Different sets (2)
- Divisible difference sets (2)
- Elementary abelian group of order (2)
- Finite abelian group (2)
- Hadamard (2)
- McFarland (2)
- Nonabelian difference sets (2)
- P-group (2)
- P-groups (2)
- P-subgroup (2)
- Relative difference set (2)
- Representation theory (2)
- 2-groups (1)
- Abelian menon difference sets (1)
- Alquaddoomi conjecture (1)
- Barker array (1)
- Barker array conjecture (1)
- Binary arrays (1)
- Binary sequences (1)
Articles 1 - 29 of 29
Full-Text Articles in Discrete Mathematics and Combinatorics
Classifying Coloring Graphs, Julie Beier, Janet Fierson, Ruth Haas, Heather M. Russell, Kara Shavo
Classifying Coloring Graphs, Julie Beier, Janet Fierson, Ruth Haas, Heather M. Russell, Kara Shavo
Department of Math & Statistics Faculty Publications
Given a graph G, its k-coloring graph is the graph whose vertex set is the proper k-colorings of the vertices of G with two k-colorings adjacent if they differ at exactly one vertex. In this paper, we consider the question: Which graphs can be coloring graphs? In other words, given a graph H, do there exist G and k such that H is the k-coloring graph of G? We will answer this question for several classes of graphs and discuss important obstructions to being a coloring graph involving order, girth, and induced subgraphs.
On The Non-Existence Of A Projective (75, 4,12, 5) Set In Pg(3, 7), Aaron C.S. Chan, James A. Davis, Jonathan Jedwab
On The Non-Existence Of A Projective (75, 4,12, 5) Set In Pg(3, 7), Aaron C.S. Chan, James A. Davis, Jonathan Jedwab
Department of Math & Statistics Faculty Publications
We show by a combination of theoretical argument and computer search that if a projective (75, 4, 12, 5) set in PG(3, 7) exists then its automorphism group must be trivial. This corresponds to the smallest open case of a coding problem posed by H. Ward in 1998, concerning the possible existence of an infinite family of projective two-weight codes meeting the Griesmer bound.
G-Perfect Nonlinear Functions, James A. Davis, Laurent Poinsot
G-Perfect Nonlinear Functions, James A. Davis, Laurent Poinsot
Department of Math & Statistics Faculty Publications
Perfect nonlinear functions are used to construct DES-like cryptosystems that are resistant to differential attacks. We present generalized DES-like cryptosystems where the XOR operation is replaced by a general group action. The new cryptosystems, when combined with G-perfect nonlinear functions (similar to classical perfect nonlinear functions with one XOR replaced by a general group action), allow us to construct systems resistant to modified differential attacks. The more general setting enables robust cryptosystems with parameters that would not be possible in the classical setting. We construct several examples of G-perfect nonlinear functions, both Z2 -valued and Za …
Proof Of The Barker Array Conjecture, James A. Davis, Jonathan Jedwab, Ken W. Smith
Proof Of The Barker Array Conjecture, James A. Davis, Jonathan Jedwab, Ken W. Smith
Department of Math & Statistics Faculty Publications
Using only elementary methods, we prove Alquaddoomi and Scholtz’s conjecture of 1989, that no s × t Barker array having s, t > 1 exists except when s = t = 2.
Peak-To-Mean Power Control In Ofdm, Golay Complementary Sequences, And Reed–Muller Codes, James A. Davis, Jonathan Jedwab
Peak-To-Mean Power Control In Ofdm, Golay Complementary Sequences, And Reed–Muller Codes, James A. Davis, Jonathan Jedwab
Department of Math & Statistics Faculty Publications
We present a range of coding schemes for OFDM transmission using binary, quaternary, octary, and higher order modulation that give high code rates for moderate numbers of carriers. These schemes have tightly bounded peak-to-mean envelope power ratio (PMEPR) and simultaneously have good error correction capability. The key theoretical result is a previously unrecognized connection between Golay complementary sequences and second-order Reed–Muller codes over alphabets ℤ2h. We obtain additional flexibility in trading off code rate, PMEPR, and error correction capability by partitioning the second-order Reed–Muller code into cosets such that codewords with large values of PMEPR are isolated. …
Some Recent Developments In Difference Sets, James A. Davis, Jonathan Jedwab
Some Recent Developments In Difference Sets, James A. Davis, Jonathan Jedwab
Department of Math & Statistics Faculty Publications
There are five known parameter families for (v, k, λ, n)- difference sets satisfying gcd(v, n)>1: the Hadamard, McFarland, Spence, Davis-Jedwab, and Chen families. The authors recently gave a recursive unifying construction for difference sets from the first four families which relies on relative difference sets. We give an overview of this construction and show that, by modifying it to use divisible difference sets in place of relative difference sets, the recent difference set discoveries of Chen can be brought within the unifying framework. We also demonstrate the recursive use of an auxiliary construction for …
A Unified Approach To Difference Sets With Gcd(V, N) > 1, James A. Davis, Jonathan Jedwab
A Unified Approach To Difference Sets With Gcd(V, N) > 1, James A. Davis, Jonathan Jedwab
Department of Math & Statistics Faculty Publications
The five known families of difference sets whose parameters (v, k, λ; n) satisfy the condition gcd(v,n) > 1 are the McFarland, Spence, Davis-Jedwab, Hadamard and Chen families. We survey recent work which uses recursive techniques to unify these difference set families, placing particular emphasis on examples. This unified approach has also proved useful for studying semi-regular relative difference sets and for constructing new symmetric designs.
New Semiregular Divisible Difference Sets, James A. Davis
New Semiregular Divisible Difference Sets, James A. Davis
Department of Math & Statistics Faculty Publications
We modify and generalize the construction by McFarland (1973) in two different ways to construct new semiregular divisible difference sets (DDSs) with λ1≠0. The parameters of the DDS fall into a family of parameters found in Jungnickel (1982), where his construction is for divisible designs. The final section uses the idea of a K-matrix to find DDSs with a nonelementary abelian forbidden subgroup.
Hadamard Difference Sets In Nonabelian 2-Groups With High Exponent, James A. Davis, Joel E. Iiams
Hadamard Difference Sets In Nonabelian 2-Groups With High Exponent, James A. Davis, Joel E. Iiams
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 Hadamard difference sets. In the abelian case, a group of order 22t + 2 has a difference set if and only if the exponent of the group is less than or equal to 2t + 2. In a previous work (R. A. Liebler and K. W. Smith, in “Coding Theory, Design Theory, Group Theory: Proc. of the Marshall Hall Conf.,” Wiley, New York, 1992), the authors constructed a difference set in a nonabelian group of order …
A Unifying Construction For Difference Sets, James A. Davis, Jonathan Jedwab
A Unifying Construction For Difference Sets, James A. Davis, Jonathan Jedwab
Department of Math & Statistics Faculty Publications
We present a recursive construction for difference sets which unifies the Hadamard, McFarland, and Spence parameter families and deals with all abelian groups known to contain such difference sets. The construction yields a new family of difference sets with parameters (v, k, λ,n)=(22d+4(22d+2−1)/3, 22d+1(22d+3+1)/3, 22d+1(22d+1+1)/3, 24d+2) for d⩾0. The construction establishes that a McFarland difference set exists in an abelian group of order 22 …
Nested Hadamard Difference Sets, James A. Davis, Jonathan Jedwab
Nested Hadamard Difference Sets, James A. Davis, Jonathan Jedwab
Department of Math & Statistics Faculty Publications
A Hadamard difference set (HDS) has the parameters (4N2, 2N2 − N, N2 − 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 × Z2pr contains a (hp2r, √hpr(2√hpr − 1), √hpr(√hpr − 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
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 (2a, 2b, 2a, 2a-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.
Exponent Bounds For A Family Of Abelian Difference Sets, K. T. Arasu, James A. Davis, Jonathan Jedwab, Siu Lun Ma, Robert L. Mcfarland
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, λ)= (q3 + 2q2 , q2 + 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 q2 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 Survey Of Hadamard Difference Sets, James A. Davis, Jonathan Jedwab
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 {d1d2-1 : d1, d2 ∈ D, d1 ≠ d2} 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].
A Nonexistence Result For Abelian Menon Difference Sets Using Perfect Binary Arrays, K. T. Arasu, James A. Davis, Jonathan Jedwab
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 (4N2, 2N2-N, N2-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×Zpα contains a Menon difference set, where p is an odd prime, |K|=pα, and pj≡−1 (mod exp (H)) for some j. Using the viewpoint of perfect binary arrays we prove that K must be cyclic. A …
Research Announcement: Recursive Construction For Families Of Difference Sets, James A. Davis, Jonathan Jedwab
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 {d1d2-1 : d1, d2, ∈ D} contains each nonzero element of G exactly λ times; n = k-λ.
Partial Difference Sets In P-Groups, James A. Davis
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.
A Construction Of Difference Sets In High Exponent 2-Groups Using Representation Theory, James A. Davis, Ken Smith
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 (22d+2, 22d+1 ±2d, 22d±2d). 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 2d+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 …
New Constructions Of Menon Difference Sets, K. T. Arasu, James A. Davis, Jonathan Jedwab, Surinder K. Sehgal
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 (4N2, 2N2 − N, N2 − N). These have been constructed for N = 2a3b, 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
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
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 s0 x s1 x s2 x ... x s, perfect binary array (PBA) from an s0s1 x s2 x ... x sr PBA.
Nonexistence Of Certain Perfect Binary Arrays, Jonathan Jedwab, James A. Davis
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
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 {d1d2-1 : d1,d2 ∈ D, d1 ≠ d2} 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
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, λ1, λ2) divisible difference set (DDS) provided that the differences dd'-1 for d, d' ∈ D, d ≠ d' contain every nonidentity element of N exactly λ1 times and every element of G - N exactly λ2 times. Difference sets are used to generate designs, as described by [4] and [9]. D will be …
Construction Of Relative Difference Sets In P-Groups, James A. Davis
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 (pj+1,p,pj+1,pj) 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
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 (pi+j, pi, pi+j, pi) relative difference sets: this bound can be met for i≤j.
Difference Sets In Abelian 2-Groups, James A. Davis
Difference Sets In Abelian 2-Groups, James A. Davis
Department of Math & Statistics Faculty Publications
Examples of difference sets are given for large classes of abelian groups of order 22d + 2. This fills in the gap of knowledge between Turyn's exponent condition and Dillon's rank condition. Specifically, it is shown thatℤ/(2d)×ℤ/(2d+2) andℤ/(2d+1)×Z/(2d+1) both admit difference sets, and these have many implications.
A Note On Nonabelian (64, 28, 12) Difference Sets, James A. Davis
A Note On Nonabelian (64, 28, 12) Difference Sets, James A. Davis
Department of Math & Statistics Faculty Publications
The existence of difference sets in abelian 2-groups is a recently settled problem [5]; this note extends the abelian constructs of difference sets to nonabelian groups of order 64.
A Note On Intersection Numbers Of Difference Sets, K. T. Arasu, James A. Davis, Dieter Jungnickel, Alexander Pott
A Note On Intersection Numbers Of Difference Sets, K. T. Arasu, James A. Davis, Dieter Jungnickel, Alexander Pott
Department of Math & Statistics Faculty Publications
We present a condition on the intersection numbers of difference sets which follows from a result of Jungnickel and Pott [3]. We apply this condition to rule out several putative (non-abelian) difference sets and to correct erroneous proofs of Lander [4] for the nonexistence of (352, 27, 2)- and (122, 37, 12)-difference sets.