Research On Existence And Applications Of Certain Discrete Structures

Combinatorial design Theory mainly studies the existence and constructions of a variety of discrete structures, whose basic content, ideas and methods intersect with algebra, number theory, graph theory, and finite geometry. Applied subjects such as computer science, information science, statistics, biology information science have a large number of discrete structural problems, which promote the development of combinatorial design theory. This thesis studies the existence and applications of some discrete structures, such as mixed orthogonal arrays, Frame-GBTDs, strong separable codes, which are closely related to statistics and information science.As a generalization of orthogonal arrays, mixed orthogonal arrays (MOA) play an important role in the design of experiment. In Hedayat et al’s monograph enti-tled with "Orthogonal Arrays Theoery and Applications", they gave a construction named "expansion alternative method" for mixed orthogonal arrays of strength 2, in the meanwhile, posed a question whether this method still works for strength t≥3. In the second chapter, we solve the problem, and describe a new "expansion replace-ment method " for general strength t. As its application, we obtain some new series of MOAs.In the third chapter, we study the asymptotic existence of a frame-generalized balanced tournament designs (Frame-GBTDs). Frame-GBTDs are widely studied because they can be used to construct equitable symbol weight codes and constant composition codes. Due to the complexity of Frame-GBTD’s structure, the existence results are rarely known. We use a powerful theorem by Lamken and Wilson on decom-positions of edge-colored complete digraphs into prescribed edge-colored subgraphs. By converting the existence of the Frame-GBTD to some appropriate problem of graph theory, we establish an asymptotic existence theorem of FGBTD(k gn).In the fourth chapter, we study orthogonal arrays which have the "simple" prop-erty(SOA). Using the combinatorial constructions, we prove that the necessary condi-tions for SOAλ(3,5,v) with λ≥2 are also sufficient with definite exceptions:v=6 and λ=3; v=3 and λ=8; v=6 and λ=35, and some possible exceptions:v=6 and λ∈{7,11,13,15,17,19,21,23,25,29,33}.In multimedia era, copyright protection is particularly important. Multimedia fingerprinting is an effective technique to protect the copyright of multimedia contents. As anti-collusion codes, frameproof codes have better traceablity than separable codes, but have fewer codewords (corresponding to the number of users) than separable codes. Very recently, strongly separable codes, which have the same traceability as frameproof codes, have been introduced By Jiang et al. In the fifth chapter, we use a probabilistic approach, which was developed by P. Erdos, N. Alon et al., to give a lower bound on the maximum number of codewords in a strongly separable code and to show that strongly separable codes asymptotically have the same number of codewords as separable codes. This shows that strongly separable codes surpass frameproof codes and separable codes, since they have strong traceability and many codewords.