Atlantic Graph Theory Seminar

Time: 3:30 pm, Atlantic time, (2:30 pm EST) Wednesday, Mar. 12

Speaker: Ron Gould, Emory University

Title: Looking for Saturation in all Kinds of Places

Abstract:

Given a graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph, but the addition of any missing edge to $G$ results in a graph containing $H$ as a subgraph. An $H$-saturated graph with the maximum number of edges is called an extremal graph for $H$ and for a given order $n$ we denoted this as $\ext(n, H).$   This is the well-known extremal number (or Turan number) of $H$ and is a well studied notion with a deep and beautiful history.

However, the focus of this talk will be the many other saturation questions that can be asked.   These include what is the minimum number of edges in an $H$-saturated graph?  What sizes (i.e. $|E(G)|$), other than the minimum or maximum, also allow $H$-saturated graphs on $n$ vertices?   Is it possible to order the inclusion of the missing edges so that at each stage more copies of $H$ will be included? What about saturation in other settings such as in hypergraphs, edge-colored graphs, random graphs, or within graphs other than the complete graph?

Keywords: saturation, saturation spectrum, weak saturation

Zoom link: