Abstract
Motivated by the famous theorem of Helly on convex sets of R a, a finite set system ~-is said to have the d-dimensional Helly property if in every subsystem ,N' ~ whose members have an empty intersection there are at most d+ 1 sets with an empty intersection again. We present several results and open problems concerning extremal properties of set systems satisfying the Helly property.
INTRODUCTION AND RESULTS
Let Y be a finite set system with underlying set X. the rank of ~-is max{lFI [Fe~}, and ~-is called a Sperner family if Fc F' implies F= F' whenever F, F'~ W. According to the usual terminology, the sets F~ ~-and the elements x e X will be called the edges and the vertices of the hypergraph ~. Moreover, we shall denote by J~ the collection of/-element sets F~ ~ and put fi := [~J. We use the shorthand r-set (and also r-subset) for r-element (sub)set and sometimes the word r-graph for r-uniform hypergraph. The family of all r-subsets of X and that of all r-sets containing a fixed element y is denoted by X (') and X {r) y respectively.
Solving a problem of Berge [Be77] , the maximum size of a uniform Ha-system was determined by Bollobfis and Duchet in [BD79] (n, r + 1, r) denotes the maximum number of edges in an r-graph on n vertices whose edge set does not contain all r-subsets of any (r + 1)-set (i.e., t (n, r+ 1, r) is the Turdn number for K~+I, the hypergraph with r+ 1 vertices and r + 1 r-element edges). (:) m (n, r, d)= t(n, r + l, r) The maximum number, m(n, r, d) 
of edges in an for r <d for r=d
The structure of extremal hypergraphs is known as well. For r < d and r > d they are unique, being isomorphic to X (r) and y(r) respectively; for r = d each of them is an extremal hypergraph for the Turfin problem hence, for d= 2 they again are unique, being the complete bipartite graphs with [_n/2J and [_(n + 1)/2J vertices in the two vertex classes.
Particular cases of this result were later generalized by Bollobfis and Duchet [BD83] who determined the maximum number of edges in a Sperner-H2-system of given rank, and by the author [T84] proving that the "large" edges (of size >d) in every Sperner-Hd-system o~ satisfy ES, ".-
Some years ago we raised the following stronger conjecture.
Conjecture 1. If ~ is a Sperner-Hd-system on n vertices, then
with equality if and only if ~ is r-uniform for some r (O<~r<<.n), and ]Yl=m (n,r,d On the other hand, using the terminology introduced in [EFK84], Conjecture 1 would imply that the convex hull of the profile vectors of Helly families of any given dimension has just one non-trivial boundary hyperplane.
In one of the main results of this paper we prove Conjecture 1 for Hal-systems under some slight restrictions as follows. Part (i) is a simple extension of (1) and, in fact, it follows by the method described in [T84] without any major changes. Part (ii), however, needs an unusual type of inequality, our Lemma 2, proved in Section 2, where the notion of "external transversals" is introduced. Lastly, (iii) applies (ii) and makes use of the fact that the Turfin numbers are explicitly known for graphs.
To demonstrate the strength of Theorem 2, we note that the main result of [BD83] is an easy corollary to it. Taking into account that m(n,l,2) n, m(n, 2,2)=Ln2/4j, and m(n,i, ~-1 = 2)=(i_1) for i~>3, it is trivial to check that m(n) := maxo~r~<n m(n, r, 2) has the following values: m(n) = n = re(n, 1, 2) for 1 ~< n ~< 3; m(4) = 4 = m(4, 1, 2) = m(4, 2, 2), m(5)=6 = m(5,2,2) = m(5,3,2); and for n~>6, m(n)= (k(,n-ll)/2J)~-m(n, [_n/2J, 2)=m(n, L(n+ 1)/25, 2). Noting that for d=2 the extremal hypergraphs in Theorem 1 are unique for all n and r, we obtain COROLLARY 1 [BD83] . A Sperner-H2-system of rank r >~3 on n >~5 vertices has at most (nk~) edges, where k=min(r-1, Ln/2J). There are precisely two non-isomorphic extremal hypergraphs for r > n/2 if n = 5 or n is even; otherwise the extremal hypergraph is unique.
(k + Those extremal structures are of the form Xy 1); in addition, K2.3 (the complete bipartite graph with 2 and 3 vertices in its vertex classes) and jf~k) are extremal if n=5 resp. n even, r>n/2. We note that Remark2 in [BD83]--claiming that the maximum size of a Sperner-H2-system of rank 2 on n vertices is Ln2/4J--is valid only with the slight restriction n ~> 4, since otherwise there are more 1-sets than edges in the Turfin graph.
Let us formulate another conjecture, an affirmative answer to which would be a considerable step towards the complete solution to Conjecture 1.
Conjecture 2. Let Y be an r-graph on n vertices, not containing K r r+l as a subhypergraph. Then the edges of Y contain at least , distinct (r -1)-sets.
Of course, this inequality is sharp for K~+ L-free hypergraphs of maximum size. If the conjecture is true, then it provides a nice analogue of the Ka68] . It would be interesting to see further variants of that important result for other restricted classes of hypergraphs, too.
Another problem arises when the Sperner property is not assumed. PROBLEM 1. Let two positive integers n and d and a set R = {rl, r2 .... } of natural numbers be given. Determine the maximum number of edges in an H~-system ~ on n vertices, with the property that IF] e R for all Fe Y (i.e., f~¢0 implies i~ R).
Concerning this latter problem, [BD79; M83] solve the cases when R is of the form {il0 ~< i~< r}. Their result is a rather particular case of the following theorem.
THEOREM 3. Let o~ be an Ha-system on n vertices, such that ]F[ ~ R for all F E ~. Then (i) Either of dCR and d+ 1 eR implies
(
ii) If d~ R and ri <~ d for all r~ R, then
I~l~< ~ / \{nl+t(n,d+l,d).
(5)
ri<d \
If d~R, n>~2d+ 1, and either n-d~R or there is an ri~R such
(iii) that d+ 1 <<, ri <~ n/2 + 1, then inequality (4) is valid.
Moreover, in each case (4) and (5) are sharp, and the hypergraph ~'~ verifying equality in (4) is unique for every R that satisfies the requirements of (i) or (iii). Namely, ~ is isomorphic to the collection of all ri-sets (r i < d) and all ri-sets containing the same fixed vertex (ri>~ d), ri~ R.
Note that we cannot expect a unique extremal structure in general; putting d = 3 and R = { 3 ), the value of the Turfin number t(n, 4, 3) is not known, but if the corresponding largest known construction turns out to be best possible, then the number of extremal structures (for Problem 1 as well) grows exponentially with n (see .
Concerning Hal-systems of bounded rank, Bollobfis and Duchet [BD83, Remark 1 ] suggest that perhaps for every fixed r and d, r > d, no SpernerHal-system of rank r on n vertices can have more than (7-~) edges if n is sufficiently large. Our next result shows that this property holds whenever r>~d+ 2. The following two properties are valid for all hypergraphs, not only for uniform ones.
LEMMA 1. Let ~ be a hypergraph with vertex set X. If there is a nonempty collection ~b of automorphisms of Y such that for any (not necessarily distinct) x, y ~ X the number of (~ ~ 45 with qS(x) = y does not depend on the choice of x and y, then for every Z c X, c~(W[Z]) ~> (IZI/[X[) ~(o~).
Proof Fix an independent set Y of cardinality e(~). Choose an automorphism ~b ~ ~0 randomly, with probability ]~1-1. By the assumption on ~b, for every y ~ Y the probability of the event ¢(y)e Z is equal to ]ZI/IX]. Hence, by the additivity of expectation, there is a ~b'e ~ for which the set Y' :=Z~ {~b'(y)ly~ Y} has at least [Yt" [ZI/tX] elements. Under automorphisms, the images of independent sets are again independent, and 
Moreover, equality holds if and only if for some nonnegative Ottegers a and b, the Ai and the Bi are the (a+b) a-subsets and b-subsets, respectively, of an (a+b)-set (and B i is the complement of Aifor i= 1, 2 ..... (a+b)).

PROOFS
We summarize some simple but important properties of Hal-systems in the next lemma, in a form given in [T83] which seems to be the most convenient to use. Its (slightly weaker) variants can be found in [BD79; M83; T84]; the basic ideas behind the different presentations are very similar, however, and therefore we omit the proof.
LEMMA 4. Let ~ be an Hal-system with a vertex set X.
(i) If F~X, F¢~, and IF[ < d, then ~ • {F} is an Hal-system as well (ii) A d-graph is an Hal-system if and only if it does not contain Kd+ t as a subhypergraph. (iii) If Fe~ is an edge maximal under inclusion, and IFI > d, then there is a subset F* ~ F, IF*[ = ]FI -1, such that F* c F' ~ Y implies F'=F.
Throughout, we shall use the *-notation for proper subsets of edges that satisfy the requirements described in (iii) of Lemma 4.
It is worth noting that Lemma 4 almost immediately implies Theorem 1. For r=d this follows by the definition of t(n, d+ 1, d); for r<d one can start with ~ = ~ (which trivially is an Hal-system for every d) and add all r-sets to it one by one. The most interesting case is r > d which we can shortly derive as follows:
Proof of m(n, r, d)<<. (~5~) for r>d. For an r-uniform Hal-system ~ of size m(n, r, d), choose a vertex y and set F(y):= F* for y q~Fe~ and F(y) :=F\{y} for yeFeY.

By the definition of F*, F#F'e~ implies F(y) ~ F'(y). Thus, the F(y) are distinct (r-1)-subsets of an (n-1 )-set, so that their number, m(n, r, d), cannot exceed (~_~). ]
Proof of Theorem 2. Let ~ be a Sperner-Hd-System with an n-element vertex set X. As a first step, we assign an ordered pair (A(F) 
, B(F)) of sets to each Fe~ as follows. For JFI ~<d, let A(F)=F and B(F)=X\.F; for IF[ >d, let A(F)=F* and B(F)=J(\F* (see Lemma4(iii)
). The Sperner property implies that those pairs satisfy the assumptions of Lemma 3, so that (6) yields f~ i + ~ ~< 1.
Moreover, equality in (7) implies that ~ is uniform. This completes the proof of (i).
Suppose next that fd ~ 0 but that all edges of ~ have size at least d (i.e., f~ = 0 for i < d). Denote by ~' the collection of d-subsets of X which are not contained in any Fe Y. Clearly, assigning the pair (F', X\F') to each F'E ~', and putting f' := I~'l, (7) can be strengthened to i=d+l For this reason, our aim is to find a fairly good lower bound on f'.
Consider the (d+ 1)-graph ~ whose vertex set V consists of the d-subsets of X, and whose edges are those (d+ 1)-subsets of V which form hypergraphs isomorphic to K~+ 1 in X. Obviously, every permutation ~ of X induces an automorphism ~b(~) of ~¢~, and the number of permutations taking a d-set F to any d-set F' (also for F'= F) does not depend on the choice of F and F'. Hence, the (non-empty) collection ~b of automorphisms ~b(Tr) satisfies the assumptions of Lemmas 1 and 2.
By Lemma 4(ii), o% is an independent set in ~. What is more, we prove that the set Y'lwhich is disjoint from o%--is an external transversal of o% in ~; i.e., it meets all edges of ~ that intersect O%. Suppose to the contrary that there is a (d+ 1)-set U in X, all of whose d-subsets are contained in some edge F of J~ and that at least one of those edges F belongs to o%. By the Sperner property, no edge of Y contains U, so that for every u ~ U there is an F(u)~ ~ such that U\F(u)= {u}. Of course, F can play the role of F(U\F). In this case, however, any d of the sets F(u) share a vertex in U but the d+ 1 edges have an empty intersection, contradicting the Helly property.
Thus, ~' is an external transversal of O%. Applying Lemma 2 for the independent set O% in ~,~, we obtain
By definition, ~(~) = t(n, d+ 1, d) and ~(~) = (~)-~(Jt~), so that
Thus, (f' +f~)>~fd (~)/m(n, d, d) , and substituting into (8) we obtain (2). It follows from Lemma 3 that ~,~ is uniform whenever equality holds.
To prove (iii), let d= 2. If o~ contains no edge of a single vertex, then (ii) implies (2). Otherwise, we apply induction on n. If, say, {x} e~, then ~\{x} is an Hd-system on just n--1 vertices (by the Sperner property), and therefore
It is trivial to check that n.m(n-1, r, 2)~< (n-1).m(n, r, 2) holds for all r~>l (and all n~>2), with strict inequality when r~>2 (recall that m(n,l, 2)=n, m(n, 2,2)=[ n2/4_], and m(n,i, 2)=('~2~) for i~>3); thus, multiplying both sides of (9) by (n-1)/n and adding 1/n, we obtain (2). I (4) when d6R.
Proof of Theorem
Moreover, uniqueness of the extremal structure in those cases follows from the fact that an r-uniform Hal-system with (~_-]) edges (r > d) consists of all r-sets containing a fixed vertex, and two such systems together can form an Hal-system only if the fixed vertex is the same in both of them. Hence, from now on we suppose that d is an element of R, and prove (4) under the assumptions of (i) and (iii). Note that the bounds on m (n, r, d) allow us to assume that R consists of precisely two elements, d and r (r > d). Now the simplest proof of (i) is to say that the d-sets F*, defined for the edges F~ ~+ 1, are distinct from each other and also from the edges of ~ (by definition); therefore Io~] + [~+11 ~<(~), implying (4). Uniqueness of the extremal hypergraph can be proved, e.g., by an argument given at the end of [BD833.
Proof of (iii) for n-deR. Let R={d,r}, d<r=n-d. I~I + I~'l + I~"1 4, d
To prove uniqueness of the extremal structure, we first note that in the case of equality there must be precisely (~) colored d-sets, and each Y (I YI =2d+ 1) must contain precisely (2a+1~ of them. We show that this Proof of (iii) (0) is not a subset of any F' (F¢F' ~), and F(0) is minimal under inclusion, with respect to these properties. (The choice of F* ensures the existence of such an F(0).) We claim that F(0) contains no edge of as a subset. Indeed, otherwise, for every x ~ F(0) there is an F x E ~ such that F(0)\Fx= {x} (by the mimimality of F(0)). Hence, if some F'e/Ta were contained in F(0), then the subhypergraph {F'}w{FxtxeF(O)} would not satisfy the Helly property. Now we apply the Ka68] in the weaker but simpler form due to Lov~sz [Lo 79, 13.31(b) ], stating that if a q-graph has (q) edges (u ~> q arbitrary real), then its edges contain at least (p) distinct p-sets for any p ~< q. (A short proof of both versions was given by Frankl [F84] .) Observe that (q)--(qUl) is a monotone increasing function of u for u >~ 2q--1. Hence, the following result is valid, too:
Any (q)-t sets of cardinality q (u >~ 2q-1, t >~O) contain at least (q u i ) -t sets of cardinality q -1.
Let ~(0) be the hypergraph formed by the sets F(0). Their definition implies that ~(0) is a Sperner family. Since Ig(0)l = 141 <<.re(n, r, d)= (~_-~), we can put to = ("r--~)--lY(0)I, and define tk=to+ [~(0)l, tk+i = tk + I~+ 1(0)I .... , tr 2 = tr 3 + 14_2(0)t. Applying the above statement for u=n-1, q=r-1, and t=t,_2, we obtain that the edges of ~r--l(0) contain at least (r'-2)_trl 2 (r-2)-sets. Adding those sets to "~r 2(0), this new (r--2)-graph has at least ("r--~)--tr 3 edges, so that it covers at least (~-~)-tr_3 sets of size r-3. The repeated application of this argument yields that the edges of @(0) contain at least ("d~)-to distinct d-sets which, by the definition of @(0), do not belong to ~. Consequently, n n 1 n i
I~l~<(d)-(~)+t0
and I~l=lo~/+l~l~<(~_a)+( ,, 1). To prove the uniqueness of the extremal structure, observe that the F* must be all the /-subsets of an (n-1)-set--for some/--if equality holds in the Kruskal-Katona theorem. Thus, in this case I~[~<(~ I) (with (n--I (r--1)n--1 n >~2r-2 is equality, of course), and 141 ~<maxdz~zr_~, ~ )= as assumed. Since 141 ~ 1 = (r l) implies that all edges of size r contain a fixed vertex, the extremal Ha-system is unique up to isomorphism. II
n --i ] ( n --1 ] n
Proof of Theorem 4. (i) The assumptions imply (r, l~>~d+l,~>(d), SO that on the left-hand side of (7), fr, has the largest denominator.
(ii) Applying the trivial upper bound t(n, d+ 1, d)<~ (d/(d+ 1))(~), the assumptions imply that t(n, d+ 1, d)~< ("d~) holds, so that on the left-hand side of (2), the denominator off~ is largest for i= r in the'range O<~i<~r. I
CONCLUDING REMARKS
At the end of this paper we raise some further problems concerning extremal properties of Hal-systems. First, recall the "missing cases" of Theorem 2 which lead to the following questions.

{'paper_id': '39928925', 'title': 'Helly property in finite set systems', 's2_url': 'https://api.semanticscholar.org/CorpusID:39928925', 'source': 'S2ORC'}