Relative T-designs In Some Association Schemes

Algebraic combinatorics,an important branch of combinatorics,mainly involves the study of objects with highly symmetric property and algebraic structure including strongly regular graphs,association schemes and finite sets such as codes and designs.Codes and designs have not only deep relationships with many areas such as representation theory of finite groups and finite geometries,but also applications to network theory and cryptography.Association schemes,a combinatorial generalization of finite transitive permutation groups,provide a unified approach to coding theory and design theory.The purpose of design theory is to find a finite subset?with nice properties?which approximates the whole space.In this paper,we mainly study relative t-designs in binary Hamming association scheme H?n,2?and Johnson association scheme J?v,k?from the viewpoint of Delsarte theory.Relative t-designs in H?n,2?are a generalization of?combinatorial?t-designs?i.e.,t-designs in J?v,k??.Shifting from t-designs to relative t-designs enables us to handle much wider variety of combinatorial struc-tures,and thus the outcome of this research will naturally have many applications.There is a close analogy between“relative t-designs in H?n,2?vs.combinatorial t-designs”and“Euclidean t-designs vs.spherical t-designs”.The methods used in the study of these two classes of designs are in some sense very similar.Therefore the present work will lead us to dig into more analogy between them.Chapter 1 briefly gives the background of design theory and the research status of spherical t-designs and combinatorial t-designs as well as their generalizations.Chapter 2 is an introduction to association schemes and Bose-Mesner algebra.Delsarte defined the regular semi-lattice,i.e.,poset with certain conditions,and pointed out the internal connection with association schemes.This observation provides an important method for the design theory in association schemes.In Chapter 3,we introduce the concepts of t-designs and relative t-designs in P-and/or Q-polynomial association schemes,and present several equivalent definitions from different perspectives.We mainly discuss the Fisher type lower bound for relative 2e-designs in P-and/or Q-polynomial association schemes and give an overview of results on tight designs.Motivated by the research of tight relative 2-designs in H?n,2?and the close relation between H?n,2?and J?v,k?,we investigate the existence problem of tight relative 2-designs on two shells in J?v,k?for the Q-structure in Chapter 4.Firstly,we obtain the feasible parameters of tight relative 2-designs for v?100.Moreover,we discuss the existence or non-existence for each case.Finally,the existence of certain tight relative 2-designs on two shells is equivalent to finding a k-element subset u₀/?B satisfying some additional conditions related to a given symmetric 2-?v,k,??design?V,B?.If v is small,then we can easily check whether such k-element subset exists or not.We construct some new tight relative 2-designs on two shells with constant weight in J?v,k?coming from some strongly regular graphs or difference sets.All known tight relative 2-designs on two shells have the structure of a coherent configuration.A relative t-design in H?n,2?is equivalent to a weighted regular t-wise balanced design.In Chapter5,we study relative t-designs in H?n,2?,putting emphasis on Fisher type inequalities and the existence of tight relative t-designs.In general,for an odd integer t,we do not have a natural lower bound for relative t-designs.However,there is a good feature for H?n,q?that relative t-designs for P-structure are equivalent to that for Q-structure,although this is not true for a general P-and Q-polynomial association scheme.Using this property,we prove that if Y is a relative t-design on p shells,then its subset in each shell must be a weighted combinatorial?t+1-p?-design.Therefore we obtain the Fisher type lower bound for relative?2e+1?-designs on two shells,moreover,we can define tight relative?2e+1?-designs using the tightness of combinatorial 2e-designs.Finally,we obtain a new family of such tight relative t-designs with t=3,4,5,which are unnoticed before.