Uniformity thresholds for the asymptotic size of extremal Bergefree hypergraphs
Abstract
Let be a graph and be a hypergraph. We say that contains a Berge if there exist injections and such that for every , . Let denote the maximum number of hyperedges in an uniform hypergraph on vertices which does not contain a Berge.
For small enough and nonbipartite , ; we show that for sufficiently large , . Let . We show lower and upper bounds for , the uniformity threshold of . In particular, we obtain that , improving a result of Győri [5].
We also study the analogous problem for linear hypergraphs. Let denote the maximum number of hyperedges in an uniform linear hypergraph on vertices which does not contain a Berge, and let the linear unformity threshold . We show that is equal to the chromatic number of .
1 Introduction and main results
Let be a graph and be a hypergraph. Generalizing the earlier definitions of Bergepath and Bergecycle, Gerbner and Palmer [3] introduced the notion of Berge hypergraphs.
Definition 1.
We say that is a Berge if there exist bijections and such that for every , .
Given a hypergraph , we denote by the shadow of , that is, the graph on the same vertex set, containing all element subsets of hyperedges from as edges. Observe that contains a Berge as a subgraph if and only if contains a copy of such that has a distinct hyperedge containing each edge of this copy of .
For a graph , let denote the maximum number of hyperedges in an uniform hypergraph on vertices which does not contain a Berge as a subgraph. The case when is the classical Turán function . We will also consider what happens if we impose the additional assumption that the hypergraph is linear (i.e., any two hyperedges intersect in at most one element). We denote the maximum number of hyperedges in a linear uniform hypergraph on vertices which does not contain a Berge by .
Győri, Katona and Lemons [7] generalized the Erdős–Gallai theorem to Bergepaths. Győri and Lemons [6] gave upper bounds, and in some cases constructions, for . Gerbner and Palmer [3] gave bounds on for and specifically . It follows from Győri’s results in [5] that if is large enough. For this result is asymptotically sharp. We studied this problem in higher uniformities, and determined that, in fact, when , improving Győri’s result. This will be obtained as a special case of more general theorems presented later.
The following result can be proved easily.
Proposition 2 (Gerbner and Palmer [3]).
For any graph and , we have
We include its proof in Section 3. By the Erdős–Stone theorem, for any bipartite graph , we have . Moreover, in the graph case, if is not bipartite, then we have . We will show that for any graph and for any sufficiently large , we have . We introduce the following threshold functions.
Definition 3.
Let be a graph. We define the uniformity threshold of as
We define the linear uniformity threshold of as
Our first theorem gives an upper bound for the value of for any graph . (Note that if is bipartite, then by Proposition 2.) The Ramsey number of two graphs is defined to be the smallest such that every coloring of the edges of the complete graph contains a copy of in the first color or in the second color. For every and this number is known to be finite by Ramsey’s theorem.
For a graph containing an edge , let denote the graph formed by deleting from .
Theorem 4.
For any graph (with at least two edges), and any of its edges , we have
Our next result is a construction giving a lower bound on .
Theorem 5.
Let be a graph with clique number . For any , there exists an uniform, Bergefree hypergraph on vertices with hyperedges. Therefore we have
The above two theorems imply .
Erdős, Frankl and Rödl [2] constructed a linear uniform Bergetrianglefree hypergraph with more than hyperedges for any and . This implies that when , in our definition of the functions and , cannot be replaced by a function of with smaller exponent.
Finally, we consider linear hypergraphs. (In Section 5 we prove Theorem 5 by blowing up a linear, Bergefree hypergraph.) It is easy to see that a linear hypergraph on vertices has at most hyperedges: fix a pair of vertices in each hyperedge; by the definition of a linear hypergraph, all these pairs must be distinct. Timmons [9] showed that (with our notation) . We prove the following exact result.
Theorem 6.
For any (nonempty) graph , we have
and for any , there exists an uniform, linear, Bergefree hypergraph on vertices with hyperedges.
Note that may be bigger than the lower bound in Theorem 5, and it obviously also bounds from below. Generalizing the proof of Theorem 5, we prove the following common generalization of Theorem 5 and the lower bound on coming from Theorem 6.
For a graph , we define a admissible partition of as a partition of into sets of size at most , such that between any two sets there is at most one edge in . ‘Contracting’ a set of vertices in a graph produces a new graph in which all the vertices of are replaced with a single vertex such that is adjacent to all the vertices to which any of the vertices of was originally adjacent.
Theorem 7.
Let be a graph, and let . Consider all the graphs obtained by contracting each set in some admissible partition of to a point, and let be the minimum of the chromatic numbers of all such graphs. If , then .
For , the only admissible partition of a graph is putting every vertex into a different set, so , and we just get back the lower bound in Theorem 6. We also get Theorem 5 as a special case of Theorem 7 when : In any admissible partition of , every vertex in a maximal clique of must belong to a different set of the partition. Indeed, no set of the partition may contain all vertices of an clique. But if a set from the partition contained two or more vertices of an clique, and another set contained another vertex of that clique, then there would be two or more edges between and , contradicting the definition of a admissible partition. This means that the graph we get after contracting all the sets of an admissible partition contains an clique, so its chromatic number is at least . Therefore .
As an example where Theorem 7 gives an improvement, consider . Putting and , we get . Indeed, the only 3admissible partition of is to put every vertex of into a different set. Theorem 5 gives a lower bound of just 5, while Theorem 6 gives 3. We give further corollaries of Theorem 7 about blowups of graphs in Section 5.
Until now we focused on uniformities for which is subquadratic. In Section 2, we discuss the behavior of as grows, more generally. In particular, we discuss uniformities for which is superquadratic using the relationship between and the maximum number of ’s in an free graph.
2 Behavior of as increases
Alon and Shikhelman [1] studied the maximum number of copies of a graph in an free graph on vertices, denoted . For example, in the following proposition, we paraphrase Propositions 2.1 and 2.2 in [1].
Proposition 8 (Alon and Shikhelman [1]).
Let . Then if and only if . Moreover, if , then for some . , otherwise
For the case, a construction showing is a complete partite graph on vertices with roughly vertices in each part. It has chromatic number , so it does not contain , and it contains copies of .
Clearly : Take an free graph with cliques, and replace each clique with a hyperedge containing the vertices of the clique. The resulting hypergraph cannot contain a Berge, as its 2shadow does not even contain a copy of . The converse is not true. If we take a Bergefree hypergraph with hyperedges, and we replace its hyperedges with cliques (i.e., we take its 2shadow), it might contain a copy of . The upper bound in the following proposition, which relates to , was discovered by Gerbner and Palmer [4]. As the proof is very simple, we include it for completeness.
Proposition 9 (Gerbner and Palmer [4]).
For any ,
Proof.
We have already seen . To prove , let be an uniform, Bergefree hypergraph on a vertex set of elements. We consider the hyperedges of onebyone, and we will mark elements of . For each hyperedge, we mark a pair of its vertices that we have not marked yet; if all those pairs are already marked, then we mark the hyperedge itself.
Let be the set of the marked pairs and hyperedges. is a graph with no copy of . Indeed, since we only marked one edge for each hyperedge, if the graph contained a copy of , its edges would be contained by distinct hyperedges of , which would form a Berge. So . Meanwhile each hyperedge in was marked because each pair of vertices in it had already been marked, so they form an clique in . But is free, so the number of cliques in it is at most . Thus, . Since , the proof is complete. ∎
Proposition 9 implies that the two functions and differ by only . So if and only if , and we have if and only if . Moreover, if , then . If is bipartite, since , the difference is even smaller — only . So for bipartite , if and only if , and if , then .
On the other hand, note that for any nonbipartite , even if we know , Proposition 9 does not imply ; so does not tell us much about .
Combining Proposition 8 and Proposition 9, we can obtain the following nice proposition discovered by Palmer et al. [8]. We note, however, that the proof given in [8] is different from the simple proof mentioned here.
Proposition 10.
Let . If , then and if , then .
More precisely, if , then , then for some . , and if
Below we outline some interesting facts about the behavior of as grows.
Proposition 10 shows that as increases from until , the function increases, and from , it is . From (at the latest), it becomes again (by Proposition 2). However, the decrease does not stop there. As shown by Theorem 4, from some point, it becomes .
In general, we do not know much about the behavior of when is between and . In the special case of , we know more. As increases from to , immediately jumps from to (by Proposition 2 since ), and it is at most for all . It would be very interesting to determine the precise threshold for when it becomes subquadratic.
It is also notable that may increase with in the range (as will be shown by the proposition below). Theorem 1.2 in Alon and Shikhelman’s paper [1] shows that if and , then . It is easy to check that monotonously increases in between and , and when . So combining this with Proposition 9, we get
Proposition 11.
For any and , we have .
Of course , while if , which implies that is not necessarily the smallest for which . (Then from some point later on — at the latest — it becomes subquadratic again and remains so.)
For a nonbipartite graph , Theorem 4 implies that for any , we have . However, it is unclear if the same holds for some bipartite graphs. If is a forest, then it is known that .
Question 12.
Is there a bipartite graph containing a cycle for which the following statement holds: There exists an integer such that for all ? If yes, is the same statement true for every bipartite containing a cycle?
The analogous question for linear hypergraphs was asked by Verstraëte [9]. For , we ask the following, more precise question about the threshold.
Question 13.
Is it true that for all ?
One can show that for , we have . Consider a bipartite free graph having edges with parts and . Let and . Now replace each vertex with vertices , and each vertex with vertices , so that each edge is replaced by the hyperedge , Let and be the sets replacing and respectively. Clearly, the resulting hypergraph is uniform.
We claim that is Bergefree. Indeed, suppose for a contradiction that is a in the shadow of such that are contained in distinct hyperedges. Since , it is impossible that the vertices of the are all contained in or . Notice that two of the vertices must correspond to the same vertex of , because otherwise would be a in as well. Furthermore, if two adjacent vertices of are in (or in ), then they correspond to the same vertex of . We have the following cases.

If two opposite vertices of , say and , are in , and and are in , then suppose w.l.o.g. that and correspond to the same vertex of . Then and are not contained in distinct hyperedges of , a contradiction.

If two adjacent vertices, say and are in , and and are in , then and correspond to the same vertex of , and so do and . Then and are not contained in distinct hyperedges of .

If three vertices, say , are in , and is in (or viceversa), then correspond to the same vertex of , so and are not contained in distinct hyperedges of .
As , this shows that for .
3 Upper bound — Proof of Theorem 4
First we prove Proposition 2 by showing that is an upper bound for , whenever .
Assume is an uniform hypergraph which contains no Berge. One by one, for every hyperedge we take an edge which has not yet been taken. By our assumption we can always do this, for otherwise we would have a complete , and the corresponding hyperedges would form a Berge. After completing this procedure, we obtain a graph in which the number of edges is equal to the number of hyperedges in . Clearly is free and thus has at most edges, completing the proof. ∎
Another essential tool in some of our proofs is the graph removal lemma. We recall it here without proof.
Lemma 14 (Graph removal lemma).
Let be a fixed graph. For any , there is a such that for every graph which has at most copies of , there exists a set of edges such that every copy of in contains at least one edge from .
We wish to apply the removal lemma to the 2shadow of , denoted . To this end, we prove the following claim.
Claim 15.
Let be a fixed graph, and let and . Let be an uniform hypergraph on vertices with no Berge. Then the number of copies of in is .
Proof.
Any copy of in has at least two edges (and therefore at least three vertices) in some hyperedge of , otherwise the hyperedges containing the edges of would form a Berge. Thus we have the following upper bound:
is considered constant, and by Proposition 2 . So the number of copies of is and so . ∎
From now on, we consider to be a fixed graph, , and . We consider an uniform hypergraph with no Berge.
By Claim 15 and the graph removal lemma, there are edges such that every copy of in the 2shadow of contains one of these edges. Call the set of these edges .
Claim 16.
Every hyperedge of contains an edge from which is contained in at most hyperedges.
Proof.
By contradiction, assume that there is a hyperedge such that every edge from contained in is in at least hyperedges. By the definition of , cannot contain a copy of . Applying Ramsey’s theorem with the edges of colored with the first color and those in colored with the second, we obtain that must contain a copy of . Let be an edge in whose addition would complete this copy of . By our assumption we can select different hyperedges to represent every edge in this copy of : itself for , and other hyperedges containing the rest of the edges. These hyperedges form a Berge in , a contradiction. ∎
4 Linear hypergraphs — Proof of Theorem 6
4.1 Construction showing
First, we show that for any we have . Let . We construct an uniform linear hypergraph on vertices with edges and no Berge. Take sets of vertices each. For each , , let . The hyperedges are the sets of ’s of the form where and .