A Survey of Minimum Saturated Graphs

Jill R. Faudree

Department of Mathematics and Statistics

University of Alaska at Fairbanks Fairbanks, AK 99775-6660

      jfaudree@alaska.edu

Ralph J. Faudree

Department of Mathematical Sciences University of Memphis Memphis, TN 38152

                                             rfaudree@memphis.edu

John R. Schmitt ^{∗}

Department of Mathematics Middlebury College Middlebury, VT 05753

                       jschmitt@middlebury.edu

Submitted: May 24, 2010; Accepted: Jul 21, 2011; Published: Jul 29, 2011 Mathematics Subject Classification: 05C35

Abstract

Given a family of (hyper)graphs F a (hyper)graph G is said to be F-saturated if G is F -free for any F ∈ F but for any edge e in the complement of G the (hyper)graph G + e contains some F ∈ F. We survey the problem of determining the minimum size of an F-saturated (hyper)graph and collect many open problems and conjectures.

1 Introduction

In this paper we will deal only with finite graphs without loops or multiple edges. Notation will be standard, and we will generally follow the notation of Chartrand and Lesniak in [CL05]. We let K_{p} denote the complete graph on p vertices, C_{l} denotes the cycle on l vertices, and P_{k} denotes the path on k vertices. If F′ is a subgraph of F, then we write F′ ⊆ F. If we wish to emphasize that F′ is a proper subgraph of F, then we write F′ ⊂ F. We adopt a similar convention for sets. Given any two graphs G and H, their join, denoted G + H, is the graph with V (G + H) = V (G) ∪ V (H) and E(G + H) = E(G) ∪ E(H) ∪ {gh | g ∈ V (G), h ∈ V (H)}.

∗Corresponding author. Partially supported by an ROA Supplement to National Science Foundation (NSF) grant DMS-0758057 and the National Security Agency, Grant H98230-10-1-0173. The author would also like to thank the Institute for Pure and Applied Mathematics at UCLA for providing a stimulating environment in which part of this document was prepared.

the electronic journal of combinatorics 18 (2011), #DS19 1

We will begin with some standard definitions. Given a (hyper)graph F, we say that the (hyper)graph G is F -free if G has no sub(hyper)graph isomorphic to F. We say a (hyper)graph G is F -saturated if G is F -free but G + e does contain a copy of F for every (hyper)edge e ∈ E(\overline{G}) where \overline{G} denotes the complement of G. For example, any complete bipartite graph is a K_{3}-saturated graph. Additionally, we have:

ex(n, F) = max{|E(G)| : |V (G)| = n and G is F -saturated},

Ex(n, F) = {G : |V (G)| = n, |E(G)| = ex(n, F), and G is F -saturated}, sat(n, F) = min{|E(G)| : |V (G)| = n and G is F -saturated}, Sat(n, F) = {G : |V (G)| = n, |E(G)| = sat(n, F), and G is F -saturated}.

Note that the word saturated could be replaced with the word free in the definitions for ex(n, F) and Ex(n, F) but not so in the other two. We will refer to ex(n, F) as the extremal number of F and sat(n, F) as the saturation number.

Additionally, we can generalize all the definitions above by replacing the graph F with a family of (hyper)graphs F. So, a (hyper)graph G is F-saturated if G contains no member of F as a sub(hyper)graph but for every edge e ∈ \overline{G}, there exists F ∈ F such that G + e contains F as a sub(hyper)graph. When F = {F } we write F -saturated, sat(n, F), etc. in place of F-saturated, sat(n, F), etc.

In 1941, P. Turán published a paper [Tur41] in which he introduced the idea of an extremal number and determined ex(n, K_{p}) and Ex(n, K_{p}). In particular, he proved that Ex(n, K_{p}) consists of a single graph (up to isomorphism): the complete (p − 1)-partite graph, where the n vertices are distributed among the partite sets as evenly as possible.

In 1964, motivated by a conjecture of P. Erdős and T. Gallai [EG61], P. Erdős, A. Hajnal, and J.W. Moon in [EHM64] introduced the idea of a saturation number (though not using that terminology) and proved the following.

Theorem 1. [EHM64] If 2 ≤ p ≤ n, then sat(n, K_{p}) = (p − 2)(n − p + 2) + \binom{p−2}{2} = \binom{n}{2} − \binom{n−p+2}{2} and Sat(n, K_{p}) contains only one graph, K_{p−2} + \overline{K}_{n−p+2}.

Note that K_{p−2} + \overline{K}_{n−p+2} can be thought of as the complete (p − 1)-partite graph on n vertices such that all but one of the partite sets contains exactly one vertex, i.e. the vertices are distributed as “unevenly” as possible amongst the p − 1 parts.

In 1986 L. Kászonyi and Zs. Tuza in [KT86] found the best known general upper bound for sat(n, F). Note that α(F) is the independence number of F (i.e. the order of the largest clique in \overline{F}) and a star on n vertices refers to the complete bipartite graph K_{1,n−1}. To state their result, we first define

u = u(F) = min{|V (F)| − α(F) − 1 : F ∈ F}

and

d = d(F) = min{|E(F′)| : F′ ⊆ F ∈ F is induced by S ∪ x},

where S is an independent set in V (F) and |S| = {|V (F)| − u − 1, x ∈ V (F) \ S}.

Theorem 2. [KT86] sat(n, F) ≤ un + (d − 1)(n − u)/2 − \binom{u+1}{2}.

This theorem is interesting for several reasons. First the proof hinges largely on two simple observations and exploits the power of considering the saturation number of families of graphs. Second, the bound is exact for a great many graphs. Finally the proof is implicitly constructive. That is, for many graphs, the proof describes how to construct an F -saturated graph. In fact, for all graphs F, the proof constructs a graph that must contain an F -saturated graph as a subgraph. An outline of the proof and its consequences now follows.

Given a family of graphs F, Kászonyi and Tuza define the family of deleted subgraphs of F as F′ = {F \x | F ∈ F, x ∈ V (F)} and recursively, F′′, F′′′, and so forth. A first observation is that a graph G on n vertices with a vertex x of degree n − 1 is F-saturated if and only if G\x is F′-saturated. Now, by the choice of parameter u in the hypothesis of the theorem, the family F^{u} must contain a star on d+1 vertices from which it immediately follows that any F^{u}-saturated graph has maximum degree less than d. The upper bound, then, is simply a count of the number of edges in a graph on n vertices such that u of the vertices have degree n − 1 and the subgraph containing the remaining n − u vertices is (d−1)-regular. For reference, we will call this graph K_{u} +G′, where G′ is a (d−1)-regular graph on n − u vertices.

R. Faudree and R. Gould observed in [FG] that the bound in [KT86] can be improved slightly by replacing G′ by a graph G^{∗} ∈ sat(n − u, K_{1,d}), since the critical fact is that the addition of any edge in G^{∗} will result in a vertex of degree d. This does not change the bound asymptotically, but gives the inequality

sat(n, F) ≤ un + (d − 1)(n − u)/2 − \binom{u + 1}{2} − \frac{1}{2}⌊d^{2}/4⌋.

This upper bound is sharp in many cases. In particular, in the case that F contains only the complete graph — the construction gives the unique extremal graph in this case (see Theorem 1 of Erdős, Hajnal, and Moon). Furthermore, in [FG], the authors establish the existence of infinite families of graphs such that for every member F, K_{u} + G^{∗} ∈ Sat(n, F). In [CFG08] this upper bound was also shown to give a sharp bound for the saturation numbers for similar graphs, such as books and generalized books. And in [FG] it is shown that the saturation numbers for various families of nearly complete graphs are either precisely the Kászonyi-Tuza bound or the bound is asymptotically correct. The bound is also sharp in the case of the very sparse graph F = {K_{1,k−1} + e} = {K_{1} + (K_{2} ∪ (k − 3)K_{1})}. In this case, u = 1 and d = 1, and the construction given by Theorem 2 gives the star graph K_{1,n−1}. In some cases the bound is known to be asymptotically correct. (See, for example, Theorem 12.)

Finally, for any graph F, the F -saturated subgraph contained in K_{u} + G^{∗} can be constructed by beginning with the graph K_{u} + \overline{K}_{n−u} and adding edges one by one from the graph G^{∗} if and only if their addition does not produce a copy of F. This procedure must end in the desired subgraph.

In many instances the bound in Theorem 2 is neither sharp nor asymptotically correct. (See, for example, Theorem 13 and Theorem 14.)

Note that Theorem 2 implies that sat(n, F) = O(n), while for the extremal number we have ex(n, F) = O(n^{2}) (see [ES66]).

A nontrivial general lower bound has yet to be determined though lower bounds do exist for certain classes of graphs as will be seen later in the survey.

One of the most interesting tools to arise as a result of the study of the saturation function is due to B. Bollobás [Bol65]. We refer to this tool as Bollobás’ inequality. It allows for simple proofs of many results, including the quantitative part of Theorem 1, which we give after the statement. It was developed however to establish a corresponding result for k-uniform hypergraphs (see Theorem 3), but it also easily adapts to allow for proofs for bipartite graphs in a bipartite setting (see Section 7, in particular Theorem 30). Bollobás’ inequality has also found use outside the study of this function; most of these uses lie in Extremal Set Theory where the method of proof is sometimes referred to as the set-pair method. For instances of such see Section 10 of the survey by P. Frankl in [GGL95] and the excellent two-part survey on the set-pair method by Zs. Tuza [Tuz94, Tuz96].

Theorem 3. [Bol65] Let {(A_{i}, B_{i}) : i ∈ I} be a finite collection of finite sets such that A_{i} ∩ B_{j} = ∅ if and only if i = j. For i ∈ I set a_{i} = |A_{i}| and b_{i} = |B_{i}|. Then

∑_{i∈I} \binom{a_{i} + b_{i}}{a_{i}}^{−1} ≤ 1  (1)

with equality if and only if there is a set Y and non-negative integers a and b, such that |Y | = a + b and {(A_{i}, B_{i}) : i ∈ I} is the collection of all ordered pairs of disjoint subsets of Y with |A_{i}| = a and |B_{i}| = b (and so B_{i} = Y \ A_{i}). In particular, if a_{i} = a and b_{i} = b for all i ∈ I, then |I| ≤ \binom{a+b}{a}. If a_{i} = 2 and b_{i} = n − p for all i ∈ I, then |I| ≤ \binom{n−p+2}{2}.

We can now easily give a proof of the quantitative part of Theorem 1.

Proof of Theorem 1 (as given in [GGL95], page 1269) Let G be an n-vertex K_{p}-saturated graph. We show that the number of non-edges l is at most \binom{n−p+2}{2}. Let A_{1}, …, A_{l} be the pairs of vertices “belonging” to a non-edge of G. For each such set there is a corresponding p−set C_{i} of vertices in V (G) containing A_{i} such that V (C_{i}) induces a K_{p} − e. Set B_{i} to be the complement of C_{i} in V (G). Now note that the hypotheses of Theorem 3 are met and so l ≤ \binom{n−p+2}{2}, or rather sat(n, K_{p}) ≥ \binom{n}{2} − \binom{n−p+2}{2}. □

In this paper, we will summarize known results for sat(n, F) and Sat(n, F). Earlier such surveys may be found in [Tuz88], [GGL95] (see the chapter by B. Bollobás), and the Ph.D. thesis of O. Pikhurko [Pik99b]. In an effort to stimulate further research, we include many open conjectures, questions, and problems. We regard these items with respect to importance and/or interest in the same order.

The paper is organized as follows. In Section 2 we consider results pertaining to complete graphs, including degree restrictions, unions of cliques, complete partite graphs, and edge coloring problems. These problems and results are among the first and most natural considerations after the introduction of the function in the early 1960s. Some results are arrived at in a straightforward manner, e.g. unions of cliques, others thwarted attack for a long time and required a novel approach, e.g the results on complete partite graphs. In Section 3 and Section 4 we present results on cycles and trees, respectively. In these sections we begin to get a sense of the challenges of studying this function, whether it be the technical proof involved in determining the value of the function for the five-cycle or the strange behavior of the function exhibited for two trees of a given order with ‘similar’ structure. In Section 5 we grapple with some of the inherent difficulties of the sat-function. One of the main current challenges in the study of the saturation function is that it fails to have the monotonic properties for which one might hope. We discuss these issues in depth and believe that Question 7 is most important to settle. Section 6 considers the problem for hypergraphs and Section 7 considers the problem for when the ‘host’ graph is something other than the complete graph. Section 8 deals with the problem when edges are directed. Section 9 shows some relationships that the sat-function has with other extremal functions, including the ex-function. In particular, it seems that certain aspects of the saturation function are as difficult as some of the most challenging outstanding problems in the whole of extremal graph theory, see Subsection 9.1. Finally in Section 10 we consider the related notion of weak saturation. Though last in our presentation, the topic should not be considered last in terms of interest or challenges present. Indeed, this last topic has attracted the attention of some of the top combinatorists of the past few decades and as a consequence some beautiful results and techniques have been found.

It should be noted that while much of this survey is devoted to compiling known results and open problems, we do give some proofs that we feel are particularly novel, striking or beautiful, one such is given above and another is to follow immediately.

Note that in the proof of Theorem 1 we only made use of the “in particular” statement found in Theorem 3. We give a proof of just this part of the theorem (as found in L. Babai and P. Frankl [BF]) as it brings to light how L. Lovász [Lov77] brought the linear algebra method into play for theorems of this type. Generalizations of Bollobás’ theorem often allow extensions of this method.

Proof of the “In particular” statement of Theorem 3

Let Y = (∪_{I}A_{i})∪(∪_{I}B_{i}). For each y ∈ Y we associate a vector v(y) = (v_{0}(y), v_{1}(y), …, v_{a}(y)) ∈ ℝ^{a+1} such that the set of vectors is in general position; that is, any a + 1 vectors are linearly independent. Now for each set Y′ ⊆ Y we associate a polynomial f_{Y′}(x) in the a + 1 variables x = (x_{0}, x_{1}, …, x_{a}) as follows:

f_{Y′}(x) = ∏_{y∈Y′}(v_{0}(y)x_{0} + v_{1}(y)x_{1} + … + v_{a}(y)x_{a}).

The above polynomial is homogeneous and has degree equal to the size of the set Y′. It follows from the definition of orthogonal that the polynomial is non-zero only when x is orthogonal to none of the v(y), y ∈ Y′.

We now consider such a polynomial associated with a set B_{i} and let a_{j} be a non-zero vector orthogonal to the subspace generated by the a elements of A_{j}. Note that a_{j} is orthogonal to v(y) only if y ∈ A_{j} (this follows from the fact that the vectors were chosen to be in general position). We are now able to claim that f_{B_{i}}(a_{j}) = 0 if and only if A_{j} and B_{i} intersect; that is, if and only if i ≠ j.

It can then be shown that the polynomials f_{B_{1}}, … f_{B_{|I|}} form a linearly independent set. Thus, (by the so-call linear algebra bound) the size of this set is not greater than the dimension of the space of homogeneous polynomials of degree b in a + 1 variables; that is, |I| ≤ \binom{(a+1)+b−1}{b} = \binom{a+b}{a}. □

2 Complete graphs

Recall that in the original paper by Erdős, Hajnal and Moon, their main result was to establish sat(n, K_{p}) and the uniqueness of the graph in Sat(n, K_{p}). This section describes results concerning graphs relatively close to minimum K_{p}-saturated graphs, such as the saturation number of K_{p} with restrictions on the minimum or maximum degree of the host graph or the saturation number of complete bipartite graphs. (One exception is the generalization to hypergraphs which is discussed in Section 6.) The reader will find that even the set of results close to the original [EHM64] result include a great variety of approaches all of which have natural open problems in their respective directions.

2.1 Degree restrictions

One of the first generalizations considered was to place additional restrictions on the graph. Recall that all the vertices in the unique extremal graph in Sat(n, K_{p}) either have degree equal to Δ = n − 1 or δ = p − 2. And, in fact, any K_{p}-saturated graph has to have minimum degree at least p−2. While confirming a conjecture of T. Gallai about the minimum degree of a K_{p}-saturated without conical (degree n − 1) vertices, A. Hajnal in [Haj65] asked, what is the minimum number of edges in a K_{p}-saturated graph if Δ ≤ n−2? With this question in mind, we define sat^{Δ}(n, F) to be the minimum number of edges in a F -saturated graph on n vertices with maximum degree no more than Δ. In Z. Füredi and Á. Seress [FS94], the value of sat^{Δ}(n, K_{3}) was found precisely for Δ ≥ (n − 2)/2 and n sufficiently large.

Theorem 4. [FS94] Let n > 2^{2^{28}}. Then

sat^{Δ}(n, K_{3}) = \begin{cases}2n − 5, & for Δ = n − 2, \\ 2n − 5 + (n − 3 − Δ)^{2}, & for n − 3 − \sqrt{n − 10} ≤ Δ ≤ n − 3, \\ 3n − 15, & for (n − 2)/2 ≤ Δ < n − 3 − \sqrt{n − 10}. \end{cases}

Upper and lower bounds are established for other values of Δ. Continuing in this direction, P. Erdős and R. Holzman [EH94] gave the following result.

Theorem 5. [EH94]

lim_{n→∞} \frac{sat^{cn}(n, K_{3})}{n} = \begin{cases}(11 − 7c)/2, & for 3/7 ≤ c < 1/2, \\ 4 & for 2/5 ≤ c ≤ 3/7. \end{cases}

In a paper of N. Alon, P. Erdős, R. Holzman, and M. Krivelevich [AEHK96] similar results for K_{4} are proved. Additionally, they construct a K_{p}-saturated graph with Δ = 2p\sqrt{n} for all p and sufficiently large n.

Problem 1. Investigate sat^{Δ}(n, K_{p}) for p ≥ 5.

From a slightly different perspective, D. Duffus and D. Hanson [DH86] considered minimally K_{p}-saturated graphs with minimum degree at least δ, for δ ≥ p − 2. Thus, define sat_{δ}(n, F) to be the minimum number of edges in an n-vertex F -saturated graph with minimum degree at least δ. Upper and lower bounds for this function are found in some instances.

Theorem 6. [DH86]

sat_{2}(n, K_{3}) = 2n − 5, n ≥ 5,
sat_{3}(n, K_{3}) = 3n − 15, n ≥ 10.

Note that the upper bound for each of the above statements in Theorem 6 can be realized by duplicating a vertex in the 5-cycle and Petersen graph, respectively. This process of duplicating a vertex occurs frequently, but certainly not always, in the extremal graphs for the sat-function. In addition, Theorem 6 plays a role in the previously mentioned results found in [FS94] and [AEHK96]. Theorem 6 led B. Bollobás [GGL95] (see page 1271) to ask the following.

Question 1. For δ ≥ 4, does sat_{δ}(n, K_{3}) = δn − O(1)?

Certainly we have sat_{δ}(n, K_{3}) ≤ δ(n−δ) as the bipartite graph K_{δ,n−δ} is K_{3}-saturated with minimum degree at least δ. (In [DH86] a different construction is given yielding a slightly better upper bound, and better yet in [FS94].) Progress has been made towards proving this lower bound. The more general problem of determining sat_{δ}(n, K_{p}) can also be considered. Indeed, one of the results of [AEHK96] (see Theorem 2) implies that sat_{δ}(n, K_{p}) = δn + O(\frac{n}{log log n}). O. Pikhurko [Pik04] improved the error term in the following.

Theorem 7. [Pik04] For any fixed δ ≥ p − 1, sat_{δ}(n, K_{p}) = δn + O(\frac{n log log n}{log n}).

Additionally, as a means of estimating sat_{δ}(n, K_{p}) Duffus and Hanson introduce the idea of a minimally color-critical graph. If we look again at the graph K_{p−2} + \overline{K}_{n−p+2}, we see that its chromatic number is p − 1 and the addition of any edge increases the chromatic number to p. Suppose G is a graph on n vertices with chromatic number p − 1 and minimum degree at least δ. They define χ_{δ}(n, p) to be the minimum number of edges that G can have such that the addition of any edge to G increases the chromatic number. Such graphs are called minimal (χ, δ)-saturated graphs. Duffus and Hanson find the value of χ_{δ}(n, p) precisely and show that the extremal graph corresponding to it is unique, consisting of a complete (p − 1)-partite graph with suitably sized partite sets. More precisely, they give the following. .

Theorem 8. [DH86] For integers n, p, δ, such that 2 ≤ p ≤ n, δ ≥ p − 2, the complete (p − 1)-partite graph with (p − 2 − ⌊\frac{n−p+1}{n−δ−1}⌋) parts of cardinality one, ⌊\frac{n−p+1}{n−δ−1}⌋ parts having cardinality (n − δ), and one part having cardinality n − (p − 2 − ⌊\frac{n−p+1}{n−δ−1}⌋) − ⌊\frac{n−p+1}{n−δ−1}⌋(n − δ) is the only n-vertex minimal (χ, δ)-saturated graph.

It is, in fact, χ_{δ}(n, p) that provides an upper bound for the number of edges in a K_{p}-saturated graph with prescribed minimum degree. This upper bound is a direct consequence of the construction in the previous theorem (as noted in Theorem 2 of [DH86]).

Finally, we mention the problem of determining the minimum size of a non-(p − 1)- partite K_{p}-saturated graph. For p = 3, this was solved by C. Barefoot, K. Casey, D. Fisher, K. Fraughnaugh, and F. Harary [BCF^{+}95]. For p = 3, such a graph has 2n − 5 edges and can be obtained by duplicating two non-adjacent vertices of a C_{5}. For p > 3, the problem has been solved and results are forthcoming [Gou].

2.2 Unions of cliques, complete partite graphs, and more

Another extension is to consider graphs which generalize the complete graph. One approach is to consider unions of cliques. For a graph F, let tF denote the disjoint union of t copies of F.

In [FFGJ09b], R. Faudree, M. Ferrara, R. Gould, and M. Jacobson determined sat(n, tK_{p}) and sat(n, K_{p}∪K_{q}) precisely as illustrated by K_{p−2}+\{(t−1)K_{p+1}∪\overline{K}_{n−pt−t+3}\} and K_{p−2} + \{K_{q+1} ∪ \overline{K}_{n−q−p+1}\} (for p ≤ q), respectively.

Theorem 9. [FFGJ09b] Let t ≥ 1, p ≥ 3 and n ≥ p(p + 1)t − p^{2} + 2p − 6 be integers. Then

sat(n, tK_{p}) = (t − 1)\binom{p + 1}{2} + \binom{p − 2}{2} + (p − 2)(n − p + 2).

Furthermore, if t = 2 or 3, the extremal graph, respectively, is unique.

This was built on previous work of W. Mader [Mad73] who considered the case p = 2. Using similar techniques, R. Faudree et al. [FFGJ09b] were able to establish the

saturation number for generalized friendship graphs. That is, for integers t, p, and l, define F_{t,p,l} to be the graph composed of t copies of K_{p} intersecting in a common K_{l}.

Theorem 10. [FFGJ09b] Let p ≥ 3, t ≥ 2 and p − 2 ≥ l ≥ 1 be integers. Then, for sufficiently large n,

sat(n, F_{t,p,l}) = (p − 2)(n − p + 2) + \binom{p − 2}{2} + (t − 1)\binom{p − l + 1}{2}.

The value of sat(n, K_{p} ∪ K_{q} ∪ K_{r}) is still open and, as the authors observe, the construction they use to establish an upper bound for sat(n, K_{p} ∪ K_{q}) (which they determine exactly) does not apply in this case. Also, it is not known in general if Sat(n, tK_{p}) is unique for t ≥ 4.

Problem 2. [FFGJ09b] Investigate sat(n, K_{p} ∪ K_{q} ∪ K_{r}) or sat(n, 2K_{p} ∪ K_{q}).

Another generalization is to complete partite graphs. Let K_{s_{1},...,s_{p}} denote the complete p-partite graph with partite sets of size s_{1}, …, s_{p} and 1 ≤ s_{1} ≤ … ≤ s_{p} and p ≥ 2. Note that the star K_{1,k−1} with k vertices will be considered in Section 4, and the 4-cycle K_{2,2} ≅ C_{4} in Section 3. O. Pikhurko and J. Schmitt [PS08] considered the graph K_{2,3} and proved the following.

Theorem 11. [PS08] There is a constant C such that for all n ≥ 5 we have

2n − Cn^{3/4} ≤ sat(n, K_{2,3}) ≤ 2n − 3.

O. Pikhurko [Pik04] computed sat(n, K_{1,...,1,s}) exactly for n sufficiently large, as subsequently did G. Chen, R. Faudree and R. Gould [CFG08] while simultaneously giving better estimates on n. R. Gould and J. Schmitt [GS07] considered the graph K_{2,...,2} and determined the extremal graph under the assumption that the graph has a vertex of smallest possible minimum degree. A very recent result of T. Bohman, M. Fonoberova, and O. Pikhurko [BFP10] confirmed that sat-function for a complete multipartite graph behaves asymptotically like the upper bound provided for this graph by Theorem 2.

Theorem 12. [BFP10] Let p ≥ 2, s_{p} ≥ … ≥ s_{1} ≥ 1. Then for all large n,

sat(n, K_{s_{1},...,s_{p}}) = (s_{1} + … + s_{p−1} + \frac{s_{p} − 3}{2})n + O(n^{3/4}).

Additionally, Bohman et al. are able to provide a stability type result — the first such result in the study of this function! That is, K_{s_{1},...,s_{p}}-saturated graphs with at most sat(n, K_{s_{1},...,s_{p}}) + o(n) edges can be changed into the construction provided by Theorem 2 by adding and removing at most o(n) edges. The authors note that the exact determination of the saturation number for complete multipartite graphs is an interesting open problem (a conjecture for the exact value of sat(n, K_{2,...,2}) is given in [GS07]). They [BFP10] also conjectured that sat(n, K_{2,3}) = 2n − 3 for all large n. This conjecture was recently confirmed by Y.-C. Chen [Che].

2.3 Edge coloring

Let F_{1}, F_{2}, …, F_{t} be graphs. We will say that a graph G is (F_{1}, F_{2}, …, F_{t})-saturated if there exists a coloring C of the edges of G in t colors 1, 2, …, t in such a way that there is no monochromatic copy of F_{i} in color i, 1 ≤ i ≤ t, but the addition of any new edge (i.e. an edge not already in G) of color i with C creates a monochromatic F_{i} in color i, 1 ≤ i ≤ t. D. Hanson and B. Toft [HT87] determined the minimum number of edges (and the maximum number of edges) in an (K_{m_{1}}, K_{m_{2}}, …, K_{m_{t}})-saturated graph. In particular, they showed that the extremal graph is K_{m−2t} + \overline{K}_{n−m+2t} where m = ∑_{i=1}^{t} m_{i} for n ≥ m − 2t + 1.

They also considered a more restrictive question. We say that a graph F arrows a t-tuple (F_{1}, F_{2}, …, F_{t}) of graphs, which is denoted F → (F_{1}, F_{2}, …, F_{t}), if any t-coloring of E(F) contains a monochromatic F_{i}-subgraph of color i for some i ∈ [t]. D. Hanson and B. Toft [HT87] gave the following.

Conjecture 1. Given t ≥ 2 and integers m_{i} ≥ 3, i ∈ [t], let

F = {F : F → (K_{m_{1}}, K_{m_{2}}, …, K_{m_{t}})}.

Let r = r(K_{m_{1}}, K_{m_{2}}, …, K_{m_{t}}) be the classical Ramsey number. Then

sat(n, F) = \binom{r − 2}{2} + (r − 2)(n − r + 2).

Notice that the conjecture reduces to Theorem 1 in the case where either t = 1 or m_{2} = … = m_{t} = 2.

G. Chen, M. Ferrara, R. Gould, C. Magnant, and J. Schmitt [CFG^{+}] confirmed this conjecture in the smallest instance, that is, for the family of graphs that arrow the pair (K_{3}, K_{3}) and n ≥ 56. These authors also determine the saturation number for the family F = {F : F → (K_{3}, P_{3})}. The conjecture of Hanson and Toft remains open and the more general problem seems challenging.

Question 2. Given t ≥ 2, and graphs F_{1}, …, F_{t}, let F = {F : F → (F_{1}, F_{2}, …, F_{t})}. What is sat(n, F)?

3 Cycles

We now consider C_{l}-saturated graphs where C_{l} denotes the cycle on l vertices. We begin by discussing the known results for small values of l, after which we focus on the case when l = n. The reader will find that for small values of l exact results are known only for l ≤ 5. For l ≥ 6, a lower bound and some upper bounds are established. Finding precise values appears to be quite difficult; the reader might try determining sat(n, C_{6})! For l = n, the saturation number is established through the collective work of many people. There are several interesting questions regarding the behavior of sat(n, C_{l}).

In his text on extremal graph theory (p. 167, Problem 39), B. Bollobás [Bol04] gave the problem of estimating sat(n, C_{l}) for 3 ≤ l ≤ n. When l = 3, as C_{3} ≅ K_{3}, the value of sat(n, C_{l}) is given by the result of [EHM64]. In 1972 L.T. Ollmann [Oll72] determined that sat(n, C_{4}) = ⌊\frac{3n−5}{2}⌋ for n ≥ 5 (this differs from the erroneous value for the function for this case given in [Bol78] p.167, Problem 40) and gave the set of extremal graphs. Later, Zs. Tuza [Tuz89] gave a shorter proof. Tuza’s proof is a rare instance in which an inductive argument (for a particular case) is used in proving a lower bound on sat(n, F). A slight extension was given by D. Fisher, K. Fraughnaugh, L. Langley [FFL97]. A graph is P_{l}-connected if every pair of nonadjacent nodes is connected by a path with l vertices. (It should be noted that this concept has sometimes been defined as a path with l edges, as opposed to l vertices). Observe that a C_{l}-saturated graph is necessarily P_{l}-connected, though a P_{l}-connected graph need not be C_{l}-saturated. Fisher et al. determined the minimum size of a P_{4}-connected graph, thus generalizing Ollmann’s result. This class of extremal graphs properly contains those of Ollmann.

Theorem 13. [Oll72],[Tuz89],[FFL97] For n ≥ 5, sat(n, C_{4}) = ⌊\frac{3n−5}{2}⌋.

D. Fisher, K. Fraughnaugh, and L. Langley [FFL95] gave an upper bound for sat(n, C_{5}) of ⌈\frac{10}{7}(n − 1)⌉. Recently, a very technical proof given by Y.-C. Chen [Che09] has shown that this upper bound also serves as a lower bound for n ≥ 21. In a subsequent manuscript [Che11], Y.-C. Chen has determined Sat(n, C_{5}) - an impressive feat considering the number and structure of the extremal graphs involved.

Theorem 14. [Che09][Che11] For n ≥ 21, sat(n, C_{5}) = ⌈\frac{10}{7}(n − 1)⌉.

C. Barefoot, L. Clark, R. Entringer, T. Porter, L. Székely, and Zs. Tuza [BCE^{+}96] gave constructions that showed that for l ≠ 8 or 10 and n sufficiently large there exists a positive constant c such that sat(n, C_{l}) is bounded above by n + c\frac{n}{l}. For small values of l their constructions rely upon, what they call, C_{l}-builders. C_{l}-builders are C_{l}-saturated graphs (of generally small order) which are used to “build” C_{l}-saturated graphs of large order by identifying many copies of the C_{l}-builder at a particular vertex. The main result in [Che11] implies that most graphs in Sat(n, C_{5}) have this structure. Note that the particular vertex at which the copies are identified is a cut-vertex. The construction given for l = 6 gives that sat(n, C_{6}) ≤ \frac{3n}{2} for n ≥ 11. We mention this case as not only is it the smallest instance for which we do not know the value of the function precisely but also because it is the only instance for which the upper bounds given in [BCE^{+}96] have not been improved despite subsequent work by various authors. However, R. Gould, T. Łuczak, and J. Schmitt [GŁS06] did improve the constant c of the upper bound given in [BCE^{+}96] for all l ≥ 8. For certain values of l their constructions resemble a bicycle wheel and do not contain cut-vertices. These wheel constructions showed that sat(n, C_{l}) ≤ (1 + \frac{2}{l−ϵ(l)})n + O(l^{2}), where ϵ(l) = 2 for l even ≥ 10, ϵ(l) = 3 for l odd ≥ 17. Z. Füredi and Y. Kim [FK] very recently improved upon these bounds with a much simpler construction.

Barefoot et al. also gave the first non-trivial lower bound on sat(n, C_{l}) for n ≥ l ≥ 5. Füredi and Kim improved upon their argument to obtain a better lower bound.

The main result of [FK] is the following.

Theorem 15. [FK] For all l ≥ 7 and n ≥ 2l − 5,

(1 + \frac{1}{l + 2})n − 1 < sat(n, C_{l}) < (1 + \frac{1}{l − 4})n + \binom{l − 4}{2}.

The reader will notice that a gap still exists between upper and lower bounds. However, Füredi and Kim believe that the constructions that yield the upper bound are essentially optimal and they pose the following.

Conjecture 2. [FK] There exists an l_{0} such that sat(n, C_{l}) = (1 + \frac{1}{l−4})n + O(l^{2}) holds for each l > l_{0}.

We now turn our attention to the case when l = n.

In an effort to understand the structure of hamiltonian graphs or conditions which imply when a graph is hamiltonian, authors have often focused on when a graph just fails to be hamiltonian. One such focus is C_{n}-saturated graphs, often referred to as maximally non-hamiltonian (MNH) graphs. Thus the question of determining sat(n, C_{n}) is rather ‘natural.’

The first result on C_{n}-saturated graphs of minimal size is due to A. Bondy [Bon72]. He showed that if such a graph G of order at least 7 has m vertices of degree two then it has size at least \frac{1}{2}(3n + m). As an MNH graph with a vertex of degree one must be a clique with a pendant edge (which in fact implies that the graph is edge maximum), this result implies that sat(n, C_{n}) ≥ ⌈\frac{3n}{2}⌉. As a result, it is logical to consider 3-regular graphs in the search for graphs in Sat(n, C_{n}). Bondy also pointed out that the Petersen graph, which has girth five, is in Sat(10, C_{10}).

Another famous 3-regular graph, the Coxeter graph, which has girth seven, was shown to be in Sat(28, C_{28}) by L. Clark and R. Entringer [CE83a]. Previously, however, W. Tutte [Tut60] had shown it to be non-hamiltonian and H.S.M. Coxeter himself [Cox81] knew that his graph was an MNH graph.

If a graph is 3-regular and hamiltonian, then it is 3-edge colorable. This makes 4edge-chromatic 3-regular graphs suitable candidates for Sat(n, C_{n}). Over the course of several papers [CE83a], [CCES86], [CES92], where each paper included some subset of the following authors - L. Clark, R. P. Crane, R. Entringer, and H.D. Shapiro, it was shown that sat(n, C_{n}) does indeed equal ⌈\frac{3n}{2}⌉ for even n ≥ 36 and odd n ≥ 53. They showed that graphs which help establish equality include the Isaacs’ flower snarks (which R. Isaacs [Isa75] showed were 4-edge-chromatic 3-regular graphs), most of which have girth six, and variations of them. These variations are obtained through “blowing up” a degree three vertex into a triangle. Through the aid of a computer search, X. Lin, W. Jiang, C. Zhang, and Y. Yang [LJZY97] analyzed the remaining small cases and were able to determine that the value of sat(n, C_{n}) matched the lower bound provided by Bondy except in a few small cases. Together, these results imply the following.

Theorem 16. For all even n ≥ 20 and odd n ≥ 17, we have sat(n, C_{n}) = ⌈\frac{3n}{2}⌉.

P. Horák and J. Širáň [HŠ86] constructed triangle-free MNH graphs of near minimal size using a construction technique of C. Thomassen [Tho74]. Thomassen’s technique involves “pasting” together two graphs at two vertices of degree three. Thomassen was interested in constructing families of hypo-hamiltonian graphs (non-hamiltonian graphs which become hamiltonian upon the removal of any vertex) and his technique builds a new hypo-hamiltonian graph from two smaller ones. Horák and Širáň show that the technique also works for MNH graphs when the smaller graphs are copies of either the Petersen graph or an Isaacs’ flower snark. The technique does not decrease the length of the shortest cycle, thus the graphs constructed are triangle-free. L. Stacho [Sta96] also used this technique on copies of the Coxeter graph, yielding MNH graphs of girth seven.

Problem 3. [HŠ86] Does there exist an MNH graph of girth greater than seven?

Problem 4. Furthermore, if there is such a graph, is there one of (near) minimal size?

L. Stacho [Sta98] also proved that |Sat(n, C_{n})| ≥ 3 for all n ≥ 88 and showed that lim_{n→∞} |Sat(n, C_{n})| = ∞, answering a question of L. Clark and R. Entringer [CE83a].

We end this section with a list of open problems.

Question 3. [BCE^{+}96] Is sat(n, C_{l}) a convex function of l, l > 3, for fixed n? Or is it convex at least when the parity of l is fixed?

If the answer to this question is in the affirmative, then one ought to be able to find a better upper bound for, say, l = 9.

Problem 5. [BCE^{+}96] Determine the value of l which minimizes sat(n, C_{l}) for fixed n.

Question 4. [BCE^{+}96] Is lim sup_{n} sat(n, C_{l})/n a decreasing function of l, at least for odd l and even l, respectively?

Question 5. [Łuc]For every x ∈ [0, 1] define a function f(x) in the following way:

f(x) = lim sup_{n→∞}(sat(n, C_{⌈xn⌉}))/n − 1.

As f(1) = \frac{1}{2}, and, most probably, f(x) = O(1/x) for small x, does f(x) → 0 as x → 0? Is f(x) continuous in [0, 1]? Is it strictly increasing? For instance, is it true that, say, f(0.99) = \frac{1}{2}?

4 Trees and forests

Trees and forests have been the focus of study for a couple of reasons. The primary one is that their simplicity has made at least some precise results possible. A second and less obvious reason is their role as building blocks to larger results. Recall that the implicitly constructive nature of the proof of Theorem 2 required the use of a K_{1,d−1}-saturated graph. (Note that in this section K_{1,d−1} = S_{d} and will be called a star.) While there are several types of trees for which the saturation number is known and in fact several for which Sat(n, T) is characterized, there are far more trees for which little is known at all. The most intriguing question regarding saturation number and trees is Question 8 in the next section.

In [KT86], L. Kászonyi and Zs. Tuza established sat(n, S_{k}), characterized Sat(n, S_{k}), and proved that, of all the trees on k vertices, S_{k}, has the largest saturation number.

Theorem 17. [KT86] Let S_{k} = K_{1,k−1} denote a star on k vertices. Then,

sat(n, S_{k}) = \begin{cases}\binom{k−1}{2} + \binom{n−k+1}{2} & if k ≤ n ≤ \frac{3k−3}{2}, \\ ⌈\frac{k−2}{2}n − \frac{(k−1)^{2}}{8} ⌉ & if \frac{3k−3}{2} ≤ n, \end{cases}

Sat(n, S_{k}) = \begin{cases}K_{k−1} ∪ K_{n−k+1} & if k ≤ n ≤ \frac{3k−3}{2}, \\ G′ ∪ K_{⌊k/2⌋} & if \frac{3k−3}{2} ≤ n, \end{cases}

where G′ is a (k − 1)-regular graph on n − ⌊k/2⌋ vertices. Also note that in the second case (n ≥ \frac{3k−3}{2}), an edge is added between G′ and K_{⌊k/2⌋} if k − 1 and n − ⌊k/2⌋ are both odd.

Furthermore, let T be a tree on k vertices such that T ≠ S_{k}, then sat(n, T) < sat(n, S_{k}).

Both results are proved simultaneously by observing that any S_{k}-saturated graph has maximum degree at most k − 2 and that the set of vertices of degree less than k − 2 must induce a complete graph. The number of edges in such a graph is bounded below by f(s) = (n − s)(k − 2)/2 + \binom{s}{2} where s is the number of vertices of small degree. All that is left is to show that f is minimized at the respective values and construct the graphs that realize these lower bounds.

Similar results were given by K. Balińska, L. Quintas, and K. Zwierzyński [BQZ06]. They considered S_{k}-saturated graphs where the number of vertices of degree strictly less than k − 1 is bounded.

In [FFGJ09a], J. Faudree, R. Faudree, R. Gould and M. Jacobson show that of all the trees on k ≥ 5 vertices the tree T_{0} obtained by subdividing a single edge of a star on k − 1 vertices has smallest saturation number.

Theorem 18. [FFGJ09a] For n ≥ k + 2, sat(n, T_{0}) = n − ⌊(n + k − 2)/k⌋ and Sat(n, T_{0}) consists of a forest of stars on k or more vertices.

Question 6. [FFGJ09a] Among all trees of order k, which is the tree(s) of second highest and the tree(s) of second lowest saturation number?

Many other results and problems on trees can be found in [FFGJ09a]. In particular, it is shown that given any positive number α and any tree T there is a tree T′ with T ⊆ T′ such that sat(n, T′) ≥ αn, and also for any tree T there is a tree T′′ with T ⊆ T′′ such that sat(n, T′′) < n. That is, there is a series of nested trees with alternating saturation numbers small and large. Thus, there are many trees with large saturation numbers and many trees with small saturation numbers. This ‘non-monotone’ condition is discussed further in the next section. However, the tree that is most fully understood is the path, P_{k}.

In [KT86], L. Kászonyi and Zs. Tuza found sat(n, P_{k}) for all k and n sufficiently large and also characterized the family of graphs in Sat(n, P_{k}). Specifically, they prove that all minimally P_{k}-saturated trees have a common structure, referred to as an almost binary tree. More specifically, for even k = 2p + 2, the base tree T_{k} is a binary tree with root of degree 3 and depth p. For odd k = 2p + 3 the tree T_{k} is a binary tree with double roots of degree 3 and depth p.

Not only is T_{k} a P_{k}-saturated tree but the addition of any number of pendant vertices to those vertices already adjacent to vertices of degree 1 does not change this property. In the theorem below, observe that a_{k} = |V (T_{k})|.

Theorem 19. [KT86] Let P_{k} be a path on k ≥ 3 vertices and let T_{k} be the tree defined above.

Let a_{k} = \begin{cases}3 · 2^{m−1} − 2 & if k = 2m, \\ 4 · 2^{m−1} − 2 & if k = 2m + 1. \end{cases} Then, for n ≥ a_{k}, sat(n, P_{k}) = n − ⌊\frac{n}{a_{m}} ⌋ and

every graph in Sat(n, P_{k}) consists of a forest with ⌊n/a_{k}⌋ components. Furthermore, if T is a P_{k}-saturated tree, then T_{k} ⊆ T.

While sat(n, P_{k}) is known for all n for k ≤ 6 (see [KT86] and [DW04a]), for the other cases, the result above only applies for n sufficiently large. In A. Dudek and A. Wojda [DW04a], some improvement was made. Specifically, it was shown that sat(n, P_{k}) = n for b_{k} ≤ n < a_{k} where b_{k} is on the order of 2^{m−2}. Also, Sat(n, P_{k}) on this interval was characterized and some general upper bounds were established.

Furthermore, when n = k much more is known. In A. Dudek, G. Katona, and A. Wojda [DKW03], some graphs in Sat(n, P_{n}) were constructed from minimally hamiltonian saturated graphs (found in [CES92]). Though the exact structure of all graphs in Sat(n, P_{n}) seems to be quite complicated, this at least established an upper bound on sat(n, P_{n}). The lower bound from this paper was improved by M. Frick and J. Singleton [FS05] and it is known that sat(n, P_{n}) = ⌈\frac{3n−2}{2}⌉ for n ≥ 54 and several small order cases.

Theorem 20. [DKW03] and [FS05] For n ≥ 54, sat(n, P_{n}) = ⌈\frac{3n−2}{2}⌉.

The notion of a hamiltonian path can be generalized to an m-path cover. That is, we say F is an m-path cover of G if all components of F are paths, V (F) = V (G), and F has at most m components. We say a graph G is m-path cover saturated (or mPCS) if G does not contain an m-path cover but connecting any two nonadjacent vertices with an edge creates an m-path cover. In A. Dudek, G. Katona, and A. Wojda [DKW06], it was shown that \frac{3}{2}n − 3m − 3 ≤ sat(n, mP CS) ≤ \frac{3}{2}n − 2m + 2.

An m-path cover is a specific kind of forest. The only other forest with unbounded number of components for which the saturation number is known is matchings. Specifically, in [KT86], it was proved that if n ≥ 3m−3, sat(n, mK_{2}) = 3m−3 and Sat(n, mK_{2}) consists of m − 1 disjoint triangles and n − 3m + 3 isolated vertices.

Theorem 21. [KT86] For n ≥ 3m − 3

sat(n, mK_{2}) = 3m − 3

and

Sat(n, mK_{2}) = (m − 2)K_{3} ∪ (n − 3m + 3)K_{1}.

In [CFF^{+}] G. Chen, J. Faudree, R. Faudree, R. Gould, and C. Magnant investigated the saturation numbers for forests in which the components were all paths or all stars. Precise numbers were determined for sat(n, mP_{k}) and sat(n, mK_{1,k}) for small values of m and k and upper bounds were given in the general case.

Some open questions are given below.

Problem 6. Determine sat(n, P_{k}) and Sat(n, P_{k}) when n is small relative to k.

Problem 7. Determine sat(n, P_{n}) for the remaining small order cases.

Problem 8. Determine sat(n, mP CS).

Problem 9. Determine sat(n, mK_{2}) and Sat(n, mK_{2}) for 2m ≤ n ≤ 3m − 4. Note that the structure of mK_{2}-saturated graphs was determined in [Mad73].

Problem 10. Determine sat(n, mP_{k}) and sat(n, mK_{1,k}) for all m and k.

5 Irregularity of the sat-function

The function sat(n, F), in general, is not monotone with respect to n or F. Turán’s extremal function is monotone with respect to n and F. That is, for F′ ⊆ F and F′ ⊆ F the following inequalities hold for every n.

ex(n, F′) ≤ ex(n, F)  (2)
ex(n, F) ≤ ex(n, F′)  (3)
ex(n, F) ≤ ex(n + 1, F)  (4)

We note that if we replace ex by sat in each of the above inequalities, then for every F′ ⊆ F and F′ ⊆ F we need not have a true statement. Prior to giving examples that illustrate when these inequalities fail, we note that the failure to be monotone makes proving statements about sat(n, F) difficult. In particular, inductive arguments generally do not work — this may also be due to the non-uniqueness of the extremal graphs; for example, see the result on K_{2,2} [Oll72] or [Che11]. The failure to be monotone also may explain the scarcity of results for sat(n, F), but in the authors’ collective opinion makes the function an interesting study.

To see that the sat-function is not, in general, monotone with respect to subgraphs, consider the ‘irregular pair’ as given by O. Pikhurko [Pik04], and that answered a question of Zs. Tuza [Tuz92] about the existence of a connected spanning subgraph F′ of subgraph F. Let F′ = K_{1,m} and F = K_{1,m} + e, where e joins two vertices in the m-set. Then sat(n, F) ≤ n − 1 as K_{1,n−1} serves as an extremal graph. However, sat(n, F′) is strictly larger for n large enough as seen by Theorem 17. Even in the class of trees, this monotone property fails at a very high level, and was observed in the previous section (see [FFGJ09a]).

To see that the sat-function is not, in general, monotone with respect to subfamilies, consider F = {K_{1,m}, K_{1,m} + e} and F′ = {K_{1,m} + e}. Then sat(n, F) = sat(n, K_{1,m}) > n − 1, but sat(n, F′) ≤ n − 1. (Note that for any F′ ⊂ F, F, F′ ∈ F then sat(n, F) = sat(n, F \ F).)

To see that the sat-function is not, in general, monotone in n, consider when F = P_{4}. By a result in [KT86], we have sat(2k − 1, P_{4}) = k + 1 > sat(2k, P_{4}) = k.

As a result of this ‘irregularity’, Zs. Tuza [Tuz86] (more readily available in [Tuz88]) made the following conjecture.

Conjecture 3. [Tuz86],[Tuz88] For every graph F, the limit lim_{n→∞} \frac{sat(n,F)}{n} exists.

Some progress towards settling this conjecture has been made, both in the positive and negative direction. However, the conjecture still remains open. We first give statements in the positive direction.

Theorem 22. [TT91] Let F be a graph. If lim inf_{n→∞} \frac{sat(n,F)}{n} < 1, then lim_{n→∞} \frac{sat(n,F)}{n} exists and is equal to 1 − \frac{1}{p}, for some positive integer p.

A characterization of graphs for which lim_{n→∞} \frac{sat(n,F)}{n} = 1 − \frac{1}{p} for any given p is given in terms of connected components. Unfortunately, this characterization ‘grows’ with p. In the characterization tree components of F play a role. Thus, Tuza gave the following problem.

Question 7. [Tuz88] Which trees T satisfy lim_{n→∞} \frac{sat(n,T)}{n} < 1?

Towards the negative direction of settling Conjecture 3, O. Pikhurko [Pik99a] showed that there exists an infinite family F of graphs for which lim_{n→∞} \frac{sat(n,F)}{n} does not exist. Later, in [Pik04] he improved this to show that for every integer m ≥ 4 there exists a family F consisting of m graphs for which lim_{n→∞} \frac{sat(n,F)}{n} does not exist, and suggested that his approach might be altered to yield a smaller family.

In addition, G. Semanišin [Sem97] has given certain instances under which the satfunction is monotone and uses these to prove some inequalities and estimations.

6 Hypergraphs

We now consider F -saturated graphs where F is a hypergraph and we restrict our attention to k-uniform hypergraphs (all edges are of size k) as these are the only results known.

6.1 Complete hypergraphs

We introduce the following notation. Consider a vertex partition S_{1} ∪ … ∪ S_{p} of F where |S_{i}| = s_{i}. For k ≤ p let W_{s_{1},...,s_{p}}^{k} denote the k-uniform hypergraph consisting of all k-tuples that intersect k different parts (and call this the weak generalization of a complete graph). Let S_{s_{1},...,s_{p}}^{k} denote the k-uniform hypergraph consisting of all k-tuples that intersect at least two parts (and call this the strong generalization of a complete graph). Most results, but not all, for F -saturated hypergraphs are when F is one of these graphs.

An early generalization of Theorem 1 was given by B. Bollobás [Bol65].

Theorem 23. [Bol65]

sat(n, S_{1,...,1}^{k}) = \binom{n}{k} − \binom{n − p + k}{k}

where p counts the number of classes in the partition. Further, there exists a unique extremal graph.

Bollobás achieved this as the result of introducing a powerful weight inequality, the simplest version of which is given in the introduction as Theorem 3. This inequality is an extension of the Lubell-Yamamoto-Meshalkin inequality, itself an extension of Sperner’s Lemma from 1928. More importantly, N. Alon [Alo85] generalized Bollobás’ weight inequality, in fact, it is a special case of a corollary to his main result.

P. Erdős, Z. Furedi, and Zs. Tuza [EFT91] consider the saturation problem for families of hypergraphs with a fixed number of edges. Among these are the graphs S_{1,k}^{k}.

Theorem 24. [EFT91] For n ≥ 4, sat(n, S_{1,3}^{3}) = ⌊\frac{(n−1)^{2}}{4} ⌋. Moreover, there are two or one extremal hypergraphs according as n is odd or even.

They also determined the asymptotic behavior of the function for the graph S_{1,k}^{k} for n > k ≥ 2. O. Pikhurko [Pik00] went further.

Theorem 25. [Pik00] Let m > k ≥ 2. Then

\frac{m − k}{2} \binom{n}{k − 1} ≥ sat(n, S_{1,m−1}^{k}) ≥ \frac{m − k}{2} \binom{n}{k − 1} − O(n^{k−4/3}).

Later, Pikhurko [Pik04] posed the following.

Conjecture 4. [Pik04] For l ≤ k − 1 and l + m > k,

sat(n, S_{l,m}^{k}) = \frac{m + 2l − k − 1}{2(k − 1)!}n^{k−1} + o(n^{k−1}).

the electronic journal of combinatorics 18 (2011), #DS19 19

6.2 Asymptotics

With the thought of extending Theorem 2 to hypergraphs, Zs. Tuza [Tuz86] (more readily available in [Tuz88]) conjectured that for any k-uniform hypergraph F, sat(n, F) = O(n^{k−1}). This was positively confirmed.

Theorem 26. [Pik99a] For any finite family F of k-uniform hypergraphs, we have

sat(n, F) = O(n^{k−1}).

More generally, we can ask the following.

Question 8. [Pik04] Does sat(n, F) = O(n^{k−1}) for any infinite family of k-graphs?

Also, in light of the irregularity of the sat-function as discussed in Section 5 Pikhurko also asked: does there exist a finite family F of k-uniform hypergraphs, k ≥ 3, for which the ratio \frac{sat(n,F)}{n^{k−1}} does not tend to any limit? (For k = 2, see the discussion in Section 5.)

For a hypergraph F and edges E, E′ ∈ F, the density of an edge E, D(E), is the largest natural number D such that there is an E′, E ≠ E′ with |E ∩ E′| ≥ D. The local density of the hypergraph F, D(F), is min{D(E) : E ∈ F }. Zs. Tuza [Tuz92] conjectured the following.

Conjecture 5. [Tuz92] For a hypergraph F there exists a constant c depending on F such that sat(n, F) = cn^{D(F)} + O(n^{D(F)−1}).

6.3 A few specific problems

Triangular family

Let T_{k} denote the family which consists of all k-uniform hypergraphs with three edges E_{1}, E_{2}, E_{3} such that E_{1}ΔE_{2} ⊆ E_{3}, where Δ denotes the symmetric difference. We call T_{k} a triangular family.

Theorem 27. [Pik04] Let k ≥ 3 be fixed. Then

n − O(log n) ≤ sat(n, T_{k}) ≤ n − k + 1.

And, for k = 3 equality holds on the right.

Conjecture 6. [Pik04] In Theorem 27 equality holds on the right.

Intersecting hypergraphs

We will call a k-uniform hypergraph F intersecting (sometimes called disjoint-edges-free) if for every pair of edges of F the intersection of the pair is non-empty. (Some authors call such graphs k-cliques, however we refrain from doing so in light of how we wish to use this term elsewhere in this survey.) We say that such a graph is maximal if it cannot be extended to another intersecting hypergraph by adding a new edge and possibly new vertices. P. Erdős and L. Lovász [EL75] first investigated the minimum number and maximum number of edges in a maximal intersecting k-uniform hypergraph. In light of the topic of this survey, we are most interested in the minimum number of edges in a maximal intersecting k-uniform hypergraph, m(k). Note that the function is independent of n for n sufficiently large.

Erdős and Lovász [EL75] gave a lower bound on m(k) of \frac{8k}{3} − 3, while Z. Füredi gave an upper bound of 3k^{2}/4 whenever k = 2n for an integer n that is the order of a projective plane. We know from J.C. Meyer [Mey74] that trivially m(1) = 1 and m(2) = 3, and that m(3) = 7. S. Dow, D. Drake, Z. Füredi, and J. Larson [DDFL85] improved the previously mentioned lower bound and gave the following.

Theorem 28. [DDFL85] For all k ≥ 4, m(k) ≥ 3k.

This result together with the upper bound of Füredi gives m(4) = 12.

Problem 11. Determine the value of m(k) for k > 4.

Disjoint-union-free

We say that a k-uniform hypergraph F is disjoint-union-free if all disjoint pairs of elements of F have distinct unions; that is, if for all E_{1}, E_{2}, E_{3}, E_{4} ∈ E(F), E_{1} ∩ E_{2} = E_{3} ∩ E_{4} = ∅ and E_{1} ∪ E_{2} = E_{3} ∪ E_{4} implies that {E_{1}, E_{2}} = {E_{3}, E_{4}}. Should this implication fail, we say E_{1}, E_{2}, E_{3}, E_{4} form a forbidden union. Let D_{k} denote the family of k-uniform hypergraphs such that each hypergraph is a set of 4 edges forming a forbidden union. (Note that D_{2} ≅ C_{4} and in this case we refer the reader to Section 3.)

P. Dukes and L. Howard [DH08] gave the following.

Theorem 29. [DH08]

sat(n, D_{3}) = \frac{n^{2}}{12} + O(n).

They also suggested the following.

Problem 12. [DH08] Determine sat(n, D_{k}) for k > 3.

7 Host graphs other than K_{n}

Note that in our definition of an F -saturated graph in the introduction, we allowed G to be any subgraph of K_{n}. We now consider F -saturated graphs where G is restricted to being a subgraph of some graph other than K_{n}.

More formally, let J be an n-vertex graph. We say that G ⊆ J is an F -saturated graph of J if G is F -free (i.e. has no subgraph isomorphic to F), but for every edge e not in E(G) but in E(J) the graph G + e does contain a copy of F. We define the following:

sat(J, F) = min{|E(G)| : V (G) = V (J), E(G) ⊆ E(J), and G is an F -saturated graph of J},

Sat(J, F) = {G : V (G) = V (J), E(G) ⊆ E(J), |E(G)| = sat(n, F), and G is an F -saturated graph of J}.

Thus, sat(K_{n}, F) and Sat(K_{n}, F) are by definition sat(n, F) and Sat(n, F), respectively. And, of course, we are interested in determining sat(J, F) and Sat(J, F) for various choices of J and F. This problem will, at times, be very challenging. A more approachable problem is made available with the following definition.

Let J_{(n_{1},...,n_{p})} be an n-vertex p-partite graph with n_{i} vertices in the i^{th} class. Let F_{(r_{1},...,r_{p})} be a p-partite graph with r_{i} ≤ n_{i} vertices in the i^{th} class. Then G ⊆ J_{(n_{1},...,n_{p})} is an F_{(r_{1},...,r_{p})}-saturated graph of J_{(n_{1},...,n_{p})} if G has no copy of F_{(r_{1},...,r_{p})} with r_{i} vertices in the i^{th} class, but G + e has a copy of F_{(r_{1},...,r_{p})} for any edge e joining vertices from distinct classes and contained in J_{(n_{1},...,n_{p})}. The difference between this definition and the previous one is that this is “sensitive” with respect to the partition. Analogously, we define sat(J_{(n_{1},...,n_{p})}, F_{(r_{1},...,r_{p})}) and Sat(J_{(n_{1},...,n_{p})}, F_{(r_{1},...,r_{p})}). Thus, the presence of parentheses in the subscript indicates that we are considering the partition “sensitive” problem, the absence of parentheses indicates we are considering the more general problem.

Problems of this type were first proposed in [EHM64]. Here the authors conjectured a value for sat(K_{(n_{1},n_{2})}, K_{(r_{1},r_{2})}), where K_{(n_{1},...,n_{p})} denotes the complete p-partite graph with n_{i} vertices in the i^{th} class. Their conjectured value was established to be correct by B. Bollobás ([Bol67b], [Bol67a]) and W. Wessel ([Wes66],[Wes67]). We thus have the following.

Theorem 30. Let 2 ≤ r_{1} ≤ n_{1} and 2 ≤ r_{2} ≤ n_{2}, then

sat(K_{(n_{1},n_{2})}, K_{(r_{1},r_{2})}) = n_{1}n_{2} − (n_{1} − r_{1} + 1)(n_{2} − r_{2} + 1)

and Sat(K_{(n_{1},n_{2})}, K_{(r_{1},r_{2})}) consists of one graph, the n_{1} by n_{2} bipartite graph consisting of all edges incident with a fixed set of size r_{1} − 1 of the n_{1}-set and all edges incident with a fixed set of size r_{2} − 1 of the n_{2}-set.

Also, and again, N. Alon [Alo85] reproved Theorem 30, generalizing it to complete k-uniform graphs in a k-partite setting — Alon’s generalization is a consequence of an extremal problem on sets which was proved using multilinear techniques (exterior algebra). Unaware of some of these results, D. Bryant and H.-L. Fu [BF02] considered K_{2,2}-saturated graphs of K_{n_{1},n_{2}} (which is the same as K_{(2,2)}-saturated graphs of K_{(n_{1},n_{2})}), showing how to construct such graphs (not just those of minimum size) using design theory. Another generalization of Theorem 30 can be found in the results on layered graphs of O. Pikhurko, for these we refer the reader to the Ph.D. thesis of O. Pikhurko [Pik99b] (cf. page 14).

The problem of determining sat(K_{n_{1},n_{2}}, P_{t}), where P_{t} is the path of order t, was considered by A. Dudek and A. P. Wojda [DW04a]. They determined the saturation number precisely for t ≤ 6 and for t > 6 they determined the value of the function under the added constraint that the graph contains no isolated vertices for n_{1}, n_{2} sufficiently large.

Problem 13. Determine sat(K_{n_{1},n_{2}}, C_{2t}) for t > 2, where C_{2t} denotes the cycle of order 2t.

Some attention has also been given to determining sat(Q_{n}, Q_{2}), where Q_{i} denotes the i-dimensional hypercube. S.-Y. Choi and P. Guan [CG08] give an asymptotic upper bound of (\frac{1}{4} + ϵ)n2^{n−1} and give exact values or sharper upper bounds for n ≤ 6. Anthony Santolupo (a former undergraduate student of the third author) conjectures that sat(Q_{n}, Q_{2}) is asymptotically \frac{1}{4}n2^{n−1}.

Problem 14. For a fixed k ≥ 2, determine sat(Q_{n}, Q_{k}).

Finally, quite recently the notion of minimal saturated matrices was introduced by A. Dudek, O. Pikhurko and A. Thomason [DPT]. We omit introducing the required definitions and terminology here, and we refer the reader to [DPT] for these and their results.

8 Graphs with directed edges

We now briefly focus our attention on graphs with directed edges. (Our focus is brief as the number of results is fairly limited. We restrict our attention to graphs; the only result for hypergraphs that we are aware of is given in [Pik99a],[Pik99b].)

Investigation in this direction began with Zs. Tuza [Tuz86] (he presented further results and a summary of earlier results in the more readily available [Tuz88]). We begin with some definitions found in [Pik99b]. Let C be a class of objects, with a binary relation ⊆. A member H of the class C is F-admissible if, for every F ∈ F, H does not contain F as a sub-object. Then we denote the family of maximal F-admissible objects of order n by SAT (n, F). H, of order n, is called F-saturated if H ∈ SAT (n, F), and if, in addition, H has minimum size, we say it has size sat(n, F).

O. Pikhurko [Pik99b] (cf. Section 4) asked if the order estimates given above (see Theorem 2 and Theorem 26) remain valid for the class of directed graphs. That is, for directed graphs do we have sat(n, F) = O(n)? He pointed out that, in general, the answer is no. As an immediate consequence to the main result of Z. Füredi, P. Horak, C. Pareek, and X. Zhu [FHPZ98], we have that sat(n, C_{3}) ≥ O(n log n) (where C_{3} has directed edges 12, 23 and 31); that is, the order estimate is super-linear! The results of these authors do not provide an upper bound (their constructions contain copies of C_{3}), and so we pose the following. Problem 15. In the class of directed graphs determine a good upper bound for sat(n, C_{3}).

O. Pikhurko [Pik99b] did show that the order estimates do remain valid under certain conditions. He considered the class of cycle-free directed graphs. A graph is cycle-free if it does not contain a cycle, in other words, there is no alternating sequence of vertices and edges (x_{1}, e_{1}, x_{2}, e_{2}, …, x_{l}, e_{l}, x_{l+1} = x_{1}) such that x_{i}x_{i+1} = e_{i}. So within the class of cycle-free directed graphs, a graph H is F-saturated if it contains no F ∈ F but the addition of any directed edge creates a copy of some F ∈ F or a directed cycle. Theorem 31. [Pik99b] In the class of cycle-free directed graphs sat(n, F) = O(n) for any family F of cycle-free graphs.

In addition, M. Jacobson and C. Tennenhouse [JT] considered sat(n, F) and showed that SAT (n, F) is non-empty for any F. They also give values and estimates for sat(n, P_{k}), where all arcs of P_{k} point in the ‘same direction’. Similar results were given earlier by S. van Aardt, J. Dunbar, M. Frick, and O. Oellermann [vAFDO09].

9 Saturation numbers and ....

In this section we consider the saturation function in relation to other functions in extremal graph theory.

9.1 extremal numbers

As noted in the introduction, P. Turán [Tur41] determined ex(n, K_{p}) and raised the question of determining ex(n, W\underbrace{1, …, 1}_{p}^{k}). Despite a strong understanding of the function

ex(n, F) for graphs (see [ES66]), his question remains unanswered for 3 ≤ k < p. In the case k = 3, p = 4, Turán conjectured that ex(n, W_{1,1,1,1}^{3}) = (\frac{5}{9} + o(1))\binom{n}{3} — more commonly known as Turán’s (3, 4)-conjecture.

In a series of papers O. Pikhurko [Pik99a] (cf. Section 3), [Pik01a] gave results that could be thought of as generalizing Theorem 17. Note that the star on m + 1 vertices is isomorphic to W_{1,m}^{2}. That is, Pikhurko first determined in [Pik99a] the asymptotic behavior of sat(n, W_{1,1,m}^{3}). Pikhurko [Pik01a] also gave a constructive upper bound for sat(n, W_{1,1,1,m}^{4}), while also considering the more general problem and giving a lower bound sat(n, W_{\underbrace{1, …, 1}_{p−1<k},m}^{k}) in terms of the extremal number. Specifically, we know that if Turán’s

(3, 4)-conjecture is true, then sat(n, W_{1,1,1,m}^{4}) = (\frac{m}{9} + o(1))\binom{n}{3}.

9.2 potential numbers

M. Ferrara and J. Schmitt [FS09] considered the following problem and related it to the saturation number. For a given graph F, an integer sequence π is said to be potentially F -graphic if there is some realization of π that contains F as a subgraph. Additionally, let σ(π) denote the sum of the terms of π. Define σ(n, F) to be the smallest integer m so that every n-term graphic sequence π with σ(π) ≥ m is potentially F -graphic. It is assumed that F has no isolated vertices and that n is sufficiently large relative to |V (F)|. Define the quantities u(F) = |V (F)|−α(F)−1, and s(F) = min{Δ(H) : H ⊆ F, |V (H)| = α(F)+1}. The following is an immediate consequence to Theorem 2 and the lower bound they establish for σ(n, F).

Theorem 32. [FS09] Let d be defined as in Theorem 2. Given a graph F, if there exists an F′ ⊆ F with 2u(F′) + s(F′) ≥ 2u(F) + d(F), then for n sufficiently large we have

2(sat(n, F)) < σ(n, F).  (5)

In particular, this result holds if d(F) = s(F).

These authors believe that the conclusion of Theorem 32 holds in general, even though the hypothesis does not. Therefore, they conjecture the following.

Conjecture 7. Let F be a graph and let n be a sufficiently large integer. Then

2(sat(n, F)) < σ(n, F).

10 Weak saturation

We now discuss the related notion of weakly saturated graphs. To do so, we first introduce some definitions and terminology.

Let k_{F} (G) count the number of copies of F in G; if F = K_{p} we will write k_{p}(G) in place of k_{K_{p}}(G). We say that an n-vertex graph G is weakly F -saturated if there is a nested sequence of graphs G = G_{0} ⊂ G_{1} ⊂ … ⊂ G_{l} = K_{n} such that G_{i} has exactly one more edge than G_{i−1} for 1 ≤ i ≤ l and k_{F} (G_{0}) < k_{F} (G_{1}) < … < k_{F} (G_{l}). (That is, G is weakly F -saturated if we can add the missing edges of G one at a time and each edge we add creates at least one new copy of F.) Of course, we are interested in the minimum size of a weakly F -saturated n-vertex graph, w-sat(n, F). Corresponding to this, an n-vertex graph that is weakly F -saturated and has w-sat(n, F) edges is said to be a member of W -Sat(n, F). The notion of weak saturation appears to have been introduced by B. Bollobás [Bol68]. In this paper he states that the problem of determining the saturation number for k-uniform hypergraphs with k ≥ 3 motivated the concept.

We first note that w-sat(n, F) ≤ sat(n, F) as any F -saturated graph is also weakly F -saturated. Of course, the first instance of the problem considered is when F = K_{p}. Bollobás [Bol68] showed that for 3 ≤ p < 7 we have w-sat(n, K_{p}) = sat(n, K_{p}) (see Theorem 1). Bollobás also conjectured that equality holds for at least some larger values of p, and later conjectured [Bol78] (see page 362) that equality holds for all p. The conjecture was confirmed by L. Lovász [Lov77] using flats of matroids representable over fields.

Theorem 33. For integers n and p, we have w-sat(n, K_{p}) = sat(n, K_{p}).

This result is of interest since the corresponding result in Turán extremal theory was such a key result, but it is also of great interest because of the many different proofs and mathematical tools used in the proofs. The different proofs found later included P. Frankl [Fra82], N. Alon [Alo85] and J. Yu [Yu93]. All of these proofs came from extremal results on pairs of families of sets with certain interesting properties that were then applied to obtain proofs of the conjecture of Bollobás on weakly K_{p}-saturated graphs. (For a statement of this more general result and discussion on how it implies the conjecture, see [GGL95] page 1274.)

Bollobás’ conjecture was also proved via two additional and different methods of G. Kalai in [Kal84] and [Kal85]. The first proof, which we give below, is based on the fact that an embedding of a weakly K_{p}-saturated graph G in ℝ^{p−2} with vertices in general position is rigid (continuous deformation of adjacent vertices preserving distance also preserves distance for all vertices). This, along with the fact that a graph G of order n with less than (p − 2)n − \binom{p−1}{2} edges embedded in ℝ^{p−2} is flexible (not rigid), completes the proof.

To give G. Kalai’s proof we need a few definitions. Given a graph G on vertex set {1, 2, …, n}, a d-embedding G(v) of G is a sequence of n points in ℝ^{d}, v = (v_{1}, v_{2}, …, v_{n}), together with the line segments [v_{i}, v_{j}], for {i, j} ∈ E(G). We say that G(v) is rigid if any continuous deformation (v_{1}(t), v_{2}(t), …, v_{n}(t)) of (v_{1}, v_{2}, …, v_{n}) that preserves the distance between every pair of adjacent vertices, preserves the distance between any pair of vertices. G(v) is flexible if it is not rigid.

Proof of Theorem 33 as given by G. Kalai [Kal84]:

Suppose G is a weakly K_{p}-saturated graph, with G = G_{0} ⊂ G_{1} ⊂ … ⊂ G_{l} = K_{n} such that G_{i} has exactly one more edge than G_{i−1} for 1 ≤ i ≤ l and k_{p}(G_{0}) < k_{p}(G_{1}) < … < k_{p}(G_{l}). We first show that every embedding of G into ℝ^{p−2}, such that the vertices are in general position, is rigid. Suppose that v_{1}, v_{2}, …, v_{n} are n points in general position in ℝ^{p−2}, and consider G(v). Note that G_{l}(v) = K_{n}(v) is rigid. Assume G_{i+1}(v) is rigid, and suppose that G_{i} = G_{i+1}−e, where e = {μ, ν} belongs to a K_{p} of G_{i+1}. Every embedding of K_{p}−e in ℝ^{p−2}, with vertices in general position, is rigid. Thus, any continuous deformation of G_{i}(v) preserves the distance between v_{μ} and v_{ν}, and so is a continuous deformation of G_{i+1}(v). By the assumption the deformation preserves the distances between any two vertices of G_{i}(v). Repeated application of this argument shows that G(v) = G_{0}(v) is rigid.

Now we take advantage of the fact that if G is a graph of order n and fewer than (p − 2)n − \binom{p−1}{2} edges, then G(v) is flexible. □

The second proof [Kal85] introduced the notion of hyperconnectivity in matroids. Kalai defined a matroid H_{k}^{n} on the set of edges of the complete graph on n vertices. A graph G on the same vertex set is k-hyperconnected if the set of its edges span H_{k}^{n}. Kalai showed that the rank of H_{p−2}^{n} equals (p−2)n−\binom{p−1}{2} and that K_{p} corresponds to a circuit in H_{p−2}^{n}. Now, let e be any non-edge in a (weakly) K_{p}-saturated graph G. Since the addition of e yields a copy of K_{p}, the edges of G span e and consequently the entire matroid. That is, G must be (p − 2)-hyperconnected. Thus such a graph has at least (p−2)n−\binom{p−1}{2} edges. The ideas introduced here were later used by O. Pikhurko [Pik01c], see Theorem 35.

In fact, we know even more — that is, we know that equality also holds for the complete k-uniform hypergraph [Lov77], [Fra82], [Kal84], [Kal85], [Alo85].

However, it is not the case that equality always holds! For instance, sat(n, C_{4}) = ⌊\frac{3n−5}{2}⌋ (see Section 3) while w-sat(n, C_{4}) = n (note that for n odd C_{n} is weakly C_{4}- saturated and for n even the graph obtained from C_{n−1} by appending an edge is weakly C_{4}-saturated). It is also interesting to note that while there exists a unique K_{3}-saturated graph of minimum size, this is not the case for weakly K_{3}-saturated graphs. Here, the set of all n-vertex trees comprise W -Sat(n, K_{3}). This pattern repeats itself for many graphs. This gives an indication that, here too, the determination of w-sat(n, F) might be challenging. In addition, Zs. Tuza [Tuz88] points out that the behavior of w-sat(n, F) and sat(n, F) differ significantly if F is relatively sparse.

Question 9. [Tuz88] Are there necessary and/or sufficient conditions for w-sat(n, F) to equal sat(n, F)?

Let H_{k}(p, q) denote the family of all k-uniform hypergraphs with p vertices and q edges. Tuza [Tuz88] conjectured that w-sat(n, H_{k}(k + 1, q)) = \binom{n−k−2+q}{q−2}. (Note that as H_{k}(k + 1, k + 1) consists only of the complete k-uniform hypergraph on k + 1 vertices, this instance of the conjecture is solved by Theorem 33.) As a first step towards this conjecture, Erdős, Füredi, and Tuza [EFT91] gave the following result.

Theorem 34. [EFT91] For n > k ≥ 2, w-sat(n, H_{k}(k + 1, 3)) = n − k + 1.

They left open the problem of determining W -Sat(n, H_{k}(k + 1, 3)), but this was later solved by O. Pikhurko [Pik01b]. In a different paper [Pik01c], Pikhurko made further progress. To state these results we must introduce a new type of graph.

Let sequences k = (k_{1}, …, k_{t}) of nonnegative integers and P_{1}, …, P_{t} of disjoint sets of sizes p = (p_{1}, …, p_{t}) be given. Define [t] = {1, …, t} and, for I ⊆ [t], we write k_{I} in place of ∑_{i∈I} k_{i} and P_{I} in place of ∪_{i∈I}P_{i}; also, we assume k_{0} = 0, P_{0} = ∅, etc. Then the pyramid Δ = Δ(p; k) is the k-graph, k = k_{[t]}, on P = P_{[t]} such that E is an edge of Δ if and only if, for every i ∈ [t], we have |E ∩ S_{[i]}| ≥ r_{[i]}.

Theorem 35. [Pik01c] Suppose we are given two non-empty sequences p = (p_{1}, …, p_{t}) and k = (k_{1}, …, k_{t}) of integers such that p_{i} ≥ k_{i} ≥ 1 for i ∈ [t]. Then

w-sat(n, Δ(p; k)) = ∑_{k′} \binom{n − p_{[t]} + k_{t}}{k′_{t+1}} ∏_{i∈[t]} \binom{p_{i} + k_{i−1} − k_{i}}{k′_{i}}, n ≥ p_{[t]},

where the summation is taken over all sequences of nonnegative integers k′ = (k′_{1}, …, k′_{t+1}) such that k′_{[t+1]} = k_{[t]} and, for some i ∈ [t], k′_{[i]} > k_{[i−1]}.

Now, let us examine the many cases covered by this theorem. First, for t = 1 the graph Δ(p; k) is the k-uniform complete hypergraph on p vertices. Thus, this theorem confirms Bollobás’ conjecture in the case k = 2 and its generalization for k ≥ 3. In the case of k = 2, i.e. graphs, it gives a new result for split graphs (consider Δ(p_{1}, p_{2}; 1, 1). And, Theorem 35 confirms Tuza’s conjecture as the only graph in H_{k}(k + 1, q) is the pyramid graph Δ(k − q + 1, q; k − q + 1, q − 1).

In [Pik01b] Pikhurko gives a construction of an H_{k}(p, q)-saturated graph which he conjectures to be minimum. This conjecture remains open.

10.1 Asymptotics

When exact determination of the function w-sat(n, F) is unknown, we may turn to the following result of Zs. Tuza [Tuz92] for an estimation. Prior to stating the estimation, we must introduce a graph invariant which, as Tuza points, out is a ‘local’ parameter of the graph F. (This is in contrast to the global parameter, the chromatic number, which controls the asymptotic behavior of the extremal number as told to us by the theorem of Erdős-Stone-Simonovits.)

We assume that F is a k-uniform hypergraph with at least two edges. For an edge E ∈ E(F) the sparseness of an edge s(E) is the smallest natural number s for which there is an E^{∗} ⊆ E with |E^{∗}| = s + 1 such that E^{∗} ⊆ E′ ∈ E(F) implies E′ = E (i.e. a set which uniquely determines the edge); if E is a subset of some other edge of F, then we put s(F) := |F |. The local sparseness of the hypergraph F s(F) is the min{s(E) : E ∈ E(F)}. Note that 1 ≤ s(F) ≤ k − 1 for all k-uniform hypergraphs.

Theorem 36. [Tuz92] For every k-uniform hypergraph F, w-sat(n, F) = Θ(n^{s(F)}).

Tuza suggests that this statement might be refined, and thus offers the following.

Conjecture 8. [Tuz92] For some positive constant c = c(F), we have w-sat(n, F) = cn^{s(F)} + O(n^{s(F)−1}).

The results in [Alo85] yield w-sat(n, F) = cn + o(n) in the case of s(F) = 1.

10.2 Other results

When F is the set of all minimal forbidden subgraphs of some hereditary property P, some results for w-sat(n, F) have been obtained. Such hereditary properties include kdegeneracy and bounded maximum degree. For results of this type, we refer the reader to work by G. Semanišin [Sem97], M. Borowiecki and E. Sidorowicz [BS02], and E. Sidorowicz [Sid07].

Acknowledgments

The third author would like to thank Oleg Pikhurko for stimulating discussions and his support and encouragement. We wish to thank the dear reader who sends us new results, corrections, omissions, open problems, conjectures, and the like. Please send these to the third author: jschmitt@middlebury.edu. The authors are indebted to the kind referee whose careful reading of our manuscript helped improve its presentation and clarity. Any remaining errors or shortcomings are the property of the authors.

References

[AEHK96] Noga Alon, Paul Erdős, Ron Holzman, and Michael Krivelevich. On ksaturated graphs with restrictions on the degrees. J. Graph Theory, 23(1):1– 20, 1996.

[Alo85] Noga Alon. An extremal problem for sets with applications to graph theory. J. Combin. Theory Ser. A, 40(1):82–89, 1985.

[Ash05] Yehuda Ashkenazi. C_{3} saturated graphs. Discrete Math., 297(1-3):152–158, 2005.

[BBJF96] Gerhard Benadé, Izak Broere, Betsie Jonck, and Marietjie Frick. Uniquely (m, k)^{τ}-colourable graphs and k-τ-saturated graphs. Discrete Math., 162(1-3):13–22, 1996.

[BCE^{+}96] Curtiss A. Barefoot, Lane H. Clark, Roger C. Entringer, Thomas D. Porter, László A. Székely, and Zsolt Tuza. Cycle-saturated graphs of minimum size. Discrete Math., 150(1-3):31–48, 1996. Selected papers in honour of Paul Erdős on the occasion of his 80th birthday (Keszthely, 1993).

[BCF^{+}95] Curtiss Barefoot, Karen Casey, David Fisher, Kathryn Fraughnaugh, and Frank Harary. Size in maximal triangle-free graphs and minimal graphs of diameter 2. Discrete Math., 138(1-3):93–99, 1995. 14th British Combinatorial Conference (Keele, 1993).

[BDF05] Lowell W. Beineke, J. E. Dunbar, and M. Frick. Detour-saturated graphs. J. Graph Theory, 49(2):116–134, 2005.

[BF] László Babai and Péter Frankl. Linear algebra methods in combinatorics with applications to geometry and computer science. unpublished book manuscript.

[BF02] Darryn E. Bryant and Hung-Lin Fu. C_{4}-saturated bipartite graphs. Discrete Math., 259(1-3):263–268, 2002.

[BFP10] Tom Bohman, Maria Fonoberova, and Oleg Pikhurko. The saturation function of complete partite graphs. J. Comb., 1(2):149–170, 2010.

[BFS07] Frank Bullock, Marietjie Frick, and Joy Singleton. Smallest claw-free, 2connected, nontraceable graphs and the construction of maximal nontraceable graphs. Discrete Math., 307(11-12):1266–1275, 2007.

[BM72] John Adrian Bondy and Uppaluri S. R. Murty. Extremal graphs of diameter two with prescribed minimum degree. Studia Sci. Math. Hungar., 7:239–241, 1972.

[Bol65] Béla Bollobás. On generalized graphs. Acta Math. Acad. Sci. Hungar, 16:447– 452, 1965.

[Bol67a] Béla Bollobás. Determination of extremal graphs by using weights. Wiss. Z. Techn. Hochsch. Ilmenau, 13:419–421, 1967.

[Bol67b] Béla Bollobás. On a conjecture of Erdős, Hajnal and Moon. Amer. Math. Monthly, 74:178–179, 1967.

[Bol68] Béla Bollobás. Weakly k-saturated graphs. In Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967), pages 25–31. Teubner, Leipzig, 1968.

[Bol78] Béla Bollobás. Extremal graph theory, volume 11 of London Mathematical Society Monographs. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1978.

[Bol04] Béla Bollobás. Extremal graph theory. Dover Publications Inc., Mineola, NY, 2004. Reprint of the 1978 original.

[Bon72] John Adrian Bondy. Variations on the Hamiltonian theme. Canad. Math. Bull., 15:57–62, 1972.

[BQZ06] Krystyna T. Balińska, Louis V. Quintas, and Krzysztof T. Zwierzyński. Extremal size in graphs with bounded degree. Ars Combin., 81:235–246, 2006.

[BS02] Mieczysław Borowiecki and Elżbieta Sidorowicz. Weakly P-saturated graphs. Discuss. Math. Graph Theory, 22(1):17–29, 2002. Conference on Graph Theory (Elgersburg, 2000).

[CCES86] Lane H. Clark, Ronni P. Crane, Roger C. Entringer, and Henry D. Shapiro. On smallest maximally non-Hamiltonian graphs. In Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986), volume 53, pages 215–220, 1986.

[CE83a] Lane Clark and Roger Entringer. Smallest maximally non-Hamiltonian graphs. Period. Math. Hungar., 14(1):57–68, 1983.

[CE83b] Lane Clark and Roger Entringer. Smallest maximally non-Hamiltonian graphs. Period. Math. Hungar., 14(1):57–68, 1983.

[CES92] Lane H. Clark, Roger C. Entringer, and Henry D. Shapiro. Smallest maximally non-Hamiltonian graphs. II. Graphs Combin., 8(3):225–231, 1992.

[CFF^{+}] Guantao Chen, Jill R. Faudree, Ralph J. Faudree, Ronald J. Gould, and

Colton Magnant. Saturation numbers for forests. manuscript.

[CFG^{+}] Guantao Chen, Michael J. Ferrara, Ronald J. Gould, Colton Magnant, and John R. Schmitt. Saturation numbers for families of ramsey-minimal graphs. manuscript.

[CFG08] Guantao Chen, Ralph J. Faudree, and Ronald J. Gould. Saturation numbers of books. Electron. J. Combin., 15(1):Research Paper 118, 12, 2008.

[CG08] Sul-young Choi and Puhua Guan. Minimum critical squarefree subgraph of a hypercube. In Proceedings of the Thirty-Ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing, volume 189, pages 57–64, 2008.

[CH79] Louis Caccetta and Roland Häggkvist. On diameter critical graphs. Discrete Math., 28(3):223–229, 1979.

[Che] Ya-Chen Chen. Miinimum K_{2,3}-saturated graphs. submitted.

[Che09] Ya-Chen Chen. Minimum C_{5}-saturated graphs. J. Graph Theory, 61(2):111– 126, 2009.

[Che11] Ya-Chen Chen. All minimum C_{5}-saturated graphs. J. Graph Theory, 67(1):9– 26, 2011.

[CL05] Gary Chartrand and Linda Lesniak. Graphs & digraphs. Chapman & Hall/CRC, Boca Raton, FL, fourth edition, 2005.

[Cox81] Harold S. M. Coxeter. A systematic notation for the Coxeter graph. C. R. Math. Rep. Acad. Sci. Canada, 3(6):329–332, 1981.

[CW98] Yan Chen and Ping Wang. Diameter saturated graphs. In Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1998), volume 131, pages 35–41, 1998.

[DDFL85] Stephen J. Dow, David A. Drake, Zoltán Füredi, and Jean A. Larson. A lower bound for the cardinality of a maximal family of mutually intersecting sets of equal size. In Proceedings of the sixteenth Southeastern international conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1985), volume 48, pages 47–48, 1985.

[DH86] Dwight A. Duffus and Denis Hanson. Minimal k-saturated and color critical graphs of prescribed minimum degree. J. Graph Theory, 10(1):55–67, 1986.

[DH08] Peter Dukes and Lea Howard. Small maximally disjoint union-free families. Discrete Math., 308(18):4272–4275, 2008.

[DKW03] Aneta Dudek, Gyula Y. Katona, and A. Paweł Wojda. m-path cover saturated graphs. In 2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization, volume 13 of Electron. Notes Discrete Math., page 4 pp. (electronic). Elsevier, Amsterdam, 2003.

[DKW06] Aneta Dudek, Gyula Y. Katona, and A. Paweł Wojda. Hamiltonian path saturated graphs with small size. Discrete Appl. Math., 154(9):1372–1379, 2006.

[DPT] Andrzej Dudek, Oleg Pikhurko, and Andrew Thomason. On minimum saturated matrices. submitted.

[DW04a] Aneta Dudek and A. Paweł Wojda. P_{m}-saturated bipartite graphs with minimum size. Discuss. Math. Graph Theory, 24(2):197–211, 2004.

[DW04b] Aneta Dudek and A. Paweł Wojda. P_{m}-saturated graphs with minimum size. Opuscula Math., 24(1):43–55, 2004.

[EFT91] Paul Erdős, Zoltán Füredi, and Zsolt Tuza. Saturated r-uniform hypergraphs. Discrete Math., 98(2):95–104, 1991.

[EG61] Paul Erdős and Tibor Gallai. On the minimal number of vertices representing the edges of a graph. Magyar Tud. Akad. Mat. Kutató Int. Közl., 6:181–203, 1961.

[EH94] Paul Erdős and Ron Holzman. On maximal triangle-free graphs. J. Graph Theory, 18(6):585–594, 1994.

[EHM64] Paul Erdős, András Hajnal, and John W. Moon. A problem in graph theory. Amer. Math. Monthly, 71:1107–1110, 1964.

[EL75] Paul Erdős and László Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, pages 609–627. Colloq. Math. Soc. János Bolyai, Vol. 10. North-Holland, Amsterdam, 1975.

[ES66] Paul Erdős and Miklós Simonovits. A limit theorem in graph theory. Studia Sci. Math. Hungar, 1:51–57, 1966.

[FFGJ09a] Jill Faudree, Ralph J. Faudree, Ronald J. Gould, and Michael S. Jacobson. Saturation numbers for trees. Electron. J. Combin., 16(1):Research Paper 91, 19, 2009.

[FFGJ09b] Ralph Faudree, Michael Ferrara, Ronald Gould, and Michael Jacobson. tK_{p}- saturated graphs of minimum size. Discrete Math., 309(19):5870–5876, 2009.

[FFL95] David C. Fisher, Kathryn Fraughnaugh, and Larry Langley. On C_{5}-saturated graphs with minimum size. In Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995), volume 112, pages 45–48, 1995.

[FFL97] David C. Fisher, Kathryn Fraughnaugh, and Larry Langley. P_{3}-connected graphs of minimum size. Ars Combin., 47:299–306, 1997.

[FG] Ralph J. Faudree and Ronald J. Gould. Saturation numbers for nearly complete graphs. manuscript.

[FHPZ98] Zoltán Füredi, Peter Horak, Chandra M. Pareek, and Xuding Zhu. Minimal oriented graphs of diameter 2. Graphs Combin., 14(4):345–350, 1998.

[FK] Zoltán Füredi and Younjin Kim. Cycle-saturated graphs with minimum number of edges. submitted.

[Fra82] Peter Frankl. An extremal problem for two families of sets. European J. Combin., 3(2):125–127, 1982.

[FS09] Michael J. Ferrara and John R. Schmitt. A general lower bound for potentially H-graphic sequences. SIAM J. Discrete Math., 23(1):517–526, 2008/09.

[FS94] Zoltán Füredi and Ákos Seress. Maximal triangle-free graphs with restrictions on the degrees. J. Graph Theory, 18(1):11–24, 1994.

[FS05] Marietjie Frick and Joy Singleton. Lower bound for the size of maximal nontraceable graphs. Electron. J. Combin., 12:Research Paper 32, 9 pp. (electronic), 2005.

[FS07] Marietjie Frick and Joy Singleton. Cubic maximal nontraceable graphs. Discrete Math., 307(7-8):885–891, 2007.

[FY74] Gary B. Faulkner and Daniel H. Younger. Non-Hamiltonian cubic planar maps. Discrete Math., 7:67–74, 1974.

[GGL95] Ronald L. Graham, Martin Grötschel, and László Lovász, editors. Handbook of combinatorics. Vol. 1, 2. Elsevier Science B.V., Amsterdam, 1995.

[GŁS06] Ronald Gould, Tomasz Łuczak, and John Schmitt. Constructive upper bounds for cycle-saturated graphs of minimum size. Electron. J. Combin., 13(1):Research Paper 29, 19 pp. (electronic), 2006.

[Gou] Ronald J. Gould. Personal communication.

[GS07] Ronald J. Gould and John R. Schmitt. Minimum degree and the minimum size of K_{2}^{t}-saturated graphs. Discrete Math., 307(9-10):1108–1114, 2007.

[Haj65] András Hajnal. A theorem on k-saturated graphs. Canad. J. Math., 17:720– 724, 1965.

[HP85] Frank Harary and Michael Plantholt. Minimum maximal graphs with forbidden subgraphs. Math. Slovaca, 35(1):83–89, 1985.

[HŠ86] Peter Horák and Jozef Širáň. On a construction of Thomassen. Graphs

Combin., 2(4):347–350, 1986.

[HT87] Denis Hanson and Bjarne Toft. Edge-colored saturated graphs. J. Graph Theory, 11(2):191–196, 1987.

[Isa75] Rufus Isaacs. Infinite families of nontrivial trivalent graphs which are not Tait colorable. Amer. Math. Monthly, 82:221–239, 1975.

[JT] Michael Jacobson and Craig Tennenhouse. Oriented graph saturation. manuscript.

[Kal84] Gil Kalai. Weakly saturated graphs are rigid. In Convexity and graph theory (Jerusalem, 1981), volume 87 of North-Holland Math. Stud., pages 189–190. North-Holland, Amsterdam, 1984.

[Kal85] Gil Kalai. Hyperconnectivity of graphs. Graphs Combin., 1(1):65–79, 1985.

[KT86] László Kászonyi and Zsolt Tuza. Saturated graphs with minimal number of edges. J. Graph Theory, 10(2):203–210, 1986.

[LJZY97] Xiaohui Lin, Wenzhou Jiang, Chengxue Zhang, and Yuansheng Yang. On smallest maximally non-Hamiltonian graphs. Ars Combin., 45:263–270, 1997.

[Lov77] László Lovász. Flats in matroids and geometric graphs. In Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977), pages 45–86. Academic Press, London, 1977.

[Łuc] Tomasz Łuczak. Personal communication.

[Mad73] Wolfgang Mader. 1-faktoren in graphen. Math. Ann., 201:269–282, 1973.

[Mey74] Jean-Claude Meyer. Quelques problèmes concernant les cliques des hypergraphes h-complets et q-parti h-complets. In Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross), pages 127–139. Lecture Notes in Math., Vol. 411. Springer, Berlin, 1974.

[Nel03] Donald A. Nelson. The structure of saturated critical blocks. J. Graph Theory, 43(3):223–237, 2003.

[Oll72] L. Taylor Ollmann. K_{2,2} saturated graphs with a minimal number of edges. In Proceedings of the Third Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1972), pages 367–392, Boca Raton, Fla., 1972. Florida Atlantic Univ.

[Pik99a] Oleg Pikhurko. Extremal hypergraphs. Ph.D Thesis, Cambridge University, 1999.

[Pik99b] Oleg Pikhurko. The minimum size of saturated hypergraphs. Combin. Probab. Comput., 8(5):483–492, 1999.

[Pik00] Oleg Pikhurko. Asymptotic evaluation of the sat-function for r-stars. Discrete Math., 214(1-3):275–278, 2000.

[Pik01a] Oleg Pikhurko. Constructing designs straightforwardly: worst arising cases. J. Combin. Des., 9(2):100–106, 2001.

[Pik01b] Oleg Pikhurko. Uniform families and count matroids. Graphs Combin., 17(4):729–740, 2001.

[Pik01c] Oleg Pikhurko. Weakly saturated hypergraphs and exterior algebra. Combin. Probab. Comput., 10(5):435–451, 2001.

[Pik04] Oleg Pikhurko. Results and open problems on minimum saturated hypergraphs. Ars Combin., 72:111–127, 2004.

[PS08] Oleg Pikhurko and John R. Schmitt. A note on minimum K_{2,3}-saturated graphs. Australasian J. Combin., 40:211–215, 2008.

[Sem97] Gabriel Semanišin. On some variations of extremal graph problems. Discuss. Math. Graph Theory, 17(1):67–76, 1997.

[Sid07] Elżbieta Sidorowicz. Size of weakly saturated graphs. Discrete Math., 307(11-12):1486–1492, 2007.

[Sta96] Ladislav Stacho. Maximally non-Hamiltonian graphs of girth 7. Graphs Combin., 12(4):361–371, 1996.

[Sta98] Ladislav Stacho. Non-isomorphic smallest maximally non-Hamiltonian graphs. Ars Combin., 48:307–317, 1998.

[Tho74] Carsten Thomassen. Hypohamiltonian and hypotraceable graphs. Discrete Math., 9:91–96, 1974.

[TT91] Mirosław Truszczyński and Zsolt Tuza. Asymptotic results on saturated graphs. Discrete Math., 87(3):309–314, 1991.

[Tur41] Paul Turán. Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok, 48:436–452, 1941.

[Tut60] William T. Tutte. A non-Hamiltonian graph. Canad. Math. Bull., 3:1–5, 1960.

[Tuz86] Zsolt Tuza. A generalization of saturated graphs for finite languages. Tanulmányok—MTA Számitástech. Automat. Kutató Int. Budapest, (185):287–293, 1986.

[Tuz88] Zsolt Tuza. Extremal problems on saturated graphs and hypergraphs. Ars Combin., 25(B):105–113, 1988. Eleventh British Combinatorial Conference (London, 1987).

[Tuz89] Zsolt Tuza. C_{4}-saturated graphs of minimum size. Acta Univ. Carolin. Math. Phys., 30(2):161–167, 1989. 17th Winter School on Abstract Analysis (Srní, 1989).

[Tuz92] Zsolt Tuza. Asymptotic growth of sparse saturated structures is locally determined. Discrete Math., 108(1-3):397–402, 1992. Topological, algebraical and combinatorial structures. Frolík’s memorial volume.

[Tuz94] Zs. Tuza. Applications of the set-pair method in extremal hypergraph theory. In Extremal problems for finite sets (Visegrád, 1991), volume 3 of Bolyai Soc. Math. Stud., pages 479–514. János Bolyai Math. Soc., Budapest, 1994.

[Tuz96] Zs. Tuza. Applications of the set-pair method in extremal problems. II. In Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), volume 2 of Bolyai Soc. Math. Stud., pages 459–490. János Bolyai Math. Soc., Budapest, 1996.

[vAFDO09] Susan A. van Aardt, Marietjie Frick, Jean E. Dunbar, and Ortrud Oellermann. Detour saturated oriented graphs. Util. Math., 79:167–180, 2009.

[Wes66] Walter A. Wessel. Über eine klasse paarer graphen, i: Beweis einer vermutung von Erdös, Hajnal, und Moon. Wiss. Z. Tech. Hochsch. Ilmenau, 12:253–256, 1966.

[Wes67] Walter Wessel. Über eine Klasse paarer Graphen. II. Bestimmung der Minimalgraphen. Wiss. Z. Techn. Hochsch. Ilmenau, 13:423–426, 1967.

[Yu93] Jie Tai Yu. An extremal problem for sets: a new approach via Bezoutians. J. Combin. Theory Ser. A, 62(1):170–175, 1993.

[Zel98] Bohdan Zelinka. Graphs maximal with respect to absence of Hamiltonian paths. Discuss. Math. Graph Theory, 18(2):205–208, 1998.