Extremal Problems for Graph Homomorphisms and Automata

Graph theory first arose in 1736 when Euler developed the basic concepts solving the Bridges of Konigsberg problem. Many modern areas of graph theory are unified in the study of graph homomorphisms; a homomorphism is a function from the vertices of a source graph to the vertices of a target graph such that the images of adjacent vertices being adjacent. Sidorenko\u27s Conjecture, about the minimum number of homomorphisms from a bipartite graph to any graph with a fixed number of vertices and edges, is the core inspiration for our investigation. We expand on the approach of Csikvari and Lin showing several classes of target graphs for which the lower bound of Sidorenko\u27s Conjecture is met for any bipartite source graph. We then turn to the problem of Brown-Kramer et al. who began classifying the `friendly\u27 vertices in graphs, vertices whose images under a random homomorphism have high expected degree. We show that two new classes of vertices are friendly, and that the connected graphs with friendly vertices are trees. We highlight the unexpected relationship between these problems; having a friendly vertex can be seen as satisfying Sidorenko\u27s Conjecture in a local sense. We subsequently turn to a more modern, form of discrete model, cellular automata. Automata were first described by Von Neumann and Ulam and are frequently used as a model of computer computation, particle systems, and cellular biology. As discrete dynamical systems they are known to exhibit complex and even chaotic limit behavior even for certain simple rules of evolution. We first show that an average randomly constructed automaton has exponentially many possible cycles, in contrast to the suggestion of simulation data from Cantor et al. Finally, we look at the evolution of one particular automaton model, bootstrap percolation. Bootstrap percolation is a monotone model of disease spread for which we study the behavior of fast acting, infecting sets of regions in a hexagonal tiling of the plane. We provide exact fastest infection times for certain `nice\u27 regions and develop an understanding of the infection process from minimum size infecting sets