F-saturated k-graphs (1986)

Originator: Zsolt Tuza, Duffus&Hanson    (presented by Oleg Pikhurko - REGS 2010)

Definitions: A k-graph is a k-uniform hypergraph; 2-uniform hypergraphs are ordinary graphs. A k-graph G is F-saturated if G does not contain F as a subgraph but the addition of any missing edge to G violates this property. Let sat(n,F) be the minimum size of an F-saturated k-graph with n vertices. It is known that sat(n,F)=O(n^k-1) (as shown by Kaszonyi and Tuza (1986) when k=2 and by Pikhurko (1999) when k>2). The reader is referred to the survey [FFS] for more details.

Conjecture 1 (Tuza [T1]): For every graph F the ratio sat(n,F)/n tends to a limit as n tends to infinity.

Comments: This conjecture is false if one allows families of forbidden k-graphs instead of just a single k-graph, even when k=2. An example found by Kostochka and Pikhurko is the family consisting of (1) two copies of K₄ with one edge joining them, (2) two copies of K₄ sharing one vertex, and (3) K₂∨(K₂+K₁) (this contains K₄ plus a vertex of degree 2).

Conjecture 2 (Tuza [T2]): If a 3-graph has an edge D such that no other edge of F intersects D in more than one vertex, then sat(n,F)=O(n).

Comments: Tuza made a more general conjecture; this is the first open case. If the assumption on F is false, then sat(n,F)-function grows as Ω(n²). Also, it is easy to show that if F has an isolated edge, then sat(n,F)=O(1); otherwise sat(n,F)=Ω(n). Thus if the conjecture is true, then the order of growth of sat(n,F) for a 3-graph F is always a multiple of nⁱ with i∈{0,1,2}, which would be a very nice result.

We mention one saturation problem for ordinary graphs. Let sat(n,F,d) be the minimum size of a saturated graph on n vertices that has minimum degree at least d. Trivially, sat(n,K₃,1)=n-1 and sat(n,K₃,d)≤d(n-d) (just consider the complete bipartite graph K_d,n-d). Duffus & Hanson [DH] showed that sat(n,K₃,2)=2n-5 for n≥5 and sat(n,K₃,3)=3n-15 for n≥10. Alon, Erdos, Holzman and Krivelevich [AEHK] showed that sat(n,K₃,3)=dn+o(n) for each fixed d.

Question 3 (Bollobas, 1995): Is it true for every fixed integer d that sat(n,K₃,d)=dn+O(1)?

References:
[AEHK] Alon, Noga; Erdős, Paul; Holzman, Ron; Krivelevich, Michael: On k-saturated graphs with restrictions on the degrees. J. Graph Theory 23 (1996), no. 1, 1-20.
[DH] Duffus, D. A.; Hanson, D.; Minimal $k$-saturated and color critical graphs of prescribed minimum degree. J. Graph Theory 10 (1986), no. 1, 55-67.
[FFS] Jill Faudree, Ralph Faudree and John Schmitt, A Survey of Minimum Saturated Graphs and Hypergraphs. Available from John Schmitt's webpage.
[T1] Zs. Tuza, Extremal problems on saturated graphs and hypergraphs, Ars Combinatoria 25B (1988), 105-113.
[T2] Zs. Tuza, Asymptotic growth of sparse saturated structures is locally determined, Discrete Math. 108 (1992), 397-402.