Some Results on Structure in Graphs and Numbers

This thesis present three results. The first is a result in structural graph theory. It demonstrates a large family of complete graphs embedded (clique embeddings) as minors of the grid-like Chimera graph, which is an abstract graph representing the D-Wave quantum adiabatic processor where vertices of the Chimera graph represent qubits in the processor. These particular embeddings are uniform in the sense that each vertex of the complete graph is represented by an equal number of vertices in the Chimera graph, which is thought to improve performance of the D-Wave processor. We present a polynomial-time algorithm to find a largest clique in this family in arbitrary induced subgraphs. Then we use the output of our algorithm as a measure of quality of a particular induced subgraph and show that the size of a largest clique embedding grows logarithmically in the grid size when a fixed percentage of qubits have been deleted. The second is a result in design theory and combinatorial number theory; constructing a family of designs called Heffter arrays. A Heffter array is a (m x n) integer matrix whose entries' absolute values cover the interval [1,mn], where every row and column sums to zero modulo 2mn+1. Archdeacon uses Heffter arrays to construct embeddings of the complete graph K_{2mn+1} into orientable surfaces such that every edge appears in an m-cycle and an n-cycle, provided either m or n is odd. This chapter establishes that m \times n Heffter arrays exist if and only m>2 and n>2. The third is a result in combinatorial number theory and structural graph theory. For subsets A,B of a group G define the product set AB = {ab : a in A, b in B}. Presented in this chapter is a classification the sets A,B such that |AB|