Turán Numbers of Vertex-disjoint Cliques in r-Partite Graphs

In a broad sense, graph theory has always been present in civilization. Graph theory is the math of connections - at a party, who knows each other? How many handshakes will each person in a meeting have to give before shaking hands with everyone? What is the best way to route traffic through a city\u27s network of roads? Extremal graph theory is a branch that deals with counting items (called vertices) and connections between two items (called edges) and determining the maximum/minimum number of characteristics needed to satisfy a certain property. The specific topic of this paper is Turán numbers, a topic of extremal graph theory that attempts to determine the maximum number of edges a graph may have without a specified pattern emerging. For two graphs, G and H, the Turán number is denoted ex(G,H), and is the maximum number of edges in a subgraph of G that contains no copy of H. We were able to find and prove a previously unknown Turán number for a certain pattern in a certain graph. To be precise, we found the Turán number of copies of vertex-disjoint cliques in r-partite graphs (part sizes n1,...,nr). That is, ex(Kn1,n2,...,nr, kKr) = ∑ ninj − n1n2 + n2(k−1) where the sum goes from 1≤ i \u3c j≤ r. This paper will describe the motivation and history of extremal graph theory, discuss definitions and concepts related to the research that was done, go through the proof of our theorem, and finally discuss possible future research as well as general open questions in the field. Note that much of this paper was adapted from a previous paper by the author and other contributors