Turán Numbers of Vertex-disjoint Cliques in r-Partite Graphs
presentationposted on 19.06.2017, 00:00 by Anna Schenfisch
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 have to give before shaking hands with everyone? What is the best way to drive from city to city? 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 talk 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, GG and HH, the Turán number is denoted eeee(GG,HH), and is the maximum number of edges in a subraph of GG that contains no copy of HH. We were able to find and prove the previously unknown Turán number for a certain pattern in a certain graph. To be precise, we found the Turán number of kk copies of vertex-disjoint cliques in rr-partite graphs (part sizes nn1,…nnrr). That is, ex(Kn1,n2,...,nr, kKr) = ∑ ninj − n1n2 + n2(k−1) where the sum goes from 1≤ i < j≤ r. This talk will describe the motivation and history of extremal graph theory, discuss definitions and concepts related to the research that was done, explain the main concept behind the proof, and finally discuss possible future research.