This chapter focuses on studies of problem structures in competitive coevolution and how they affect coevolutionary search processes. We first give a brief introduction on the general literature studies of coevolutionary problem structures and search to provide context and setting that motivates the methodology we will present in subsequent sections. In particular, we will introduce the abstract coevolution as a specific family of random walks (finite state Markov chains) on coevolutionary digraphs. We will develop key theoretical results on these population-one coevolutionary search processes that provide crucial qualitative insights what makes coevolutionary problems difficult for search. We will apply our theory of Markov chains on coevolution to develop quantitative tools for analysis that one can use to characterize the speed of coevolutionary search for a given problem (cycle) complexity. The next section continues on with a further theoretical study we have made to establish a deep connection between PageRank and abstract coevolution. We will formally establish that PageRank authorities can be used to indicate the importance (performance) of vertices in coevolutionary digraphs. Furthermore, they have a natural and second interpretation as visitation probabilities of coevolutionary search on digraphs with restart. The last section will close with a brief remark about the diverse nature of theoretical tools that have been used to better understand coevolutionary systems and the links between them.