Saturation numbers for Families of Ramsey-Minimal Graphs
Michael Ferrara, University of Colorado, Denver
Meeting Time: February 8, 2011, 2:00-2:50pm
Abstract:
Let \({\mathcal F}\) be a family of graphs. A graph \(G\) is \({\mathcal F}\)-saturated if \(G\) contains
no member of \({\mathcal F}\) as a subgraph, but for any pair of nonadjacent vertices
\(u\) and \(v\) in \(G\), \(G + uv\) contains some member of \({\mathcal F}\). The classical
Turán problem is concerned with determining \(ex({\mathcal F}; n)\), the maximum
number of edges in an \({\mathcal F}\)-saturated graph. Here we are concerned with
determining \(sat({\mathcal F}; n)\), the minimum number of edges in an \({\mathcal F}\)-saturated
graph.
We say that \(G\) is Ramsey-minimal with respect to \(H_1\) and \(H_2\) if
every red-blue coloring of the edges of \(G\) contains either a red copy of
\(H_1\) or a blue copy of \(H_2\), but no proper subgraph of \(G\) has this property.
The majority of the talk will be devoted to the problem of determining
the minimum number of edges in an \(R_{min}(H_1;H_2)\)-saturated graph of
fixed order, where \(R_{min}(H_1;H_2)\) denotes the family of graphs that are
Ramsey-minimal with respect to \(H_1\) and \(H_2\). Most significantly, we
affirm the first nontrivial case of a 1987 conjecture of Hanson and Toft
for complete \(H_1\) and \(H_2\).