Extremal Problems for Graphs and Hypergraphs

Published in University of Illinois at Chicago, 2021

Recommended citation: Mukherjee, Sayan. "Extremal Problems for Graphs and Hypergraphs." Thesis,Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago (2021).

Given a fixed graph $G$ and a positive integer $n$, the extremal number [Turan, 1941] denotes the maximum number of edges a graph on $n$ vertices can have without copies of $G$. Determining the extremal number for arbitrary graphs, or even its asymptotic behavior, is a tremendously difficult problem. The work of several researchers on this problem led to the birth of the field of extremal combinatorics. In this work, we study three different extensions of the extremal number: (a) A general study of the Erdos-Komlos function, (b) The generalized Turan problem of counting triangles, and (c) The extremal number of $3$-graphs.

Download paper here

DOI: 10.25417/UIC.17026274.V1