\UseRawInputEncoding

Saturation Numbers for Berge Cliques

Sean English Dept. of Mathematics and Statistics, University of North Carolina Wilmington ([email protected]) Jürgen Kritschgau Dept. of Mathematics, Carnegie Mellon University ([email protected]). Research is supported by NSF grant DMS-1839918. Mina Nahvi Dept. of Mathematics, University of Illinois Urbana-Champaign ([email protected]) Elizabeth Sprangel Dept. of Mathematics, Iowa State University ([email protected])

Abstract

Let $F$ be a graph and $\mathcal{H}$ be a hypergraph, both embedded on the same vertex set. We say $\mathcal{H}$ is a Berge- $F$ if there exists a bijection $\phi:E(F)\to E(\mathcal{H})$ such that $e\subseteq\phi(e)$ for all $e\in E(F)$ . We say $\mathcal{H}$ is Berge- $F$ -saturated if $\mathcal{H}$ does not contain any Berge- $F$ , but adding any missing edge to $\mathcal{H}$ creates a copy of a Berge- $F$ . The saturation number $\mathrm{sat}_{k}(n,\text{Berge-}F)$ is the least number of edges in a Berge- $F$ -saturated $k$ -uniform hypergraph on $n$ vertices. We show

\mathrm{sat}_{k}(n,\text{Berge-}K_{\ell})\sim\frac{\ell-2}{k-1}n,

for all $k,\ell\geq 3$ . Furthermore, we provide some sufficient conditions to imply that $\mathrm{sat}_{k}(n,\text{Berge-}F)=O(n)$ for general graphs $F$ .

1 Introduction

Extremal graph theory is concerned with maximizing or minimizing some parameter over a restricted class of graphs. Let $\mathcal{G}$ and $\mathcal{F}$ be $k$ -uniform hypergraphs. We say that $\mathcal{G}$ is $\mathcal{F}$ -saturated if $\mathcal{G}$ does not contain a copy of $\mathcal{F}$ but $\mathcal{G}+e$ does for any $e\in E(\overline{\mathcal{G}})$ . The most well-studied problem in extremal graph theory is the Turán problem, which asks for the maximum number of edges in a $\mathcal{F}$ -free hypergraph $\mathcal{G}$ on $n$ vertices. This maximum is known as the extremal number or Turán number of $\mathcal{F}$ , and is denoted $\mathrm{ex}_{k}(n,\mathcal{F})$ . Any $\mathcal{F}$ -free hypergraph $\mathcal{G}$ with $\mathrm{ex}_{k}(|V(\mathcal{G})|,\mathcal{F})$ edges must necessarily be $\mathcal{F}$ -saturated, so we can write

\mathrm{ex}_{k}(n,\mathcal{F})=\max\{|E(\mathcal{G})|:|V(\mathcal{G})|=n,\mathcal{G}\text{ is }\mathcal{F}\text{-saturated}\}.

On the flipside, the saturation number of $\mathcal{F}$ , denoted $\mathrm{sat}_{k}(n,\mathcal{F})$ , is the least number of edges in a $\mathcal{F}$ -saturated graph on $n$ vertices, or

\mathrm{sat}_{k}(n,\mathcal{F})=\min\{|E(\mathcal{G})|:|V(\mathcal{G})|=n,\mathcal{G}\text{ is }\mathcal{F}\text{-saturated}\}.

Saturation was first introduced by Erdős, Hajnal and Moon [7] for graphs, and then generalized for hypergraphs by Bollobás [3] who showed that

\mathrm{sat}_{k}(n,\mathcal{K}^{(k)}_{\ell})=\binom{n}{k}-\binom{n-\ell+k}{k},

(1)

where $\mathcal{K}^{(k)}_{\ell}$ denotes the complete $k$ -uniform hypergraph on $\ell$ vertices. Since these seminal results, much work has been done on the saturation function and many generalizations have been studied. For a dynamic survey on saturation numbers, see [4].

In this work, we are interested in the saturation function for Berge hypergraphs, which are a generalization of Berge paths and Berge cycles introduced by Gerbner and Palmer [8]. Given a graph $F$ and a hypergraph $\mathcal{H}$ embedded on the same vertex set, we say that $\mathcal{H}$ is a Berge- $F$ if there is a way to embed $F$ and $\mathcal{H}$ on the same vertex set such that there exists a bijection $\phi:E(F)\to E(\mathcal{H})$ that has $e\subseteq\phi(e)$ for all $e\in E(F)$ . We note that many non-isomorphic hypergraphs may be a Berge- $F$ and a hypergraph may be a Berge copy of many non-isomorphic graphs. We will write $\mathrm{sat}_{k}(n,\text{Berge-}F)$ for the least number of edges in a Berge- $F$ -saturated $k$ -uniform hypergraph on $n$ vertices.

Saturation numbers for Berge hypergraphs were first studied by the first author and others in [6], where some results on the saturation function for Berge paths, matchings, cycles, and cliques are given. Since the seminal work on saturation for Berge hypergraphs, the topic has gotten significant attention (see [1, 2, 9, 11] for some of the results on the topic). Prior to this work, the following result was the only known result on saturation for Berge cliques.

Theorem 1.1 ([6]).

For all $k\geq 3$ and $n\geq k+1$ ,

\mathrm{sat}_{k}(n,\text{Berge-}K_{3})=\left\lceil\frac{n-1}{k-1}\right\rceil.

Our main theorem determines the asymptotics of Berge- $K_{\ell}$ for all fixed clique sizes $\ell$ and uniformities $k$ .

Theorem 1.2.

For $\ell\geq 3$ and $k\geq 3$ ,

\mathrm{sat}_{k}(n,\text{Berge-}K_{\ell})\sim\frac{\ell-2}{k-1}n.

The case $\ell=3$ is covered by Theorem 1.1. When $\ell\geq 4$ , the lower bound in Theorem 1.2 follows from Theorem 2.1, while the upper bound follows from Theorem 3.9.

In addition to the main result, we also study the linearity of Berge saturation for general graphs. For ( $2$ -uniform) graphs $F$ , Kászonyi and Tuza [10] showed that $\mathrm{sat}_{2}(n,F)=O(n)$ , while Pikhurko [12] showed that $\mathrm{sat}_{k}(n,\mathcal{F})=O(n^{k-1})$ for $k$ -uniform hypergraphs $\mathcal{F}$ , and this result is best-possible, as seen for example in equation (1) stating the result from [3]. In [6] it was conjectured that $\mathrm{sat}_{k}(n,\text{Berge-}F)=O(n)$ , suggesting that the saturation function for Berge hypergraphs should grow more like graph saturation than $k$ -uniform hypergraph saturation. This conjecture was confirmed for uniformities $3\leq k\leq 5$ in [5], but is still open in general.

We prove two results which show that many graphs have Berge saturation numbers which grow at most linearly. The first theorem deals with graphs with large minimum degree.

Theorem 1.3.

If $\delta(F)>\frac{|V(F)|-\alpha(F)}{2}$ and $k\geq 3$ , then

\mathrm{sat}_{k}(n,\text{Berge-}F)=O(n).

Our final result concerns graphs with large girth. Recall that the girth of a graph is the length of the shortest cycle (which we will denote by $g(G)$ ), and the vertex feedback number is the least number of vertices necessary to delete which leaves an acyclic graph (which we will denote by $f(G)$ ).

Theorem 1.4.

Let $F$ be a graph with girth $g$ and vertex feedback number $f$ . If $g>f$ and $k\geq 3$ , then

\mathrm{sat}_{k}(n,\text{Berge-$F$})=O(n).

1.1 Definitions and organization

Let $F$ be a graph and $\mathcal{H}$ be a $k$ -uniform Berge- $F$ embedded on the same vertex set, and let $\phi:E(F)\to E(\mathcal{H})$ be a bijection such that $e\subseteq\phi(e)$ for all $e\in E(F)$ . We call $\phi$ the Berge edge map. When $F$ and $\mathcal{H}$ are embedded in such a way that there exists a Berge edge map, we say that $F$ is a Berge- $F$ witness. When $F$ is a Berge- $F$ witness for $\mathcal{H}$ , the vertices in $V(F)$ are called core vertices of the Berge- $F$ hypergraph $\mathcal{H}$ . Given a hypergraph $\mathcal{H}$ and a set $e\subseteq 2^{V(\mathcal{H})}$ such that $e\notin E(\mathcal{H})$ , we say $\mathcal{H}+e$ contains a new Berge- $F$ if $\,H+e$ contains a Berge- $F$ that uses $e$ .

Uniform hypergraphs are of primary concern in this paper, but in order to simplify proofs, we find it useful to occasionally deal with non-uniform hypergraphs, usually a hypergraph where all but one edge has $k$ vertices, and the one other edge has $2$ vertices. We note that the definition of a Berge- $F$ does not depend on $\mathcal{H}$ being uniform. In particular, we will say a pair $uv\subseteq V(\mathcal{H})$ is $\ell$ -good if $\mathcal{H}+uv$ contains a new Berge- $K_{\ell}$ . Since we occasionally speak of non-uniform hypergraphs, we note here that if we refer to the complement $\overline{\mathcal{H}}$ of a $k$ -uniform hypergraph, this is assumed to be the $k$ -uniform complement.

In a $k$ -uniform hypergraph $\mathcal{H}$ , a loose path of length $2$ is a pair of edges that intersect in exactly one vertex. The single vertex of degree $2$ in the loose path of length $2$ will be called a hinge vertex. Given two vertices $u,v\in V(\mathcal{H})$ , we will write $v\preceq u$ if $\{e\in E(\mathcal{H})\mid v\in e\}\subseteq\{e\in E(\mathcal{H})\mid u\in e\}$ . We note that $\preceq$ is reflexive and transitive, but in general $\preceq$ may not be a partial order as it may not be anti-symmetric.

We note that if $F$ is a non-empty graph with isolated vertices and $F^{\prime}$ is the subgraph of $F$ induced by $E(F)$ , then for all $n$ large enough, $\mathrm{sat}_{k}(n,\text{Berge-}F)=\mathrm{sat}_{k}(n,\text{Berge-}F^{\prime})$ , so throughout the paper we will silently assume that no graphs have isolated vertices. All asymptotics are with respect to $n\to\infty$ , with all other parameters assumed to be constant unless specifically stated otherwise. All logarithms written as $\log n$ are in base $2$ . The complete join of two $2$ -graphs, $F$ and $G$ , denoted $F\vee G$ , is the graph whose vertex set is the disjoint union $V(F\vee G)=V(F)\cup V(G)$ , and the edge set

E(F\vee E)=E(F)\cup E(G)\cup\{xy\mid x\in V(F),y\in V(G)\}.

The rest of the paper is organized as follows. In Sections 2 and 3, we prove the lower bound and upper bound for Theorem 1.2, respectively. In Section 4, we prove Theorems 1.3 and 1.4. Finally, in Section 5, we briefly discuss the open problem of determining the exact values for the saturation numbers for Berge- $K_{4}$ .

2 Lower bound for Berge- $K_{\ell}$ saturation

We present here an asymptotic lower bound for $\mathrm{sat}_{k}(n,\text{Berge-}K_{\ell})$ . Fortunately, the same argument works for all $k\geq 2$ and $\ell\geq 3$ .

Theorem 2.1.

For any $k\geq 2$ and $\ell\geq 3$ ,

\mathrm{sat}_{k}(n,\text{Berge-}K_{\ell})\geq(1+o(1))\frac{\ell-2}{k-1}n.

Proof.

Let $\mathcal{H}$ be a $k$ -uniform Berge- $K_{\ell}$ -saturated hypergraph. Partition the vertex set $V(\mathcal{H})=X\cup A\cup B$ , where

X=\{v\in V(\mathcal{H})\mid d(v)\geq\log^{2}n\},

$A\subseteq V(\mathcal{H})\setminus X$ such that $v\in A$ if and only if $v$ is contained in at least $\ell-2$ edges that intersect $X$ , and $B=V(\mathcal{H})\setminus(X\cup A)$ . Note that if $|X|>n/\log n$ , then by counting degrees, $|E(\mathcal{H})|>\frac{|X|\log^{2}n}{k}=\omega(n)\geq(1+o(1))\frac{\ell-2}{k-1}n$ , so we are done unless $|X|\leq n/\log n=o(n)$ .

We will show that $|B|=o(n)$ as well. Indeed, first note that every non-edge $f\subseteq B$ contains a pair $u,v\in f$ that is connected by $\ell-2$ Berge paths of length $2$ since adding $f$ to $\mathcal{H}$ creates a Berge- $K_{\ell}$ . Since $u\not\in A$ , at least one of these Berge paths must contain a hinge vertex in $A\cup B$ . Each vertex $a\in A\cup B$ can play the role of this hinge vertex for at most $\binom{d(a)}{2}(k-1)^{2}\binom{|B|}{k-2}$ size $k$ non-edges $f\subseteq B$ since we can choose two edges in the Berge path of length $2$ in $\binom{d(a)}{2}$ and then the vertices $u$ and $v$ in at most $(k-1)$ ways each, and finally the remaining $k-2$ vertices in $f$ in $\binom{|B|}{k-2}$ ways. So, if $p$ is the total number of $k$ -sets $f\subseteq B$ that are not edges of $\mathcal{H}$ , then

p\leq\sum_{a\in A\cup B}\binom{d(a)}{2}(k-1)^{2}\binom{|B|}{k-2}\leq k^{2}\binom{|B|}{k-2}\sum_{a\in A\cup B}\binom{\log^{2}n}{2}\leq k^{2}\binom{|B|}{k-2}\frac{n\log^{4}n}{2}.

(2)

On the other hand, since every vertex $b\in B$ has degree less than $\log^{2}n$ , by a degree count, $B$ contains at most $\frac{|B|\log^{2}n}{k}$ edges, and thus

\binom{|B|}{k}-\frac{|B|\log^{2}n}{k}\leq p.

(3)

If $|B|\geq n/\log n$ , then the left side of (3) is greater than $\frac{1}{2}\binom{|B|}{k}$ . Comparing this to the right side of (2) with some rearranging, we get that

\frac{(|B|-k+2)(|B|-k+1)}{k^{3}(k-1)}\leq n\log^{4}n,

which is a contradiction for $|B|\geq n/\log n$ . Thus, $|B|=o(n)$ as claimed.

Thus, since $|X|,|B|=o(n)$ , we must have $|A|=(1+o(1))n$ . Now, let us count the number of edges of $\mathcal{H}$ that contain at least one vertex in $A$ and at least one vertex in $X$ . Each such edge contains at most $k-1$ vertices in $A$ , and each vertex in $A$ is in at least $\ell-2$ such edges by definition of $A$ , so the total number of edges containing at least one vertex from $X$ and at least one from $A$ is at least

\frac{\ell-2}{k-1}|A|\leq|E(\mathcal{H})|.

Since $|A|=(1+o(1))n$ , the theorem holds. ∎

3 Upper bound

In this section, we provide Berge- $K_{\ell}$ -saturated constructions for all uniformities $k\geq 3$ and all clique sizes $\ell\geq 4$ . The work is divided into three subsections. In Section 3.1, we state and prove a few simple observations which will be useful in the later sections. In Section 3.2, we construct specific small $k$ -uniform Berge- $K_{\ell}$ -saturated hypergraphs which also have the properties that every pair is $\ell$ -good, and that every set of $\ell-1$ vertices contains a Berge clique. Due to some technical constraints when $\ell=4$ , we provide one construction for $\ell=4$ and one for $\ell\geq 5$ . In Section 3.3, we use the small hypergraphs constructed in Section 3.2 to find a Berge- $K_{\ell}$ saturated hypergraph with few edges on $n$ vertices for all large $n$ .

3.1 Upper bound tools

We present here two simple observations which will help show that our constructions are Berge- $K_{\ell}$ -saturated.

Observation 3.1.

Let $\mathcal{H}$ be a hypergraph and let $u,v\in V(\mathcal{H})$ be such that $v\preceq u$ . Let $e\in 2^{V(\mathcal{H})}$ be such that $v\in e$ . Let

e^{\prime}=\begin{cases}e&\text{ if }u\in e,\\ (e\setminus\{v\})\cup\{u\}&\text{ if }u\not\in e.\end{cases}

For any graph $F$ , if $\mathcal{H}+e$ contains a new Berge- $F$ in which $u$ is not core, then $\mathcal{H}+e^{\prime}$ contains a new Berge- $F$ . Furthermore, there is a new Berge- $F$ in $\mathcal{H}+e$ and a new Berge- $F$ in $\mathcal{H}+e^{\prime}$ such that the two Berge- $F$ ’s have the same core vertices except possibly with $u$ as a core vertex instead of $v$ .

Proof.

Assume $H+e$ contains a Berge- $F$ , call it $\mathcal{F}$ , that uses the edge $e$ and in which $u$ is not core. If $v$ is not core in $\mathcal{F}$ , then $(\mathcal{F}-e)+e^{\prime}$ is a Berge- $F$ with the same witness as $\mathcal{F}$ . If $v$ is core, then since every edge containing $v$ also contains $u$ , $(\mathcal{F}-e)+e^{\prime}$ is a Berge- $F$ with the same core vertices as $\mathcal{F}$ , except with $u$ in place of $v$ . ∎

Observation 3.2.

Let $\mathcal{H}$ be a hypergraph and let $u,v\in V(H)$ be such that $v\preceq u$ . If $\mathcal{H}$ contains a Berge- $F$ whose core vertices include $v$ and not $u$ , then $\mathcal{H}$ also contains a Berge- $F$ with the same core vertices, except with $u$ in place of $v$ .

Proof.

This follows immediately from the fact that every edge that contains $v$ also contains $u$ . ∎

3.2 Small hypergraphs saturated with respect to pairs

Our first construction is for a small hypergraph that is Berge- $K_{4}$ -saturated with some nice extra properties.

Construction 3.3.

Fix $k\geq 3$ . Let $D=\{d_{1},d_{2},\dots,d_{k-3}\}$ (when $k=3$ we allow $D=\emptyset$ ) and $C=\{c_{1},c_{2},c_{3},c_{4},c_{5}\}$ be disjoint sets of vertices. Let $\mathcal{C}(k,4)$ be the $k$ -uniform hypergraph with $V(\mathcal{C}(k,4))=C\cup D$ , and

E(\mathcal{C}(k,4))=\{\{c_{i},c_{i+1},c_{i+2}\}\cup D\mid i\in[5]\},

where the indices $i$ are taken modulo $5$ .

It is worth noting that $\mathcal{C}(3,4)$ is the $3$ -uniform tight cycle on $5$ vertices. We now show that $\mathcal{C}(k,4)$ has the property that every pair is $4$ -good and every three vertices form a Berge clique. It is also easy to see that $\mathcal{C}(k,4)$ is Berge- $K_{4}$ -saturated, but we do not explicitly prove this until Section 3.3.

Lemma 3.4.

Let $k\geq 3$ and let $\mathcal{C}:=\mathcal{C}(k,4)$ . Then

1.

Every pair in $V(\mathcal{C})$ is $4$ -good, and
2.

Every set of three vertices in $V(\mathcal{C})$ are the core vertices of a Berge- $K_{3}$ .

Proof.

First, we prove (1). Let $xy\subseteq V(\mathcal{C})$ . First, let us consider the case where $xy=c_{i}c_{j}$ for some $i,j\in[5]$ . We may assume without loss of generality that $j\in\{i+1,i+2\}$ (modulo $5$ ). In either case, $\mathcal{C}+c_{i}c_{j}$ contains a Berge- $K_{4}$ with core vertices $c_{i-1},c_{i},c_{i+1}$ and $c_{i+2}$ with Berge edge map

	$\displaystyle c_{i-1}c_{i}$	$\displaystyle\mapsto c_{i-2}c_{i-1}c_{i}\cup D,$
	$\displaystyle c_{i-1}c_{i+1}$	$\displaystyle\mapsto c_{i-1}c_{i}c_{i+1}\cup D,$
	$\displaystyle c_{i-1}c_{i+2}$	$\displaystyle\mapsto c_{i+2}c_{i+3}c_{i-1}\cup D$
	$\displaystyle c_{i+1}c_{i+2}$	$\displaystyle\mapsto c_{i+1}c_{i+2}c_{i-2}\cup D,$
	$\displaystyle c_{i}c_{i+1}$	$\displaystyle\mapsto\begin{cases}c_{i}c_{i+1}&\text{ if }j=i+1,\\ c_{i}c_{i+1}c_{i+2}\cup D&\text{ if }j=i+2,\end{cases}$
	$\displaystyle c_{i}c_{i+2}$	$\displaystyle\mapsto\begin{cases}c_{i}c_{i+1}c_{i+2}\cup D&\text{ if }j=i+1,\\ c_{i}c_{i+2}&\text{ if }j=i+2.\\ \end{cases}$

Now, if exactly one of $x$ or $y$ is in $D$ , say $x\in D$ , $y=c_{i}$ , then note that $c_{i+1}\preceq x$ , so by Observation 3.1, since $\mathcal{C}+c_{i}c_{i+1}$ contains a Berge- $K_{4}$ with core vertices $c_{i-1},c_{i},c_{i+1}$ and $c_{i+2}$ , $H+xy$ contains a Berge- $K_{4}$ as well.

Finally, if both $x,y\in D$ , then we note that $c_{1}\preceq x$ and $c_{2}\preceq y$ , so applying Observation 3.1 twice, we first note that since $\mathcal{C}+c_{1}c_{2}$ contains a Berge- $K_{4}$ with core vertices $c_{5}$ , $c_{1}$ , $c_{2}$ and $c_{3}$ , $\mathcal{C}+c_{1}y$ contains a Berge- $K_{4}$ with core vertices $c_{5}$ , $c_{1}$ , $y$ and $c_{3}$ , and then $\mathcal{C}+xy$ contains a Berge- $K_{4}$ .

Now let us focus on (2). Let $xyz\subseteq V(\mathcal{C})$ . First, we will consider the case when $xyz\subseteq C$ . Due to symmetry, we may assume that $xyz=c_{1}c_{2}c_{3}$ or $xyz=c_{1}c_{2}c_{4}$ . If $xyz=c_{1}c_{2}c_{3}$ , then

	$\displaystyle c_{1}c_{2}$	$\displaystyle\mapsto c_{5}c_{1}c_{2},$
	$\displaystyle c_{1}c_{3}$	$\displaystyle\mapsto c_{1}c_{2}c_{3},$
	$\displaystyle c_{2}c_{3}$	$\displaystyle\mapsto c_{2}c_{3}c_{4},$

is a Berge edge map for a Berge- $K_{3}$ with core vertices $x,y,z$ . If $xyz=c_{1}c_{2}c_{4}$ , then

	$\displaystyle c_{1}c_{2}$	$\displaystyle\mapsto c_{5}c_{1}c_{2},$
	$\displaystyle c_{1}c_{4}$	$\displaystyle\mapsto c_{4}c_{5}c_{1},$
	$\displaystyle c_{2}c_{4}$	$\displaystyle\mapsto c_{2}c_{3}c_{4},$

again gives us a Berge- $K_{3}$ .

If $xyz\not\subseteq C$ , since $c_{i}\preceq d_{j}$ for all $i\in[5]$ , $j\in[k-3]$ , by repeated application of Observation 3.2, starting with any triple contained in $C$ (that also contains any elements of $xyz$ that are in $C$ ), we can replace vertices in $C$ with the vertices of $xyz$ that are in $D$ , each step retaining the property that the triple is the core of a Berge- $K_{3}$ , resulting in a Berge- $K_{3}$ with core vertices $xyz$ . ∎

The following construction and lemma are analogous to Construction 3.3 and Lemma 3.4, but for the case $\ell\geq 5$ .

Construction 3.5.

Fix $k\geq 3$ , $\ell\geq 5$ . Let $D=\{d_{1},d_{2},\dots,d_{k-3}\}$ and $C=\{c_{1},c_{2},c_{3},\dots,c_{\ell}\}$ . Start with a copy of the ( $2$ -uniform) graph $K:=K_{\ell}-c_{1}c_{2}$ on the vertex set $C$ , and extend the edges of $K$ to $k$ -uniform hyperedges in the following way. Let $e\in E(K)$ .

1.

If $c_{1}\in e,c_{2}\notin e$ , then extend $e$ to $e\cup\{c_{2}\}\cup D$ .
2.

If $e=\{c_{2},c_{3}\}$ , then extend $e$ to $e\cup\{c_{4}\}\cup D$ .
3.

If $e=\{c_{2},c_{4}\}$ , then extend $e$ to $e\cup\{c_{5}\}\cup D$ .
4.

If $c_{1}\notin e,c_{2}\in e$ , and $c_{3},c_{4}\notin e$ , then extend $e$ to $e\cup\{c_{3}\}\cup D$ .
5.

If $c_{1},c_{2}\notin e$ , then extend $e$ to $e\cup\{c_{1}\}\cup D$ .

Let $\mathcal{C}(k,\ell)$ be the resulting $k$ -uniform hypergraph.

Lemma 3.6.

Let $k\geq 3$ , $\ell\geq 5$ and let $\mathcal{C}:=\mathcal{C}(k,\ell)$ . Then

1.

Every pair in $V(\mathcal{C})$ is $\ell$ -good, and
2.

Every set of $\ell-1$ vertices in $V(\mathcal{C})$ are the core vertices of a Berge- $K_{\ell-1}$ .

Proof.

Let $K$ , $C$ and $D$ be defined as in Construction 3.5. Notice that the extension of the edges in $E(K)$ to edges in $E(\mathcal{C})$ gives a bijection $\phi:E(\mathcal{C})\to E(K)$ . In order to show that every pair $xy$ in $\mathcal{C}$ is $\ell$ -good, we show that there is a modification of $\phi$ that witnesses a Berge- $K_{\ell}$ using the edge $xy$ .

Case 1: $xy\subseteq C$ . Let $K^{*}$ be the copy of $K_{\ell}$ with vertex set $C$ . In this case, we will show that $K^{*}$ is a witness to a Berge- $K_{\ell}$ in $\mathcal{C}+xy$ . Notice that if $xy=c_{1}c_{2}$ , then $\phi$ in addition to $xy\mapsto c_{1}c_{2}$ gives a Berge- $K_{\ell}$ .

Case 1.1: $c_{1}\in xy$ , $c_{2}\not\in xy$ , say $x=c_{1}$ . Then by Construction 3.5 (1), $\phi^{-1}(xy)=c_{1}yc_{2}\cup D$ , so we let $\phi_{xy}:E(\mathcal{C})\cup\{xy\}\to E(K^{*})$ be given by

\phi_{xy}(e)=\begin{cases}xy=c_{1}y&\text{if }e=xy,\\ c_{1}c_{2}&\text{if }e=c_{1}c_{2}y\cup D,\\ \phi(e)&\text{otherwise}.\end{cases}.

Case 1.2: $c_{2}c_{3}=xy$ , say $c_{2}=x$ and $c_{3}=y$ . We have that $\phi^{-1}(xy)=c_{2}c_{3}c_{4}\cup D$ , while $\phi^{-1}(c_{3}c_{4})=c_{1}c_{3}c_{4}\cup D$ , and finally $\phi^{-1}(c_{1}c_{3})=c_{1}c_{2}c_{3}\cup D$ . Thus, we let $\phi_{xy}:E(\mathcal{C})\cup\{xy\}\to E(K^{*})$ be given by

\phi_{xy}(e)=\begin{cases}xy=c_{2}c_{3}&\text{if }e=xy,\\ c_{3}c_{4}&\text{if }e=c_{2}c_{3}c_{4}\cup D,\\ c_{1}c_{3}&\text{if }e=c_{1}c_{3}c_{4}\cup D,\\ c_{1}c_{2}&\text{if }e=c_{1}c_{2}c_{3}\cup D,\\ \phi(e)&\text{otherwise}.\end{cases}

Case 1.3: $c_{2}c_{4}=xy$ , say $c_{2}=x$ and $c_{4}=y$ . We have that $\phi^{-1}(xy)=c_{2}c_{4}c_{5}\cup D$ , while $\phi^{-1}(c_{4}c_{5})=c_{1}c_{4}c_{5}\cup D$ , and finally $\phi^{-1}(c_{1}c_{4})=c_{1}c_{2}c_{4}\cup D$ . Thus, we let $\phi_{xy}:E(\mathcal{C})\cup\{xy\}\to E(K^{*})$ be given by

\phi_{xy}(e)=\begin{cases}xy=c_{2}c_{4}&\text{if }e=xy,\\ c_{4}c_{5}&\text{if }e=c_{2}c_{4}c_{5}\cup D,\\ c_{1}c_{4}&\text{if }e=c_{1}c_{4}c_{5}\cup D,\\ c_{1}c_{2}&\text{if }e=c_{1}c_{2}c_{4}\cup D,\\ \phi(e)&\text{otherwise}.\end{cases}

Case 1.4: $c_{2}\in xy$ , $c_{1},c_{3},c_{4}\not\in xy$ , say $c_{2}=x$ . Note that $\phi^{-1}(xy)=c_{2}yc_{3}\cup D$ , while $\phi^{-1}(c_{3}y)=c_{3}yc_{1}\cup D$ , and $\phi^{-1}(c_{1}y)=c_{1}yc_{2}\cup D$ . This leads us to $\phi_{xy}:E(\mathcal{C})\cup\{xy\}\to E(K^{*})$ given by

\phi_{xy}(e)=\begin{cases}xy=c_{2}y&\text{if }e=xy\\ c_{3}y&\text{if }e=c_{2}yc_{3}\cup D\\ c_{1}y&\text{if }e=c_{3}yc_{1}\cup D\\ c_{1}c_{2}&\text{if }e=c_{1}yc_{2}\cup D\\ \phi(e)&\text{otherwise}\end{cases}.

Case 1.5: $c_{1}c_{2}\cap xy=\emptyset$ . Then $\phi^{-1}(xy)=c_{1}xy\cup D$ , and $\phi^{-1}(c_{1}x)=c_{1}xc_{2}\cup D$ . Let $\phi_{xy}:E(\mathcal{C})\cup\{xy\}\to E(K^{*})$ be given by

\phi_{xy}(e)=\begin{cases}xy&\text{if }e=xy,\\ c_{1}x&\text{if }e=c_{1}xy\cup D,\\ c_{1}c_{2}&\text{if }e=c_{1}xc_{2}\cup D,\\ \phi(e)&\text{otherwise}.\end{cases}

In all subcases, $\phi_{xy}$ gives a Berge- $K_{\ell}$ .

Case 2: $|xy\cap C|=1$ . Assume without loss of generality that $x\in C$ and $y\in D$ . let $c\in C\setminus\{x\}$ be any vertex, and note $c\preceq y$ . By Case 1, $\mathcal{C}+xc$ contains a Berge- $K_{\ell}$ with all core vertices in $C$ (in particular, $y$ is not core). Then by Observation 3.1, $\mathcal{C}+xy$ contains a Berge- $K_{\ell}$ .

Case 3: $xy\subseteq D$ . Note that $c_{1}\preceq x$ and $c_{2}\preceq y$ . By Case 1, $\mathcal{C}+c_{1}c_{2}$ contains a Berge- $K_{\ell}$ with all core vertices in $C$ . Then by Observation 3.1, $\mathcal{C}+xc_{2}$ contains a Berge- $K_{\ell}$ with all core vertices in $C\cup\{x\}$ , and so by Observation 3.1 again, $\mathcal{C}+xy$ contains a Berge- $K_{\ell}$ .

Now let us prove statement 2. of the Lemma 3.6. First, let $X\subseteq C$ be a set of $\ell-1$ vertices, and let $c\in C\setminus X$ and $x\in X$ . By Case 1 of statement 1. of Lemma 3.6, $\mathcal{C}+cx$ contains a Berge- $K_{\ell}$ with all core vertices in $C$ . In particular, every vertex in $X$ is core, and $cx\not\subseteq X$ , so $\mathcal{C}$ must contain a Berge- $K_{\ell-1}$ on $X$ .

Now assume $X\subseteq V(\mathcal{C})$ , $|X|=\ell-1$ , but with $X\not\subseteq C$ . Recall $c_{i}\preceq d_{j}$ for all $i\in[\ell]$ , $j\in[k-3]$ . Therefore, starting with any set $X^{\prime}$ of $\ell-1$ vertices with $X\cap C\subseteq X^{\prime}\subseteq C$ , we can replace the vertices in $X^{\prime}\setminus X$ with vertices in $X\cap D$ one at a time by repeated application of Observation 3.2. At each step, we retain the property that the current set of $\ell-1$ vertices is the core of a Berge- $K_{\ell-1}$ , resulting in a Berge- $K_{\ell-1}$ on $X$ . ∎

3.3 Saturated construction for large $n$

Here we provide the final construction which will provide the desired upper bound in Theorem 1.2.

Construction 3.7.

Fix $k\geq 3$ and $\ell\geq 4$ , and let $n\geq 10k^{2}\ell$ . Let $\mathcal{C}:=\mathcal{C}(k,\ell)$ , and let $c_{1},c_{2},\dots,c_{\ell-2}$ be $\ell-2$ distinct vertices from $\mathcal{C}$ . Let $a,b\in\mathbb{Z}_{\geq 0}$ be such that

a(k-1)+b(k-2)=n-|V(\mathcal{C})|-1

(4)

and $1\leq b\leq k-1$ . We then construct the hypergraph $\mathcal{S}:=\mathcal{S}(n,k,\ell)$ with vertex set

V(\mathcal{S})=V(\mathcal{C})\cup\bigcup_{i=1}^{a}A_{i}\cup\bigcup_{i=1}^{b}B_{i}\cup\{v\}

where $|A_{i}|=k-1$ for all $i\in[a]$ and $|B_{i}|=k-2$ for all $i\in[b]$ , noting that $|V(\mathcal{S})|=|V(\mathcal{C})|+a(k-1)+b(k-2)+1=n$ . Let

E(\mathcal{S})=E(\mathcal{C})\cup\{A_{i}\cup\{c_{j}\}\mid i\in[a],j\in[\ell-2]\}\cup\{B_{i}\cup\{v,c_{j}\}\mid i\in[b],j\in[\ell-2]\}.

(5)

See Figure 1 for a drawing of $\mathcal{S}(n,k,4)$ .

Refer to caption — Figure 1: The construction $\mathcal{S}(n,k,4)$

The bound $n\geq 10k^{2}\ell$ is not the best possible, it is simply an easy-to-state bound that is large enough to guarantee that a choice of integers $a,b$ in Construction 3.7 exists.

We now show that $\mathcal{S}(n,k,\ell)$ is Berge- $K_{\ell}$ -saturated, which will provide the desired upper bound in Theorem 1.2.

Lemma 3.8.

The hypergraph $\mathcal{S}:=\mathcal{S}(n,k,\ell)$ is Berge- $K_{\ell}$ -saturated for all $k\geq 3$ , $\ell\geq 4$ and $n\geq 10k^{2}\ell$ .

Proof.

First let us show that $\mathcal{S}$ is Berge- $K_{\ell}$ -free. Indeed, the only vertices that have degree at least $\ell-1$ are in $V(\mathcal{C})\cup\{v\}$ . The vertex $v$ only has $\ell-2$ neighbors with degree at least $\ell-1$ , so $v$ cannot be a core vertex of any Berge- $K_{\ell}$ , so any Berge- $K_{\ell}$ would be contained in $V(\mathcal{C})$ , but only $\binom{\ell}{2}-1$ edges of $\mathcal{S}$ have at least two vertices in $V(\mathcal{C})$ , so no Berge- $K_{\ell}$ exists in $\mathcal{S}$ .

Now, let $e\in E(\overline{\mathcal{S}})$ . By Lemmas 3.4 (1) and 3.6 (1), every pair in $V(\mathcal{C})$ is $\ell$ -good, so we may assume $|e\cap V(\mathcal{C})|\leq 1$ .

Case 1: Suppose there exists a pair $X,Y\in\{A_{i}\mid i\in[a]\}\cup\{B_{i}\mid i\in[b]\}$ with $X\neq Y$ such that $X\cap e\neq\emptyset$ and $Y\cap e\neq\emptyset$ . For simplicity let us assume $X,Y\in\{A_{i}\mid i\in[a]\}$ , as the case where one or more of $X$ or $Y$ are in $\{B_{i}\mid i\in[b]\}$ is nearly identical. Let $x\in X\cap e$ and $y\in Y\cap e$ . We claim there is a Berge- $K_{\ell}$ with core vertices $\{x,y,c_{1},c_{2},\dots,c_{\ell-2}\}$ . Indeed, by Lemma 3.4 (2) and Lemma 3.6 (2), there is a Berge- $K_{\ell-2}$ with core vertices $\{c_{1},c_{2},\dots,c_{\ell-2}\}$ using edges from $\mathcal{C}$ only. Then the edges $X\cup\{c_{i}\}$ and $Y\cup\{c_{i}\}$ can play the role of $xc_{i}$ and $yc_{i}$ respectively for each $i\in[\ell-2]$ (in the case where $X\in\{B_{i}\mid i\in[b]\}$ , we use the edges $X\cup\{v,c_{i}\}$ ), and finally $e$ can play the role of $xy$ , completing the Berge- $K_{\ell}$ .

Case 2: Suppose that $e\,\cap(V(\mathcal{C})\setminus\{c_{1},c_{2},\dots,c_{\ell-2}\})\neq\emptyset$ . Let $c\in e\,\cap(V(\mathcal{C})\setminus\{c_{1},c_{2},\dots,c_{\ell-2}\})$ and let $x\in e\setminus\{c\}$ . Note that $x\not\in V(\mathcal{C})$ since $|e\cap V(\mathcal{C})|\leq 1$ . We will assume $x\in A_{1}$ since if $x\in A_{i}$ for $i\in[a]\setminus\{1\}$ , $x\in B_{i}$ for $i\in[b]$ or $x=v$ , the case is nearly identical. We claim there is a Berge- $K_{\ell}$ with core vertices in $\{x,c,c_{1},c_{2},\dots,c_{\ell-2}\}$ . Indeed, by Lemma 3.4 (2) and Lemma 3.6 (2), there exists a Berge- $K_{\ell-1}$ with core vertices in $\{c,c_{1},c_{2},\dots,c_{\ell-2}\}$ and only using edges from $\mathcal{C}$ . Then the edge $A_{1}\cup\{c_{i}\}$ can play the role of $xc_{i}$ for $i\in[\ell-2]$ , while the edge $e$ plays the role of $xc$ , completing the Berge- $K_{\ell}$ .

Case 3: Suppose $v\in e$ and neither Case 1 nor Case 2 happen. We claim that there exists a set $X\in\{A_{i}\mid i\in[a]\}$ such that $e\cap X\neq\emptyset$ . Indeed, for the sake of contradiction, suppose there does not exist a set $X\in\{A_{i}\mid i\in[a]\}$ such that $e\cap X\neq\emptyset$ . Recall that $e$ can contain at most one vertex in $\mathcal{C}$ . Since we are not in Case 2, any vertex in $e\cap\mathcal{C}$ would need to be $c_{i}$ for some $i\in[\ell-2]$ . Since we are not in Case 1, $e$ cannot contain vertices from two $B_{j}$ ’s, so all the other vertices in $e$ must come from a single $B_{j}$ , $j\in[b]$ , however then $e=\{c_{i},v\}\cup B_{j}\in E(H)$ , a contradiction. We may assume, without loss of generality, that $A_{1}\cap e\neq\emptyset$ , say $a\in A_{1}\cap e$ . Then, similar to Case 1, we can find a Berge- $K_{\ell}$ with core vertices in $\{a,v,c_{1},c_{2},\dots,c_{\ell-2}\}$ . Indeed, by Lemma 3.4 (2) and Lemma 3.6 (2), there is a Berge- $K_{\ell-2}$ with core vertices $\{c_{1},c_{2},\dots,c_{\ell-2}\}$ using only edges from $\mathcal{C}$ . Then the edges $A_{1}\cup\{c_{i}\}$ and $B_{1}\cup\{v,c_{i}\}$ can play the role of $ac_{i}$ and $vc_{i}$ , respectively for each $i\in[\ell-2]$ . Finally, $e$ can play the role of $av$ , completing the Berge- $K_{\ell}$ .

Case 4: None of the cases 1, 2 or 3 happen. We claim that this does not occur. Indeed, $v\not\in e$ since we are not in Case 3. Furthermore, at most one vertex in $\mathcal{C}$ is in $e$ , and if any are, that vertex must be from $\{c_{1},c_{2},\dots,c_{\ell-2}\}$ since we are not in Case 2. Since we are not in Case 1, $e$ intersects at most one set $X\in\{A_{i}\mid i\in[a]\}\cup\{B_{i}\mid i\in[b]\}$ . Thus, the only way $e$ has $k$ vertices is if $e=X\cup\{c_{j}\}$ for some $X\in\{A_{i}\mid i\in[a]\}\cup\{B_{i}\mid i\in[b]\}$ and $j\in[\ell-2]$ . Furthermore, $X$ must be one of the $A_{i}$ ’s since the $B_{i}$ ’s only have $k-2$ vertices, but $A_{i}\cup\{c_{j}\}\in E(\mathcal{S})$ for all $i\in[a]$ , $j\in[\ell-2]$ , contradicting the assumption that $e\in E(\overline{\mathcal{S}})$ . ∎

The following theorem summarizes the results of Section 3. Our results could imply a slightly stronger bound than provided below, but we did not attempt to fight for lower-order terms, so this bound suffices for our purposes.

Theorem 3.9.

Fix $k\geq 3$ , $\ell\geq 4$ and let $n\geq 10k^{2}\ell$ . Then

\mathrm{sat}(n,\text{Berge-}K_{\ell})\leq\frac{\ell-2}{k-1}n+\binom{\ell}{2}-1

(6)

Proof.

By Lemma 3.8, $\mathcal{S}:=\mathcal{S}(n,k,\ell)$ is Berge- $K_{\ell}$ -saturated. Let $\mathcal{C}:=\mathcal{C}(k,\ell)$ . By (5), we can see that

|E(\mathcal{S})|=|E(\mathcal{C})|+(a+b)(\ell-2),

(7)

where $a$ and $b$ are the integers defined in (4). Recall that $|E(\mathcal{C})|=\binom{\ell}{2}-1$ . From (4), we have that

a+b=\frac{n-|V(\mathcal{C})|-1+b}{k-1}\leq\frac{n}{k-1},

(8)

where the inequality follows from the fact that $b\leq k-1$ and the fact that

|V(\mathcal{C})|=\begin{cases}k+2&\text{if }\ell=4,\\ k+\ell-3&\text{ if }\ell\geq 5.\end{cases}

Combining (7) and (8) gives us (6). ∎

4 Results on linearity for Berge- $F$ saturation

In this section, we prove Theorems 1.3 and 1.4. We start with a construction which will help us prove Theorem 1.3.

Construction 4.1.

Fix $k\geq 3$ , let $F$ be a ( $2$ -uniform) graph with $|V(F)|\geq\alpha(F)+2$ , and let $n\geq 10k|V(F)|^{3}$ . Set $\nu:=|V(F)|-\alpha(F)-1$ for convenience. Assume that $k>\nu$ , and let $a,t\in\mathbb{Z}_{\geq 0}$ be such that

a(k-\nu+1)+t=n-\nu

(9)

and $0\leq t<k-\nu+1$ . We then construct the hypergraph $\mathcal{H}:=\mathcal{H}(n,k,F)$ with vertex set

V(\mathcal{H})=V_{1}\cup\bigcup_{i=1}^{a}A_{i}\cup T,

where $|V_{1}|=\nu$ , $|A_{i}|=k-\nu+1$ for all $i\in[a]$ , and $|T|=t$ . Let $V_{1}=\{v_{1},v_{2},\dots,v_{\nu}\}$ . Let

E(\mathcal{H})=\{(V_{1}\cup A_{i})\setminus\{v_{j}\}\mid i\in[a],j\in[\nu]\}.

We do not always expect $\mathcal{H}(n,k,F)$ to be Berge- $F$ -free, but the following lemma shows that if it is Berge- $F$ -free, the saturation numbers for Berge- $F$ grow linearly.

Lemma 4.2.

Let $F$ be a graph with $|V(F)|\geq\alpha(F)+2$ , $k>|V(F)|-\alpha(F)-1=:\nu$ and $n\geq 10k|V(F)|^{3}$ . If $\mathcal{H}:=\mathcal{H}(n,k,F)$ is Berge- $F$ -free, then

\mathrm{sat}_{k}(n,\text{Berge-}F)=O(n).

Proof.

Let $\alpha:=\alpha(F)$ and $A:=\bigcup_{i=1}^{a}A_{i}$ .

First, we claim that for any set $\{a_{1},a_{2},\dots,a_{\alpha+1}\}\subset A$ in which $a_{i}$ and $a_{j}$ are from different $A_{k}$ ’s, there exists a Berge- $(K_{\nu}\vee\overline{K_{\alpha+1}})$ in $\mathcal{H}$ with core vertices $\{v_{1},v_{2},\dots,v_{\nu}\}\cup\{a_{1},a_{2},\dots,a_{\alpha+1}\}$ and in which the $v_{i}$ ’s correspond to the $K_{\nu}$ . Indeed, let us assume without loss of generality that $a_{i}\in A_{i}$ . Now, for each $i\in[\alpha+1]$ and $j\in[\nu]$ , we can use the edge $(V_{1}\cup A_{i})\setminus\{v_{j-1}\}$ to connect $a_{i}$ to $v_{j}$ (indices of the $v_{j}$ ’s taken modulo $\nu$ ), giving us a Berge $K_{\nu,\alpha+1}$ . Then, from (9), we can see that

a=\frac{n-\nu-t}{k-\nu+1}\geq\frac{n-k}{k}>\nu^{2}+\alpha+1,

where in the last inequality, we use our bound on $n$ and that $\nu^{2}+\alpha+2<10|V(F)|^{3}$ . In particular, this implies that we have at least $\nu^{2}>\binom{\nu}{2}$ sets $A_{i}$ with $i>\alpha+1$ . Therefore, there are plenty of edges of the form $(V_{1}\cup A_{i})\setminus\{v_{j}\}$ for $i\in[a]\setminus[\alpha+1]$ and $j\in[\nu]$ to create the Berge- $K_{\nu}$ on $V_{1}$ . This completes the proof of the claim.

Now, arbitrarily add edges to $\mathcal{H}$ that do not create a Berge- $F$ until the hypergraph is Berge- $F$ -saturated, and call the resulting hypergraph $\mathcal{H}^{\prime}$ . Let $x\in A$ be a vertex. For the sake of contradiction, assume that

d_{\mathcal{H}^{\prime}}(x)-d_{\mathcal{H}}(x)>\binom{|V_{1}|+t+(\alpha-1)k^{2}}{k-1}.

This implies that $x$ has $\alpha$ neighbors, which we will denote by $x_{1},\dots,x_{\alpha}\in A$ such that

1.

$x_{i}$ and $x_{i^{\prime}}$ are not contained in the same $A_{j}$ for $i\neq i^{\prime}$ , $j\in[a]$ , and
2.

there exists an injection $\phi$ from $\{x_{1},\dots,x_{\alpha}\}$ into $\{e\in E(\mathcal{H}^{\prime})\setminus E(\mathcal{H})\mid x\in e\}$ such that $x_{i}\in\phi(x_{i})$ for $i\in[\alpha]$ .

Indeed, since $d_{\mathcal{H}^{\prime}}(x)-d_{\mathcal{H}}(x)>\binom{|V_{1}|+t}{k-1}$ , $x$ must have a neighbor outside of $V_{1}\cup T$ , say $x_{1}$ , with an edge $e_{1}\in E(\mathcal{H}^{\prime})\setminus E(\mathcal{H})$ such that $x,x_{1}\in e_{1}$ . The edge $e_{1}$ intersects at most $k$ of the $A_{i}$ ’s. Let $B_{1}$ denote the union of all the $A_{i}$ ’s which intersect $e_{1}$ , and note that $|B_{1}|\leq k|A_{1}|\leq k^{2}$ . Since $d_{\mathcal{H}^{\prime}}(x_{1})-d_{\mathcal{H}}(x_{1})>\binom{|V_{1}|+t+k^{2}}{k-1}$ , $x$ must have a second neighbor, say $x_{2}$ , not in $V_{1}\cup T\cup B_{1}$ , and let $e_{2}\in E(\mathcal{H}^{\prime})\setminus E(\mathcal{H})$ be such that $x,x_{2}\in e_{2}$ , noting that $e_{2}\neq e_{1}$ . Then we can define $B_{2}$ to be the union of all the $A_{i}$ ’s that intersect $e_{1}$ or $e_{2}$ , and note that $|B_{2}|\leq 2k|A_{1}|\leq 2k^{2}$ . Continuing inductively, we can find $x_{3},\dots,x_{\alpha}$ , as claimed.

These edges in $E(\mathcal{H}^{\prime})\setminus E(\mathcal{H})$ , along with the Berge- $(K_{\nu}\vee\overline{K_{\alpha+1}})$ in $\mathcal{H}$ with core vertices $\{v_{1},v_{2},\dots,v_{\nu},x_{1},x_{2},\dots,x_{\alpha},x\}$ give us a Berge- $(K_{\nu+1}\vee\overline{K_{\alpha}})$ , which contains a Berge- $F$ , a contradiction. Thus, $d_{\mathcal{H}^{\prime}}(x)-d_{\mathcal{H}}(x)\leq\binom{|V_{1}|+t+(\alpha-1)k^{2}}{k-1}$ for every vertex $x\in A$ .

We can now wastefully bound $|E(\mathcal{H}^{\prime})|$ . Indeed, we have that $|E(\mathcal{H})|=\nu a\leq\nu n=O(n)$ , and

	$\displaystyle\|E(\mathcal{H}^{\prime})\setminus E(\mathcal{H})\|$	$\displaystyle\leq\|\{e\in V_{1}\cup T\}\|+\|\{e\in E(\mathcal{H}^{\prime})\setminus E(\mathcal{H})\mid e\cap A\neq\emptyset\}\|$
		$\displaystyle\leq\binom{\|V_{1}\|+t}{k}+ak\binom{\|V_{1}\|+t+(\alpha-1)k^{2}}{k-1}$
		$\displaystyle\leq k\binom{\|V_{1}\|+t+(\alpha-1)k^{2}}{k-1}n=O(n).$

Thus,

\mathrm{sat}_{k}(n,\text{Berge-}F)\leq|E(\mathcal{H}^{\prime})|=|E(\mathcal{H})|+|E(\mathcal{H}^{\prime})\setminus E(\mathcal{H})|=O(n).

∎

We will need a result from [1] to deal with an edge case in Theorem 1.3. The result below is significantly weaker than the result in [1], but it suffices for our purposes.

Theorem 4.3 ([1]).

For any $k\geq 3$ , $\ell\geq 1$ ,

\mathrm{sat}_{k}(n,\text{Berge-}K_{1,\ell})=O(n).

We also need a result that handles the case when $k\leq\nu$ . Let $\beta(F)$ denote the vertex cover number of $F$ .

Theorem 4.4 ([5]).

Fix $k\geq 3$ . If $F$ is a graph with $\beta(F)\geq k+1$ , then $\mathrm{sat}_{k}(n,\text{Berge-}F)=O(n)$ .

We can now prove the first of our two results on linearity.

Proof of Theorem 1.3.

First note that if $\alpha(F)=|V(F)|$ , then $F$ contains no edges and the saturation function is not defined. Furthermore, if $\alpha(F)=|V(F)|-1$ , then $F$ is a star, and by Theorem 4.3, the result follows. Thus, we may assume $|V(F)|\geq\alpha(F)+2$ . Suppose that $|V(F)|-\alpha(F)-1=:\nu\geq k$ . Then using the fact that $|V(F)|=\alpha(F)+\beta(F)$ , we get $\beta(F)-1\geq k$ . In this case, Theorem 4.4 shows that $\mathrm{sat}_{k}(n,\text{Berge-}F)=O(n)$ . Thus, we will assume that $k>\nu$ .

Let $\mathcal{H}:=\mathcal{H}(n,k,F)$ as in Construction 4.1. We claim that $\mathcal{H}$ is Berge- $F$ -free. Assume to the contrary that there is a copy of $F$ which witnesses Berge- $F$ in $\mathcal{H}$ . We have that $|V(F)\cap A|\geq|V(F)|-\nu=\alpha(F)+1$ , and further there must exist an $i\in[a]$ such that $|V(F)\cap A_{i}|\geq 2$ since otherwise the $\alpha(F)+1$ vertices in $V(F)\cap A$ would form an independent set in $F$ which is too large. Say $x,y\in A_{i}$ . We must have $d_{F}(x)+d_{F}(y)-1\leq\nu$ since there are only $\nu$ edges of $\mathcal{H}$ that intersect $A_{i}$ and only one can play the role of $xy$ , contributing to the degree of both vertices, but $d_{F}(x)+d_{F}(y)-1\geq 2\delta(F)-1>|V(F)|-\alpha(F)-1=\nu$ , a contradiction.

Thus, $\mathcal{H}$ is Berge- $F$ -free, so by Lemma 4.2, the result holds. ∎

We state here a construction from [5] for a $k$ -uniform hypergraph on a vertex set $V$ of size $n$ (where $n$ is sufficiently large), which will be used to prove our final result. We will let $f(G)$ denote the vertex feedback number of the graph $G$ .

Construction 4.5 ([5]).

Let $G$ be any graph and let $n$ be sufficiently large. If $f(G)=0$ , then for any $a$ , let $H_{k}(n,a,G,\emptyset)$ denote the empty graph on vertex set $V$ . If $f(G)\geq 1$ , let $S$ be a minimum vertex feedback set of $G$ , and let $|E(G[S])|=\ell$ . Let the (initially empty) vertex set $V$ be partitioned into three sets $V=V_{1}\cup V_{2}\cup V_{3}$ , where $|V_{1}|=f(G)$ , and $|V_{2}|=(k-2)\ell$ . We first add $\ell$ edges between $V_{1}$ and $V_{2}$ to create a Berge- $G[S]$ with core vertices in $V_{1}$ . Indeed, arbitrarily label the vertices in $V_{1}$ with labels from the vertex set of $G[S]$ , and then for each $2$ -edge $uv$ of $G[S]$ , add a $k$ -edge that contains the vertices labeled $u$ and $v$ in $V_{1}$ , and $k-2$ vertices in $V_{2}$ so that after all $\ell$ edges are added, each vertex in $V_{2}$ has degree $1$ .

Now, choose some integer $1\leq a\leq k-1$ such that $a+f(G)\geq k$ . If $a$ does not divide $|V_{3}|$ , arbitrarily choose $(|V_{3}|\mod a)$ vertices, and remove them to form the set $V_{3}^{\prime}\subset V_{3}$ , with $|V_{3}^{\prime}|=ra$ for some $r\in\mathbb{Z}$ . Partition $V_{3}^{\prime}$ into $r$ sets of size $a$ , and let $\mathcal{M}$ be the collection of these $a$ -sets. For each $a$ -set $A$ in $\mathcal{M}$ , add the $\binom{|V_{1}|}{k-a}$ edges that contain $A$ and $k-a$ vertices from $V_{1}$ . Call this construction $\mathcal{H}_{k}(n,a,G,S)$ .

Our poof of Theorem 1.4 will use $a=k-f(G)+1$ or $a=k-1$ . However, the original statement of the construction of $\mathcal{H}_{k}(n,a,G,S)$ in [5] takes $a$ as a more general parameter and facilitates the statement of their theorem.

Theorem 4.6 ([5]).

Let $F$ be a graph with vertex feedback set $S$ , $|S|=f(F)$ . Let $1\leq a\leq k-1$ be such that $a+f(F)>k$ . If $\mathcal{H}(n,a,F,S)$ does not contain a Berge- $F$ , then

\mathrm{sat}_{k}(n,\text{Berge-}F)=O(n).

We are now ready to prove Theorem 1.4

Proof of Theorem 1.4.

Let $S$ be a minimum vertex feedback set of $F$ . First, consider the case when $f\leq k$ so that $1\leq a=k-f+1\leq k$ . Let $H:=H_{k}(n,k-f+1,F,S)$ . We claim that $H$ is Berge- $F$ -free. Indeed, suppose for the sake of contradiction, that $H$ contains a Berge- $F$ , and let $F$ be a witness to this Berge- $F$ . For any $A\in\mathcal{M}$ , only $\binom{|V_{1}|}{k-a}=\binom{f}{f-1}=f<g$ edges of $H$ are incident with vertices in $A$ , so no cycle of $F$ can be contained in a set $A$ . This implies that $V_{1}$ is a vertex feedback set of $F$ , and since $|V_{1}|=f$ , $V_{1}$ is a minimum vertex feedback set of $F$ .

Similarly, if $f>k$ , then we choose $a=k-1$ and let $H:=H_{k}(n,k-f+1,F,S)$ . We claim that $H$ is Berge- $F$ -free. Indeed, suppose for the sake of contradiction, that $H$ contains a Berge- $F$ , and let $F$ be a witness to this Berge- $F$ . For any $A\in\mathcal{M}$ , only $\binom{|V_{1}|}{k-a}=\binom{f}{1}=f<g$ edges of $H$ are incident with vertices in $A$ , so no cycle of $F$ can be contained in a set $A$ . This implies that $V_{1}$ is a vertex feedback set of $F$ , and since $|V_{1}|=f$ , $V_{1}$ is a minimum vertex feedback set of $F$ .

In either case, we proceed with the following argument. For any $v\in V_{1}$ , $v$ must be in a cycle $C$ in $F$ that does not contain any other vertices in $V_{1}$ , since otherwise $V_{1}\setminus\{v\}$ would be a smaller vertex feedback set. However, this implies that $C$ is contained in $\{v\}\cup A$ for some $A\in\mathcal{M}$ , but there are only $f<g$ hyperedges of $H$ that intersect $A$ , so there are not enough hyperedges to create a Berge copy of the cycle $C$ , and we arrive at a contradiction.

Thus $H$ is Berge- $F$ -free, and by Theorem 4.6, the result follows. ∎

5 Concluding remarks

The saturation number for Berge- $K_{3}$ is known exactly, whereas here we were only able to determine the asymptotics of the saturation number for larger cliques. It would be nice to be able to find the exact value, at least in some small cases. The most tractable case is $\mathrm{sat}_{3}(n,\text{Berge-}K_{4})$ . By counting edges in $\mathcal{S}(n,3,4)$ from Construction 3.7 more carefully than is done in Theorem 3.9, we can get the following:

Remark 5.1.

For all $n\geq 10$ ,

\mathrm{sat}_{3}(n,\text{Berge-}K_{4})\leq\begin{cases}n&\text{ if }n\text{ is odd,}\\ n+1&\text{ if }n\text{ is even.}\end{cases}

It seems difficult to push the lower bound to match this, but it would be quite interesting to see work in this direction.

Problem 5.2.

Determine $\mathrm{sat}_{3}(n,\text{Berge-}K_{4})$ exactly. In particular, is $\mathrm{sat}_{3}(n,\text{Berge-}K_{4})=n$ when $n$ is odd?

References

[1] B. Austhof and S. English, Nearly-regular hypergraphs and saturation of Berge stars, Electron. J. Combin. 26 (2019), no. 4, Paper No. 4.49, 11.
[2] M. Axenovich and C. Winter, A note on saturation for Berge- $G$ hypergraphs, Graphs Combin. 35 (2019), no. 4, 933–939.
[3] B. Bollobás, On generalized graphs, Acta Math. Acad. Sci. Hungar. 16 (1965), 447–452.
[4] B. Currie, J. Faudree, R. Faudree, and J. Schmitt, A survey of minimum saturated graphs, Electron. J. Combin. (2021), DS19: Oct 11, 2021.
[5] S. English, D. Gerbner, A. Methuku, and M. Tait, Linearity of saturation for Berge hypergraphs, European J. Combin. 78 (2019), 205–213.
[6] S. English, P. Gordon, N. Graber, A. Methuku, and E. Sullivan, Saturation of Berge hypergraphs, Discrete Math. 342 (2019), no. 6, 1738–1761.
[7] P. Erdős, A. Hajnal, and J. Moon, A Problem in Graph Theory, The American Mathematical Monthly 71 (1964), no. 10, 1107–1110.
[8] D. Gerbner and C. Palmer, Extremal results for Berge hypergraphs, SIAM J. Discrete Math. 31 (2017), no. 4, 2314–2327.
[9] D. Gerbner, B. Patkós, Zs. Tuza, and M. Vizer, On saturation of Berge hypergraphs, European J. Combin. 102 (2022), Paper No. 103477, 7.
[10] L. Kászonyi and Z. Tuza, Saturated graphs with minimal number of edges, J. Graph Theory 10 (1986), no. 2, 203–210.
[11] L. Liu, C. He, and L. Kang, Saturation number of Berge stars in random hypergraphs, Electron. J. Combin. 27 (2020), no. 4, Paper No. 4.45, 10.
[12] O. Pikhurko, The minimum size of saturated hypergraphs, Combin. Probab. Comput. 8 (1999), no. 5, 483–492.

	$\displaystyle\|E(\mathcal{H}^{\prime})\setminus E(\mathcal{H})\|$	$\displaystyle\leq\|\{e\in V_{1}\cup T\}\|+\|\{e\in E(\mathcal{H}^{\prime})\setminus E(\mathcal{H})\mid e\cap A\neq\emptyset\}\|$
		$\displaystyle\leq\binom{\|V_{1}\|+t}{k}+ak\binom{\|V_{1}\|+t+(\alpha-1)k^{2}}{k-1}$
		$\displaystyle\leq k\binom{\|V_{1}\|+t+(\alpha-1)k^{2}}{k-1}n=O(n).$

Saturation Numbers for Berge Cliques

Abstract

1 Introduction

Theorem 1.1 ([6]).

Theorem 1.2.

Theorem 1.3.

Theorem 1.4.

1.1 Definitions and organization

2 Lower bound for Berge-KℓK_{\ell} saturation

Theorem 2.1.

Proof.

3 Upper bound

3.1 Upper bound tools

Observation 3.1.

Proof.

Observation 3.2.

Proof.

3.2 Small hypergraphs saturated with respect to pairs

Construction 3.3.

Lemma 3.4.

Proof.

Construction 3.5.

Lemma 3.6.

Proof.

3.3 Saturated construction for large nn

Construction 3.7.

Lemma 3.8.

Proof.

Theorem 3.9.

Proof.

4 Results on linearity for Berge-FF saturation

Construction 4.1.

Lemma 4.2.

Proof.

Theorem 4.3 ([1]).

Theorem 4.4 ([5]).

Proof of Theorem 1.3.

Construction 4.5 ([5]).

Theorem 4.6 ([5]).

Proof of Theorem 1.4.

5 Concluding remarks

Remark 5.1.

Problem 5.2.

References

2 Lower bound for Berge- $K_{\ell}$ saturation

3.3 Saturated construction for large $n$

4 Results on linearity for Berge- $F$ saturation