Thesis (Ph. D.)--Colorado State University, 2004. / Includes bibliographical references.

The combinatorial objects known as association schemes arise in group theory, extremal graph theory, coding theory, the design of experiments, and even quantum information theory. One may think of a d-class association scheme as a (d + 1)-dimensional matrix algebra over R closed under entrywise products. In this context, an imprimitive scheme is one which admits a subalgebra of block matrices, also closed under the entrywise product. Such systems of imprimitivity provide us with quotient schemes, smaller association schemes which are often easier to understand, providing useful information about the structure of the larger scheme. One important property of any association scheme is that we may find a basis of d + 1 idempotent matrices for our algebra. A cometric scheme is one whose idempotent basis may be ordered E0, E1, . . . , Ed so that there exists polynomials f0, f1, . . . , fd with fi ◦ (E1) = Ei and deg(fi) = i for each i. Imprimitive cometric schemes relate closely to t-distance sets, sets of unit vectors with only t distinct angles, such as equiangular lines and mutually unbiased bases. Throughout this thesis we are primarily interested in three distinct goals: building new examples of cometric association schemes, drawing connections between cometric association schemes and other objects either combinatorial or geometric, and finding new realizability conditions on feasible parameter sets — using these conditions to rule out open parameter sets when possible. After introducing association schemes with relevant terminology and definitions, this thesis focuses on a few recent results regarding cometric schemes with small d. We begin by examining the matrix algebra of any such scheme, first looking for low rank positive semidefinite matrices with few distinct entries and later establishing new conditions on realizable parameter sets. We then focus on certain imprimitive examples of both 3- and 4-class cometric association schemes, generating new examples of the former while building realizability conditions for both. In each case, we examine the related t-distance sets, giving conditions which work towards equivalence; in the case of 3-class Q-antipodal schemes, an equivalence is established. We conclude by partially extending a result of Brouwer and Koolen concerning the connectivity of graphs arising from metric association schemes.

In recent years quantum algorithms have become a popular area of mathematical research. Farhi and Gutmann introduced the concept of a quantum walk in 1998. In this thesis we investigate mixing properties of continuous-time quantum walks from a mathematical perspective. We focus on the connections between mixing properties and association schemes. There are three main goals of this thesis. Our primary goal is to develop the algebraic groundwork necessary to systematically study mixing properties of continuous-time quantum walks on regular graphs. Using these tools we achieve two additional goals: we construct new families of graphs that admit uniform mixing, and we prove that other families of graphs never admit uniform mixing. We begin by introducing association schemes and continuous-time quantum walks. Within this framework we develop specific algebraic machinery to tackle the uniform mixing problem. Our main algebraic result shows that if a graph has an irrational eigenvalue, then its transition matrix has at least one transcendental coordinate at all nonzero times. Next we study algebraic varieties related to uniform mixing to determine information about the coordinates of the corresponding transition matrices. Combining this with our main algebraic result we prove that uniform mixing does not occur on even cycles or prime cycles. However, we show that the probability distribution of a quantum walk on a prime cycle gets arbitrarily close to uniform. Finally we consider uniform mixing on Cayley graphs of elementary abelian groups. We utilize graph quotients to connect the mixing properties of these graphs to Hamming graphs. This enables us to find new results about uniform mixing on Cayley graphs of certain elementary abelian groups.

In recent years quantum algorithms have become a popular area of mathematical research. Farhi and Gutmann introduced the concept of a quantum walk in 1998. In this thesis we investigate mixing properties of continuous-time quantum walks from a mathematical perspective. We focus on the connections between mixing properties and association schemes. There are three main goals of this thesis. Our primary goal is to develop the algebraic groundwork necessary to systematically study mixing properties of continuous-time quantum walks on regular graphs. Using these tools we achieve two additional goals: we construct new families of graphs that admit uniform mixing, and we prove that other families of graphs never admit uniform mixing. We begin by introducing association schemes and continuous-time quantum walks. Within this framework we develop specific algebraic machinery to tackle the uniform mixing problem. Our main algebraic result shows that if a graph has an irrational eigenvalue, then its transition matrix has at least one transcendental coordinate at all nonzero times. Next we study algebraic varieties related to uniform mixing to determine information about the coordinates of the corresponding transition matrices. Combining this with our main algebraic result we prove that uniform mixing does not occur on even cycles or prime cycles. However, we show that the probability distribution of a quantum walk on a prime cycle gets arbitrarily close to uniform. Finally we consider uniform mixing on Cayley graphs of elementary abelian groups. We utilize graph quotients to connect the mixing properties of these graphs to Hamming graphs. This enables us to find new results about uniform mixing on Cayley graphs of certain elementary abelian groups.

No description available.

This thesis presents an introduction to Schur rings (S-rings) and their various properties. Special attention is given to S-rings that are commutative. A number of original results are proved, including a complete classification of the central S-rings over the simple groups PSL(2,q), where q is any prime power. A discussion is made of the counting of symmetric S-rings over cyclic groups of prime power order. An appendix is included that gives all S-rings over the symmetric group over 4 elements with basic structural properties, along with code that can be used, for groups of comparatively small order, to enumerate all S-rings and compute character tables for those S-rings that are commutative. The appendix also includes code optimized for the enumeration of S-rings over cyclic groups.

The problems we study in this thesis arise in computer science, extremal set theory and quantum computing. The first common feature of these problems is that each can be reduced to characterizing the independent sets of maximum size in a suitable graph. A second common feature is that the size of these independent sets meets an eigenvalue bound due to Delsarte and Hoffman. Thirdly, the graphs that arise belong to association schemes that have already been studied in other contexts. Our first problem involves covering arrays on graphs, which arises in computer science. The goal is to find a smallest covering array on a given graph <i>G</i>. It is known that this is equivalent to determining whether <i>G</i> has a homomorphism into a <i>covering array graph</i>, <i>CAG(n,g)</i>. Thus our question: Are covering array graphs cores? A covering array graph has as vertex set the partitions of <i>{1,. . . ,n}</i> into <i>g</i> cells each of size at least <i>g</i>, with two vertices being adjacent if their meet has size <i>g²</i>. We determine that <i>CAG(9,3)</i> is a core. We also determine some partial results on the family of graphs <i>CAG(g²,g)</i>. The key to our method is characterizing the independent sets that meet the Delsarte-Hoffman bound---we call these sets <i>ratio-tight</i>. It turns out that <i>CAG(9,3)</i> sits inside an association scheme, which will be useful but apparently not essential. We then turn our attention to our next problem: the Erdos-Ko-Rado theorem and its <i>q</i>-analogue. We are motivated by a desire to find a unifying proof that will cover both versions. The EKR theorem gives the maximum number of pairwise disjoint <i>k</i>-sets of a fixed <i>v</i>-set, and characterizes the extremal cases. Its <i>q</i>-analogue does the same for <i>k</i>-dimensional subspaces of a fixed <i>v</i>-dimensional space over <i>GF(q)</i>. We find that the methods we developed for covering array graphs apply to the EKR theorem. Moreover, unlike most other proofs of EKR, our argument applies equally well to the <i>q</i>-analogue. We provide a proof of the characterization of the extremal cases for the <i>q</i>-analogue when <i>v=2k</i>; no such proof has appeared before. Again, the graphs we consider sit inside of well-known association schemes; this time the schemes play a more central role. Finally, we deal with the problem in quantum computing. There are tasks that can be performed using quantum entanglement yet apparently are beyond the reach of methods using classical physics only. One particular task can be solved classically if and only if the graph &Omega;(<i>n</i>) has chromatic number <i>n</i>. The graph &Omega;(<i>n</i>) has as vertex set the set of all <i>?? 1</i> vectors of length <i>n</i>, with two vertices adjacent if they are orthogonal. We find that <i>n</i> is a trivial upper bound on the chromatic number, and that this bound holds with equality if and only if the Delsarte-Hoffman bound on independent sets does too. We are thus led to characterize the ratio-tight independent sets. We are then able to leverage our result using a recursive argument to show that <i>&chi;</i>(&Omega;(<i>n</i>)) > <i>n</i> for all <i>n</i> > 8. It is notable that the reduction to independent sets, the characterization of ratio-tight sets, and the recursive argument all follow from different proofs of the Delsarte-Hoffman bound. Furthermore, &Omega;(<i>n</i>) also sits inside a well-known association scheme, which again plays a central role in our approach.

The problems we study in this thesis arise in computer science, extremal set theory and quantum computing. The first common feature of these problems is that each can be reduced to characterizing the independent sets of maximum size in a suitable graph. A second common feature is that the size of these independent sets meets an eigenvalue bound due to Delsarte and Hoffman. Thirdly, the graphs that arise belong to association schemes that have already been studied in other contexts. Our first problem involves covering arrays on graphs, which arises in computer science. The goal is to find a smallest covering array on a given graph <i>G</i>. It is known that this is equivalent to determining whether <i>G</i> has a homomorphism into a <i>covering array graph</i>, <i>CAG(n,g)</i>. Thus our question: Are covering array graphs cores? A covering array graph has as vertex set the partitions of <i>{1,. . . ,n}</i> into <i>g</i> cells each of size at least <i>g</i>, with two vertices being adjacent if their meet has size <i>g²</i>. We determine that <i>CAG(9,3)</i> is a core. We also determine some partial results on the family of graphs <i>CAG(g²,g)</i>. The key to our method is characterizing the independent sets that meet the Delsarte-Hoffman bound---we call these sets <i>ratio-tight</i>. It turns out that <i>CAG(9,3)</i> sits inside an association scheme, which will be useful but apparently not essential. We then turn our attention to our next problem: the Erdos-Ko-Rado theorem and its <i>q</i>-analogue. We are motivated by a desire to find a unifying proof that will cover both versions. The EKR theorem gives the maximum number of pairwise disjoint <i>k</i>-sets of a fixed <i>v</i>-set, and characterizes the extremal cases. Its <i>q</i>-analogue does the same for <i>k</i>-dimensional subspaces of a fixed <i>v</i>-dimensional space over <i>GF(q)</i>. We find that the methods we developed for covering array graphs apply to the EKR theorem. Moreover, unlike most other proofs of EKR, our argument applies equally well to the <i>q</i>-analogue. We provide a proof of the characterization of the extremal cases for the <i>q</i>-analogue when <i>v=2k</i>; no such proof has appeared before. Again, the graphs we consider sit inside of well-known association schemes; this time the schemes play a more central role. Finally, we deal with the problem in quantum computing. There are tasks that can be performed using quantum entanglement yet apparently are beyond the reach of methods using classical physics only. One particular task can be solved classically if and only if the graph &Omega;(<i>n</i>) has chromatic number <i>n</i>. The graph &Omega;(<i>n</i>) has as vertex set the set of all <i>± 1</i> vectors of length <i>n</i>, with two vertices adjacent if they are orthogonal. We find that <i>n</i> is a trivial upper bound on the chromatic number, and that this bound holds with equality if and only if the Delsarte-Hoffman bound on independent sets does too. We are thus led to characterize the ratio-tight independent sets. We are then able to leverage our result using a recursive argument to show that <i>&chi;</i>(&Omega;(<i>n</i>)) > <i>n</i> for all <i>n</i> > 8. It is notable that the reduction to independent sets, the characterization of ratio-tight sets, and the recursive argument all follow from different proofs of the Delsarte-Hoffman bound. Furthermore, &Omega;(<i>n</i>) also sits inside a well-known association scheme, which again plays a central role in our approach.

This thesis considers spectral approaches to finding maximum cocliques in graphs. We focus on the relation between the eigenspaces of a graph and the size and location of its maximum cocliques. Our main result concerns the computational problem of finding the size of a maximum coclique in a graph. This problem is known to be NP-Hard for general graphs. Recently, Codenotti et al. showed that computing the size of a maximum coclique is still NP-Hard if we restrict to the class of circulant graphs. We take an alternative approach to this result using quotient graphs and coding theory. We apply our method to show that computing the size of a maximum coclique is NP-Hard for the class of Cayley graphs for the groups $\mathbb{Z}_p^n$ where $p$ is any fixed prime. Cocliques are closely related to equitable partitions of a graph, and to parallel faces of the eigenpolytopes of a graph. We develop this connection and give a relation between the existence of quadratic polynomials that vanish on the vertices of an eigenpolytope of a graph, and the existence of elements in the null space of the Veronese matrix. This gives a us a tool for finding equitable partitions of a graph, and proving the non-existence of equitable partitions. For distance-regular graphs we exploit the algebraic structure of association schemes to derive an explicit formula for the rank of the Veronese matrix. We apply this machinery to show that there are strongly regular graphs whose $\tau$-eigenpolytopes are not prismoids. We also present several partial results on cocliques and graph spectra. We develop a linear programming approach to the problem of finding weightings of the adjacency matrix of a graph that meets the inertia bound with equality, and apply our technique to various families of Cayley graphs. Towards characterizing the maximum cocliques of the folded-cube graphs, we find a class of large facets of the least eigenpolytope of a folded cube, and show how they correspond to the structure of the graph. Finally, we consider equitable partitions with additional structural constraints, namely that both parts are convex subgraphs. We show that Latin square graphs cannot be partitioned into a coclique and a convex subgraph.