Extremal problems in codes, finite sets and geometries

Citation

Mazorow, Moya Michelle (1991) Extremal problems in codes, finite sets and geometries. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/s0dw-zr59. https://resolver.caltech.edu/CaltechETD:etd-07182007-091952

Abstract

NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract is included in .pdf document.

This thesis covers some extremal problems in the areas of coding theory, finite set systems, and projective geometry. It was completed under the supervision of Professor R. M. Wilson.

Bounds on the dimension of a binary linear code C are derived when constraints are placed on the weights of words in C. It is known if C is a binary linear code of length a2[superscript alpha] and dimension 2[superscript alpha], then C contains a nonzero word of weight divisible by 2[superscript alpha]. A code of length 18 and dimension 7 is constructed that contains no nonzero word of weight divisible by 6. Let p be an odd prime and [alpha] a positive integer. It is shown that if p[superscript alpha] is large, then a code of length 6p[superscript alpha] that contains no nonzero words of weight divisible by 2p[superscript alpha] has dimension at most [1.95007]2p[superscript alpha]. This is a slight improvement over the known bound. For an infinite family of even b, codes of length 3b containing no nonzero words of weight divisible by b are constructed whose dimensions are approximately [...].

Coloring problems on graphs and hypergraphs are also studied. Let G = K9 be the complete graph on 9 vertices. A coloring C = [...] of the subgraphs K4 is constructed with the property that no edge of G is contained in two K4's of the same color. It is also shown if the edges of Kn are three colored then for large n there are at least 0.4([...]) triangles whose edges are colored differently.

We consider coloring problems in projective geometry similar to the statement above on triangles. If the points of PG(3,q) are partitioned into q + 1 classes, then there are at most q4 + 1 lines tranverse to the partition. Also included is a much easier result that if the points of a projective (n - 1)-space of order q are partitioned into p = [...] classes, then there are at most q[superscript n-1] hyperplanes that are transverse to the partition. In both cases, up to isomorphism, it is shown that there is a unique partition that achieves the upper bound.

Thesis Files