Strongly regular Cayley graphs,skew Hadamard difference sets,and rationality of relative Gauss sums

In this paper, we give constructions of strongly regular Cayley graphs and skew Hadamard difference sets. Both constructions are based on choosing cyclotomic classes in finite fields. Our results generalize ten of the eleven sporadic examples of cyclotomic strongly regular graphs given by Schmidt and White (2002) [23] and several subfield examples into infinite families. These infinite families of strongly regular graphs have new parameters. The main tools that we employed are relative Gauss sums instead of explicit evaluations of Gauss sums.     

Pseudo-Paley graphs and skew Hadamard difference sets from presemifields

Let (K, + ,*) be an odd order presemifield with commutative multiplication. We show that the set of nonzero squares of (K, *) is a skew Hadamard difference set or a Paley type partial difference set in (K, +) according as q is congruent to 3 modulo 4 or q is congruent to 1 modulo 4. Applying this result to the Coulter–Matthews presemifield and the Ding–Yuan variation of it, we recover a recent construction of skew Hadamard difference sets by Ding and Yuan [7]. On the other hand, applying this result to the known presemifields with commutative multiplication and having order q congruent to 1 modulo 4, we construct several families of pseudo-Paley graphs. We compute the p-ranks of these pseudo-Paley graphs when q = 3⁴, 3⁶, 3⁸, 3¹⁰, 5⁴, and 7⁴. The p-rank results indicate that these graphs seem to be new. Along the way, we also disprove a conjecture of René Peeters [17, p. 47] which says that the Paley graphs of nonprime order are uniquely determined by their parameters and the minimality of their relevant p-ranks. Dedicated to Dan Hughes on the occasion of his 80th birthday.     

Some results on strongly regular graphs from unions of cyclotomic classes

In this paper, we construct some families of strongly regular graphs on finite fields by using unions of cyclotomic classes and index 2 Gauss sums. New infinite families of strongly regular graphs are found.     

Constructions of strongly regular Cayley graphs using index four Gauss sums

We give a construction of strongly regular Cayley graphs on finite fields $\mathbb{F}_{q}$ by using union of cyclotomic classes and index 4 Gauss sums. In particular, we obtain two infinite families of strongly regular graphs with new parameters.     

Strongly regular Cayley graphs from partitions of subdifference sets of the Singer difference sets

In this paper, we give a new lifting construction of “hyperbolic” type of strongly regular Cayley graphs. Also we give new constructions of strongly regular Cayley graphs over the additive groups of finite fields based on partitions of subdifference sets of the Singer difference sets. Our results unify some recent constructions of strongly regular Cayley graphs related to m-ovoids and i-tight sets in finite geometry. Furthermore, some of the strongly regular Cayley graphs obtained in this paper are new or nonisomorphic to known strongly regular graphs with the same parameters.     

Subgroup regular sets in Cayley graphs

Let Γ be a graph with vertex set V, and let a and b be nonnegative integers. A subset C of V is called an $(a,b)$-regular set in Γ if every vertex in C has exactly a neighbors in C and every vertex in $V?C$ has exactly b neighbors in C. In particular, $(0,1)$-regular sets and $(1,1)$-regular sets in Γ are called perfect codes and total perfect codes in Γ, respectively. A subset C of a group G is said to be an $(a,b)$-regular set of G if there exists a Cayley graph of G which admits C as an $(a,b)$-regular set. In this paper we prove that, for any generalized dihedral group G or any group G of order 4p or pq for some primes p and q, if a nontrivial subgroup H of G is a $(0,1)$-regular set of G, then it must also be an $(a,b)$-regular set of G for any $0?a?|H|?1$ and $0?b?|H|$ such that a is even when $|H|$ is odd. A similar result involving $(1,1)$-regular sets of such groups is also obtained in the paper.     

Lifting constructions of strongly regular Cayley graphs

We give two “lifting” constructions of strongly regular Cayley graphs. In the first construction we “lift” a cyclotomic strongly regular graph by using a subdifference set of the Singer difference sets. The second construction uses quadratic forms over finite fields and it is a common generalization of the construction of the affine polar graphs [7] and a construction of strongly regular Cayley graphs given in [15]. The two constructions are related in the following way: the second construction can be viewed as a recursive construction, and the strongly regular Cayley graphs obtained from the first construction can serve as starters for the second construction. We also obtain association schemes from the second construction.     

A family of skew Hadamard difference sets

In 1933 a family of skew Hadamard difference sets was described by Paley using matrix language and was called the Paley-Hadamard difference sets in the literature. During the last 70 years, no new skew Hadamard difference sets were found. It was conjectured that there are no further examples of skew Hadamard difference sets. This conjecture was proved to be true for the cyclic case in 1954, and further progress in favor of this conjecture was made in the past 50 years. However, the conjecture remains open until today. In this paper, we present a family of new perfect nonlinear (also called planar) functions, and construct a family of skew Hadamard difference sets using these perfect nonlinear functions. We show that some of the skew Hadamard difference sets presented in this paper are inequivalent to the Paley-Hadamard difference sets. These new examples of skew Hadamard difference sets discovered 70 years after the Paley construction disprove the longstanding conjecture on skew Hadamard difference sets. The class of new perfect nonlinear functions has applications in cryptography, coding theory, and combinatorics.     

Special subsets of difference sets with particular emphasis on skew Hadamard difference sets

This article introduces a new approach to studying difference sets via their additive properties. We introduce the concept of special subsets, which are interesting combinatorial objects in their own right, but also provide a mechanism for measuring additive regularity. Skew Hadamard difference sets are given special attention, and the structure of their special subsets leads to several results on multipliers, including a categorisation of the full multiplier group of an abelian skew Hadamard difference set. We also count the number of ways to write elements as a product of any number of elements of a skew Hadamard difference set.      

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.     

Relative difference sets fixed by inversion and Cayley graphs

Using graph theoretical technique, we present a construction of a (30,2,29,14)-relative difference set fixed by inversion in the smallest finite simple group—the alternating group A₅. To our knowledge this is the first example known of relative difference sets in the finite simple groups with a non-trivial forbidden subgroup. A connection is then established between some relative difference sets fixed by inversion and certain antipodal distance-regular Cayley graphs. With the connection, several families of antipodal distance-regular Cayley graphs which are coverings of complete graphs are presented.     

A characterization of two classes of strongly regular graphs

The half dual polar graphsD _4,4(q) and the alternating forms graphsAlt(4,q) are characterized among strongly regular graphs with classical parameters via the geometric structures of polar spaces and affine polar spaces of rank 4, respectively.