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.

A spectral graph realization is an embedding of a finite simple graph into Euclidean space that is constructed from the eigenvalues and eigenvectors of the graph's adjacency matrix. It has previously been observed that some polytopes can be reconstructed from their edge-graphs by taking the convex hull of a spectral realization of this edge-graph. These polytopes, which we shall call spectral polytopes, have remarkable rigidity and symmetry properties and are a source for many open questions. In this thesis we aim to further the understanding of this phenomenon by exploring the geometric and combinatorial properties of spectral polytopes on several levels. One of our central questions is whether already weak forms of symmetry can be a sufficient reason for a polytope to be spectral. To answer this, we derive a geometric criterion for the identification of spectral polytopes and apply it to prove that indeed all polytopes of combined vertex- and edge-transitivity are spectral, admit a unique reconstruction from the edge-graph and realize all the symmetries of this edge-graph. We explore the same questions for graph realizations and find that realizations of combined vertex- and edge-transitivity are not necessarily spectral. Instead we show that we require a stronger form of symmetry, called distance-transitivity. Motivated by these findings we take a closer look at the class of edge-transitive polytopes, for which no classification is known. We state a conjecture for a potential classification and provide complete classifications for several sub-classes, such as distance-transitive polytopes and edge-transitive polytopes that are not vertex-transitive. In particular, we show that the latter class contains only polytopes of dimension d <= 3. As a side result we obtain the complete classification of the vertex-transitive zonotopes and a new characterization for root systems.