Discrete Applied Mathematics Seminar by Minjung Michelle Kang: The Saturation Spectrum of Odd Cycles

Speaker: Minjung Michelle Kang, Ph.D. candidate, Illinois Institute of Technology

Title: The Saturation Spectrum of Odd Cycles

Abstract: Given a cycle ${}_k$ on $k$ vertices, we say that a graph $G$ is $C_k$-saturated if it does not contain a $C_k$-subgraph, but the addition of any new edges to $G$ creates at least one copy of $C_k$. For $k=3$, this is a classical problem in extremal graph theory, i.e., how big/small can a triangle-free graph be? Mantel, in 1907, determined the maximum value, and later, the general construction was given by T{u}'ran. The questions for $k=3$ and $k=4$ are completely answered, and the next interesting question is for $k\ge 5$. In this talk, we will characterize all pairs $(n,m)$ for which there is a $C_5$-saturated graph on $n$ vertices and $m$ edges and provide some general results about the size of $C_k$-saturated graphs when $k$ is odd. This is joint work with R. Gould and A. Kundgen.

 

Discrete Applied Math Seminar

Request Zoom Link