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 contains contributions in two different but closely related subfields of Scientific and Parallel Computing which arise in the context of various eigenvalue problems: periodic and parallel eigenvalue reordering and parallel algorithms for Sylvestertype matrix equations with applications in condition estimation. Many real world phenomena behave periodically, e.g., helicopter rotors, revolving satellites and dynamic systems corresponding to natural processes, like the water flow in a system of connected lakes, and can be described in terms of periodic eigenvalue problems. Typically, eigenvalues and invariant subspaces (or, specifically, eigenvectors) to certain periodic matrix products are of interest and have direct physical interpretations. The eigenvalues of a matrix product can be computed without forming the product explicitly via variants of the periodic Schur decomposition. In the first part of the Thesis, we propose direct methods for eigenvalue reordering in the periodic standard and generalized real Schur forms which extend earlier work on the standard and generalized eigenvalue problems. The core step of the methods consists of solving periodic Sylvester-type equations to high accuracy. Periodic eigenvalue reordering is vital in the computation of periodic eigenspaces corresponding to specified spectra. The proposed direct reordering methods rely on orthogonal transformations and can be generalized to more general periodic matrix products where the factors have varying dimensions and ±1 exponents of arbitrary order. In the second part, we consider Sylvester-type matrix equations, like the continuoustime Sylvester equation AX −XB =C, where A of size m×m, B of size n×n, and C of size m×n are general matrices with real entries, which have applications in many areas. Examples include eigenvalue problems and condition estimation, and several problems in control system design and analysis. The parallel algorithms presented are based on the well-known Bartels–Stewart’s method and extend earlier work on triangular Sylvester-type matrix equations resulting in a novel software library SCASY. The parallel library provides robust and scalable software for solving 44 sign and transpose variants of eight common Sylvester-type matrix equations. SCASY also includes a parallel condition estimator associated with each matrix equation. In the last part of the Thesis, we propose parallel variants of the direct eigenvalue reordering method for the standard and generalized real Schur forms. Together with the existing and future parallel implementations of the non-symmetric QR/QZ algorithms and the parallel Sylvester solvers presented in the Thesis, the developed software can be used for parallel computation of invariant and deflating subspaces corresponding to specified spectra and associated reciprocal condition number estimates.