Book free $3$-Uniform Hypergraphs

Let $G$ be a graph. The vertex and the edge set of $G$ are denoted by $V(G)$ and $E(G)$. If there are two triangles sitting on an edge in a graph, we call this a diamond. Whereas $k$ triangles sitting on an edge is called a $k$-book, denoted by a $B_{k}$. Similarly, let $H$ be a hypergraph and the vertex and the edge set of $H$ be denoted by $V(H)$ and $E(H)$. A hypergraph is called $r$-uniform if each member of $E$ has size $r$. A hypergraph $H=(V,E)$ is called linear if every two hyperedges have at most one vertex in common. A Berge cycle of length $k$, denoted by Berge-$C_{k}$, is an alternating sequence of distinct vertices and distinct hyperedges of the form $v_{1},h_{1},v_{2},h_{2},\dots,v_{k},h_{k}$ where $v_{i},v_{i+1}\in h_{i}$ for each $i\in\{1,2,\dots,k-1\}$ and $v_{k}v_{1}\in h_{k}$. The hypergraph equivalent of $k$-books is defined similarly with $k$ Berge triangles sharing a common edge. We say that this common edge is the base of the $k$-book.

The maximum number of edges in a triangle-free graph is one of the classical results in extremal graph theory and proved by Mantel in $1907$ [13]. The extremal problem for diamond-free graphs follows from this. Given a graph $G$ on $n$ vertices and having $\left\lfloor{\frac{n^{2}}{4}}\right\rfloor+1$ edges. Mantel showed that $G$ contains a triangle. Rademacher (unpublished, and simplified later by Erdős in [6]) proved in the 1940s that the number of triangles in $G$ is at least $\left\lfloor{\frac{n}{2}}\right\rfloor$. Erdős conjectured in 1962 [7] that the size of the largest book in $G$ is at least $\frac{n}{6}$ and this was proved soon after by Edwards (unpublished, see also Khadźiivanov and Nikiforov [11] for an independent proof).

Both Rademacher’s and Edwards’ results are sharp. In the former, the addition of an edge to one part in the complete balanced bipartite graph (note that in $G$ there is an edge contained in $\left\lfloor{\frac{n}{2}}\right\rfloor$ triangles) achieves the maximum. In the latter, every known extremal construction of $G$ has $\Omega(n^{3})$ triangles. For more details on book-free graphs we refer the reader to the following articles [2], [14] and [16]. We look into the equivalent problem in the case of hypergraphs.

Given a family of hypergraphs $\mathcal{F}$, we say that a hypergraph $H$ is $\mathcal{F}$-free if for every $F\in\mathcal{F}$, the hypergraph $H$ does not contain a $F$ as a sub-hypergraph.

The systematic study of the Turán number of Berge cycles started with Lazebnik and Verstraëte [12], who studied the maximum number of hyperedges in an $r$-uniform hypergraph containing no Berge cycle of length less than five. Another result was the study of Berge triangles by Győri [8]. He proved that:

It continued with the study of Berge five cycles by Bollobás and Győri [3]. In [9], Győri, Katona, and Lemons proved the following analog of the Erdős-Gallai Theorem [5] for Berge paths. For other results see [1, 10]. The particular case of determining the maximum number of the hyperedges of a triangle-free linear hypergraph on $n$ vertices is equivalent to the famous $(6,3)$-problem, which is a special case of a general problem of Brown, Erdős, and Sós. The following theorem of Ruzsa and Szemerédi plays important role in our paper:

We continue the work on that and determine the maximum number of hyperedges for a $k$-book-free $3$-uniform hypergraph. The main result is as follows:

The following example shows that this result is asymptotically sharp. Take a complete bipartite graph with color classes of size $\left\lceil{\frac{n}{4}}\right\rceil$ and $\left\lfloor{\frac{n}{4}}\right\rfloor$ respectively. Denote the vertices in each class with $x_{i}$ and $y_{i}$ respectively. Construct a graph by doubling each vertex and replacing each edge with two hyperedges as shown below (Figure 1). So essentially, we have replaced every graph edge with two hyperedges. The construction does not contain a $B_{k}$, as it does not contain a Berge triangle. With this, the number of hyperedges is $2\times\frac{n^{2}}{16}=\frac{n^{2}}{8}$.

Fix $k\geq 2$, $\epsilon>0$ and set

$$n_{1}(k,\epsilon)=\max\left\{18k+12,n_{0}\left(\frac{\epsilon}{6k^{2}-8k}\right)\right\}$$

where $n_{0}(.)$ is from Theorem 3. Suppose that $n>n_{1}(k,\epsilon)$. Let $H$ be a $B_{k}$-free $3$-uniform hypergraph on $n$ vertices. We are interested in the $2$-shadow, i.e., let $G$ be a graph with vertex set $V(H)$ and

$$E(G)=\{ab\mid\{a,b\}\subset e\in E(H)\}.$$

If an edge in $G$ lies in more than one hyperedge in $H$, we color it blue. Otherwise, we color it red. We define hypergraphs $H_{r}$ and $H_{b}$ in the following way. $V(H_{r})=V(H_{b})=V(H)$,

$$E(H_{r})=\{e\in E(H)\mid e\textrm{ contains two or three red edges of }G\}$$

and $E(H_{b})=E(H)\setminus E(H_{r})$. Note that each hyperedge in $H_{b}$ contains two or three blue edges of $G$.

Now let us work on the sub-hypergraph $H_{b}$.

We now give an upper bound on the number of hyperedges in $H_{b}$.

Recall that both Turán numbers of triangle-free graph and $k$-book-free graphs on $n$ vertices are $\frac{n^{2}}{4}$, moreover Győri [8] proved that the maximum number of hyperedges in a Berge triangle-free $3$-uniform hypergraphs on $n$ vertices is at most $\frac{n^{2}}{8}$. Given the similarities, we conjecture the following:

Győri’s research was partially supported by the National Research, Development and Innovation Office NKFIH, grants K132696, K116769, and K126853. Judit Nagy-György acknowledges support by the project TKP2021-NVA-09. Project no. TKP2021-NVA-09 has been implemented with the support provided by the Ministry of Innovation and Technology of Hungary from the National Research, Development and Innovation Fund, financed under the TKP2021-NVA funding scheme. Nagy-György’s research was partially supported by the National Research, Development and Innovation Office NKFIH, grant KH129597.