Constructions of External Difference Families and Disjoint Difference Families

External difference families (EDFs) are a type of new combinatorial designs originated from cryptography. In this paper, some earlier ideas of recursive and cyclotomic constructions of combinatorial designs are extended, and a number of classes of EDFs and disjoint difference families are presented. A link between a subclass of EDFs and a special type of (almost) difference sets is set up.     

一类新的部分差集以及分圆数的新性质

本文研究了分圆理论与部分差集,强正则图的关系.利用分圆方法,构造了一类新的部分差集,并反过来得到了分圆数的一些新性质.     

Negative Latin square type partial difference sets in nonabelian groups of order 64

There exist few examples of negative Latin square type partial difference sets (NLST PDSs) in nonabelian groups. We present a list of 176 inequivalent NLST PDSs in 48 nonisomorphic, nonabelian groups of order 64. These NLST PDSs form 8 nonisomorphic strongly regular graphs. These PDSs were constructed using a combination of theoretical techniques and computer search, both of which are described. The search was run exhaustively on 212/267 nonisomorphic groups of order 64.     

Negative Latin square type partial difference sets and amorphic association schemes with Galois rings

A partial difference set (PDS) having parameters (n², r(n?1), n+r²?3r, r²?r) is called a Latin square type PDS, while a PDS having parameters (n², r(n+1), ?n+r²+3r, r² +r) is called a negative Latin square type PDS. There are relatively few known constructions of negative Latin square type PDSs, and nearly all of these are in elementary abelian groups. We show that there are three different groups of order 256 that have all possible negative Latin square type parameters. We then give generalized constructions of negative Latin square type PDSs in 2‐groups. We conclude by discussing how these results fit into the context of amorphic association schemes and by stating some open problems. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 266‐282, 2009     

Cyclotomic constructions of external difference families and disjoint difference families

External difference families (EDFs) are a type of new combinatorial designs originated from cryptography. Some results had been obtained by Chang and Ding, the connection between EDFs and disjoint difference families (DDFs) was also established. In this paper, further cyclotomic constructions of EDFs and DDFs are presented, and several classes of EDFs and DDFs are obtained. Answers to problems 1 and 4 by Chang and Ding are also given. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 333–341, 2009     

New partial geometric difference sets and partial geometric difference families

Using Galois rings and Galois fields, we construct several infinite classes of partial geometric difference sets, and partial geometric difference families, with new parameters. Furthermore, these partial geometric difference sets (and partial geometric difference families) correspond to new infinite families of directed strongly regular graphs. We also discuss some of the links between partially balanced designs, 2-adesigns (which were recently coined by Cunsheng Ding in “Codes from Difference Sets” (2015)), and partial geometric designs, and make an investigation into when a 2-adesign is a partial geometric design.     

Constructions of Nested Partial Difference Sets with Galois Rings

There have been several recent constructions of partial difference sets (PDSs) using the Galois rings for p a prime and t any positive integer. This paper presents constructions of partial difference sets in where p is any prime, and r and t are any positive integers. For the case where 2$$ " align="middle" border="0"> many of the partial difference sets are constructed in groups with parameters distinct from other known constructions, and the PDSs are nested. Another construction of Paley partial difference sets is given for the case when p is odd. The constructions make use of character theory and of the structure of the Galois ring , and in particular, the ring × . The paper concludes with some open related problems.     

New negative Latin square type partial difference sets in nonelementary abelian 2-groups and 3-groups

A partial difference set having parameters (n ², r(n − 1), n + r ² − 3r, r ² − r) is called a Latin square type partial difference set, while a partial difference set having parameters (n ², r(n + 1), − n + r ² + 3r, r ² + r) is called a negative Latin square type partial difference set. Nearly all known constructions of negative Latin square partial difference sets are in elementary abelian groups. In this paper, we develop three product theorems that construct negative Latin square type partial difference sets and Latin square type partial difference sets in direct products of abelian groups G and G′ when these groups have certain Latin square or negative Latin square type partial difference sets. Using these product theorems, we can construct negative Latin square type partial difference sets in groups of the form where the s _i are nonnegative integers and s ₀ + s ₁ ≥ 1. Another significant corollary to these theorems are constructions of two infinite families of negative Latin square type partial difference sets in 3-groups of the form for nonnegative integers s _i . Several constructions of Latin square type PDSs are also given in p-groups for all primes p. We will then briefly indicate how some of these results relate to amorphic association schemes. In particular, we construct amorphic association schemes with 4 classes using negative Latin square type graphs in many nonelementary abelian 2-groups; we also use negative Latin square type graphs whose underlying sets can be elementary abelian 3-groups or nonelementary abelian 3-groups to form 3-class amorphic association schemes.      

Partial Geometric Difference Families

We introduce the notion of a partial geometric difference family as a variation on the classical difference family and a generalization of partial geometric difference sets. We study the relationship between partial geometric difference families and both partial geometric designs and difference families, and show that partial geometric difference families give rise to partial geometric designs. We construct several infinite families of partial geometric difference families using Galois rings and the cyclotomy of Galois fields. From these partial geometric difference families, we generate a list of infinite families of partial geometric designs and directed strongly regular graphs.     

Finite‐time synchronization of a class of N‐coupled complex partial differential systems with time‐varying delay

This study examines finite‐time synchronization for a class of N‐coupled complex partial differential systems (PDSs) with time‐varying delay. The problem of finite‐time synchronization for coupled drive‐response PDSs with time‐varying delay is similarly considered. The synchronization error dynamic of the PDSs is defined in the q‐dimensional spatial domain. We construct a feedback controller to achieve finite‐time synchronization. Sufficient conditions are derived by using the Lyapunov‐Krasoviskii stability approach and inequalities technology to ensure that the proposed networks achieve synchronization in finite time. The proposed systems demonstrate extensive application. Finally, an example is used to verify the theoretical results.     

Partial geometric difference sets and partial geometric difference families

The concept of a partial geometric difference set (or $1\frac{1}{2}$-difference set) was introduced by Olmez in 2014. Recently, Nowak, Olmez and Song introduced the notion of a partial geometric difference family, which generalizes both the classical difference family and the partial geometric difference set. It was shown that partial geometric difference sets and partial difference families give rise to partial geometric designs. In this paper, a number of new infinite families of partial geometric difference sets and partial geometric difference families are constructed. From these partial geometric difference sets and difference families, we generate a list of infinite families of partial geometric designs.     

Disjoint congruence classes and a timetabling application

We consider a combinatorial problem motivated by a special simplified timetabling problem for subway networks. Mathematically the problem is to find (pairwise) disjoint congruence classes modulo certain given integers; each such class corresponds to the arrival times of a subway line of a given frequency. For a large class of instances we characterize when such disjoint congruence classes exist and how they may be determined. We also study a generalization involving a minimum distance requirement between congruence classes, and a comparison of different frequency families in terms of their “efficiency”. Finally, a general method based on integer programming is also discussed.     

两类组合设计及其在认证码中的应用

W．Ogata等定义了两种新的组合设计：外差族（EDF）与外平衡不完全区组设计（E-BIBD）．本文首先用有限域中的分圆类给出EDF的一个构造；接着用EBIBD构造出具有完善保密性的最优分裂A-码，然后证明了由满足一定条件的两个EBIBD通过上述方法构造出的两个认证码是同构的.     

Disjoint paths in symmetric digraphs

Given a number of requests ?, we propose a polynomial-time algorithm for finding ? disjoint paths in a symmetric directed graph. It is known that the problem of finding ?≥2 disjoint paths in a directed graph is NP-hard [S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraph homeomorphism problem, Journal of Theoretical Computer Science 10 (2) (1980) 111-121]. However, by studying minimal solutions it turns out that only a finite number of configurations are possible in a symmetric digraph. We use Robertson and Seymour’s polynomial-time algorithm [N. Robertson, P. D. Seymour, Graph minors xiii. The disjoint paths problem, Journal of Combinatorial Theory B (63) (1995) 65-110] to check the feasibility of each configuration.     

The Existence of （v, 4, 1） Disjoint Difference Families with v a Prime Power

A （v, k, λ） difference family （（v, k, λ）-DF in short） over an abelian group G of order v, is a collection F=（Bi｜i ∈ I} of k-subsets of G, called base blocks, such that any nonzero element of G can be represented in precisely A ways as a difference of two elements lying in some base blocks in F. A （v, k, λ）-DDF is a difference family with disjoint blocks. In this paper, by using Weil＇s theorem on character sum estimates, it is proved that there exists a （p^n, 4, 1）-DDF, where p = 1 （rood 12） is a prime number and n ≥1.     

Constructions of optimal difference systems of sets

Difference systems of sets (DSSs) are combinatorial configurations which were introduced in 1971 by Levenstein for the construction of codes for synchronization. In this paper, we present two kinds of constructions of difference systems of sets by using disjoint difference families and a special type of difference sets, respectively. As a consequence, new infinite classes of optimal DSSs are obtained.     

Existence and non-existence results for strong external difference families

We consider strong external difference families (SEDFs); these are external difference families satisfying additional conditions on the patterns of external differences that occur, and were first defined in the context of classifying optimal strong algebraic manipulation detection codes. We establish new necessary conditions for the existence of $(n,m,k,\lambda )$-SEDFs; in particular giving a near-complete treatment of the $\lambda =2$ case. For the case $m=2$, we obtain a structural characterization for partition type SEDFs (of maximum possible $k$ and $\lambda$), showing that these correspond to Paley partial difference sets. We also prove a version of our main result for generalized SEDFs, establishing non-trivial necessary conditions for their existence.     

Partial Difference Triples

It is known that a strongly regular semi-Cayley graph (with respect to a group G) corresponds to a triple of subsets (C, D, D) of G. Such a triple (C, D, D) is called a partial difference triple. First, we study the case when D D is contained in a proper normal subgroup of G. We basically determine all possible partial difference triples in this case. In fact, when nor 25, all partial difference triples come from a certain family of partial difference triples. Second, we investigate partial difference triples over cyclic group. We find a few nontrivial examples of strongly regular semi-Cayley graphs when |G| is even. This gives a negative answer to a problem raised by de Resmini and Jungnickel. Furthermore, we determine all possible parameters when G is cyclic. Last, as an application of the theory of partial difference triples, we prove some results concerned with strongly regular Cayley graphs.     

Plateaued functions,partial geometric difference sets,and partial geometric designs

Plateaued functions on finite fields have been studied in many papers in recent years. As a generalization of plateaued functions on finite fields, we introduce the notion of a plateaued function on a finite abelian group. We will give a characterization of a plateaued function in terms of an equation of the matrix associated to the function. Then we establish a one‐to‐one correspondence between the ${\mathbb{Z}}_2$‐valued plateaued functions and partial geometric difference sets (with specific parameters) in finite abelian groups. We will also discuss two general methods (extension and lifting) for the construction of new partial geometric difference sets from old ones in (abelian or nonabelian) finite groups, and construct many partial geometric difference sets and plateaued functions. A one‐to‐one correspondence between partial geometric difference sets (in arbitrary finite groups) and partial geometric designs will be proved.     

Existence of (q,k, 1) difference families with q a prime power and k = 4, 5

The existence of a (q, k, 1) difference family in GF(q) has been completely solved for k = 3. For k = 4, 5 partial results have been given by Bose, Wilson, and Buratti. In this article, we continue the investigation and show that the necessary condition for the existence of a (q, k, 1) difference family in GF(q), i.e., q ≡ 1 (mod k(k − 1)) is also sufficient for k = 4, 5. For general k, Wilson's bound shows that a (q, k, 1) difference family in GF(q) exists whenever q ≡ 1 (mod k(k − 1)) and q > [k(k − 1)/2]^k(k−1). An improved bound on q is also presented. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 21–30, 1999