of 6
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

A sharp lower bound on the number of hyperedges in a friendship 3-hypergraph

Category:

School Work

Publish on:

Views: 54 | Pages: 6

Extension: PDF | Download: 0

Share
Description
AUSTRALASIAN JOURNAL OF COMBINATORICS Volume , Pages 7 78 A sharp lower bound on the number of hyperedges in a friendship -hypergraph P. C. Li G. H. J. van Rees Department of Computer Science University
Transcript
AUSTRALASIAN JOURNAL OF COMBINATORICS Volume , Pages 7 78 A sharp lower bound on the number of hyperedges in a friendship -hypergraph P. C. Li G. H. J. van Rees Department of Computer Science University of Manitoba Winnipeg, Manitoba RT 2N2 Canada Abstract Let X, B be a set system in which B is a set of -subsets of X. Then X, Bisafriendship -hypergraph if it satisfies the following property: for all distinct elements u, v, w X, there exists a unique fourth element x X such that {u, v, x}, {u, w, x}, {v, w, x} B. The element x is called the completion of u, v, w and we say u, v, w is completed by x. If a friendship -hypergraph contains an element f X such that {f,u,v} Bfor all u, v X \{f}, then the friendship -hypergraph is called a universal friend -hypergraph and the element f is called a universal friend of the hypergraph. In this note, we show that if X, B is a friendship -hypergraph with X = n, then B 2n 1n 2/. In addition, we show that this bound is met if and only if X, B is a universal friend -hypergraph. 1 Introduction Let X, B be a set system in which B is a set of -subsets of X. Then X, B isa friendship -hypergraph if it satisfies the following property: for all distinct elements u, v, w X, there exists a unique fourth element x X such that {u, v, x}, {u, w, x}, {v, w, x} B. The element x is called the completion of u, v, w and we say u, v, w is completed by x. If a friendship -hypergraph contains an element f X such that {f,u,v} B for all u, v X \{f}, then the friendship -hypergraph is called a universal friend -hypergraph and the element f is called a universal friend of the hypergraph. The members of B are called hyperedges while we reserve the term Research supported by NSERC-RPGIN Corresponding author; Research supported by NSERC- RPGIN 74 P.C. LI AND G.H.J. VAN REES Figure 1: The universal friend -hypergraph on eight points Figure 2: The non-universal friend -hypergraph on eight points triple for three elements that may or may not be a hyperedge. When writing out hyperedges in friendship -hypergraphs we omit brackets and commas. Friendship hypergraphs were introduced by Sós [2]. She observed that if n 2, 4 mod 6, then there exists a universal friend -hypergraph. Such a hypergraph must be constructed from a Steiner Triple System in the following manner: start with a Steiner Triple System Y,Aonn 1 1, mod 6 elements. Then introduce a new element f Y to form the universal friend -hypergraph, X, B, where X = Y {f} and B = A {{f,x,y} : x, y X, x y}. Clearly f is the universal friend. Figure 1 gives a universal friend -hypergraph on eight points with universal friend 0. In [1], Hartke and Vanderbussche showed that friendship -hypergraphs without a universal friend exist. Such hypergraphs are called non-universal friend - hypergraphs. They showed that there is exactly one such hypergraph when n =8, at least three when n = 16 and at least one when n = 2. They also showed that any friendship -hypergraph must have at least 1 nn 2 hyperedges. In [], Li, van 2 Rees, Seo and Singhi showed that the known friendship -hypergraphs on less than 1 points are the only such hypergraphs. They also proved that that the number of hyperedges in a friendship -hypergraph on n points, is at least n 2 /2. Figure 2 shows the non-universal friend -hypergraph on eight points. We will improve the lower bound for hyperedges in a friendship -hypergraph to B 2n 1n 2/. We will also show that the universal friend -hypergraph meets this bound and no other friendship -hypergraphs meet this bound. Therefore this bound is met if and only if n 2, 4mod6. 2 A new lower bound In this section, we will show that if X, B is a friendship hypergraph on n points, then B 2n 1n 2/. The proof will follow from Proposition 2 of [1]. Before we proceed, we state two useful observations from [1]. HYPEREDGES IN A FRIENDSHIP -HYPERGRAPH Every pair of points from X occurs together in at least one member of B, and 2. every hyperedge must be contained in a unique K4, the complete -hypergraph on four points. From the second observation, it is simple to deduce that B can be partitioned into copies of K4. In Figures 1 and 2, each column consists of the hyperedges that are in the same K4. Theorem 2.1 If X, B is a friendship -hypergraph, then B 2 n 1n 2. Proof Let a X. As in [1], we partition the hyperedges into three sets: 1. Let E 2 be the graph consisting of the edges formed by taking all hyperedges containing element a, and removing element a. 2. E A consists of the hyperedges that are contained in a K 4 with the element a.. E B consists of the remaining hyperedges. Note that hyperedges containing a and the hyperedges in E B can both be partitioned into copies of K4. To get a lower bound on B, we will compute a lower bound for E 2 + E A + E B. As in [1], we first prove that each xyw E A is counted three times. If xyw E A, then the vertices x, y, w, a form a K4, and each vertex of the K 4 is the completion for the other three. So xyw is counted for all three pairs xy, yw and xw. Since xyw E A only if xy, yw, xw E 2,then E A = 1 E 2. The key to getting a better lower bound is to carefully consider E B. There are n 1 E2 pairs xy that do not occur in E 2 2.Letxy be such a pair and let a be as above. Consider a, x, y and the element u that completes them. By definition, there must be hyperedges axu, ayu and uxy. Nowhyperedgeuxy must be in E B.When this occurs, we say that the triple a, x, y is finished by the K4 that contains the hyperedge uxy. Note that only one K4 can finish a triple a, x, y. We claim that at most three triples of the form a, x, y, where xy E 2 can be finished by any given K4 of E B. To see this, let a, x, y be a triple finished by a K4 of E B. Let this K4 consist of the hyperedges uxy, wxy, uwx, uwy. Then the completion of a, x, y must be either u or w. Without loss of generality, suppose it is u. Then there are hyperedges axu, ayu and xyu in X, B, where xu and yu are in E 2 and hyperedge xyu must be in E B. That leaves only pairs uw, wx and wy in the K4 that have not been assigned to E 2 or its complement. If three more triples of the form a, x, y where xy E 2 are finished by this K4, then these triples must be a, w, x; a, w, y and a, u, w. This implies that wx, wy, uw E 2. But this is impossible, since a, w, x must be completed by element u or y. If it completed by u, thenuw E 2, which is a contradiction. Similarly, if it is completed by y, thenwy E 2, which is also a contradiction. Therefore, each K4 can finish at most three triples of the form a, x, y where xy E 2. This implies that there 76 P.C. LI AND G.H.J. VAN REES must be at least n 1 E2 / K 2 4 sineb, or equivalently EB 4 n 1 E2. 2 Then we have E 2 + E A + E B E E n 1 E2 = 2n 1n 2. 2 We point out that if the above bound is met, and a hyperedge xyz is in E B and xyz istheedgeusedbythek4 containing it to finish the triple a, x, y where xy E 2, then yz and xz are in E 2 and therefore, the hyperedge xyz canbeusedbythek4 to finish exactly one pair xy in this case not in E 2. In addition, each K4 in E B must finish exactly three triples of the form a, x, y, where xy E 2, if the above bound is to be met. Lemma 2.2 Let X, B be a friendship -hypergraph with B = 2 n 1n 2 hyperedges. Let a be an element of X, andlete 2 be defined as in Theorem 2.1. If xy E 2, then the pair xy occurs in exactly two hyperedges in the friendship - hypergraph. Proof In the proof of the previous theorem, if the lower bound is attained then every K4 in E B must finish three triples of the form a, x, y where a is used to define E 2 and xy E 2. In order to get a contradiction let some pair 12 / E 2 be in more than 2 hyperedges; i.e., 12 is in at least two K4 s. We will now use the observation immediately after the proof of Theorem 2.1. Let 124 and 1256 be two K4sinE B containing pair 12. Let one of the hyperedges, say 12 be used by 124 to finish the triple a, 1, 2. Now consider the hyperedges 125, 126 in the other K4. If 125 is used by 1256 to finish some triple a, x, y, where xy E 2, then this implies xy =15or xy = 25. In either case, this would imply that 12 E 2, which is a contradiction. The same holds for 126. Therefore, a pair like xy / E 2 can not occur in more than one K4 in EB and so can and must occur in exactly two hyperedges in the friendship -hypergraph. Suppose we have a friendship -hypergraph with B = 2 n 1n 2 hyperedges and a pair xy that does not occur with some element z X \{x, y}. Then choosing the element z to construct E 2 shows that the pair xy E 2, and therefore by Lemma 2.2, occurs in exactly two hyperedges of the friendship hypergraph. So we have the following observation: Any pair of elements xy in this situation occurs in either n 2 hyperedges or two hyperedges of the friendship hypergraph. We now show that if 4 n 1 2 is an integer and X, B is friendship hypergraph on X = n elements having 4 n 1 2 hyperedges, then X, B must be the universal friend hypergraph. Theorem 2. If 4 n 1 2 is an integer and X, B is friendship hypergraph on X = n elements having 4 n 1 2 hyperedges, then X, B must be the universal friend hypergraph. Consequently, n 2, 4mod6. Proof By the remark after Lemma 2.2, we know that a pair of points occurs exactly 2orn 2 times in the friendship -hypergraph. Let α denote the number of pairs that HYPEREDGES IN A FRIENDSHIP -HYPERGRAPH 77 appear in exactly 2 hyperedges, and let β denote the number of pairs that appear in exactly n 2 hyperedges. Then, by counting pairs and total occurrence of pairs in the friendship -hypergraph, we have the following set of linear equations: n α + β = 2 and 2α +n 2β = 2 n 1n 2. Solving for α and β, we get the unique solution of α = n 1 2 and β = n 1. Therefore, the hypergraph must contain n 1 2 pairs that occur in exactly two hyperedges and n 1 pairs that occur in exactly n 2 hyperedges of the hypergraph. By the pigeonhole principle, there are two pairs, each occurring n 2 times in the hypergraph, that have a common element. Without loss of generality, suppose the pairs 12 and 1, each occur in n 2 hyperedges of the hypergraph. Then the hyperedges 12, 124,...,12n and 14, 15,...,1n are in the hypergraph. Note that if the pair 14 occurs more than 2 times then it must occur n 2 times. But then every other pair containing 1 must also occur more than 2 times and so occurs n 2 times. Then we see that all pairs containing element 1 occur n 2 times, giving the universal friend hypergraph where element 1 is the universal friend. So suppose the pair 14 occur exactly two times. We will show that this leads to a contradiction. We proceed to show that the pair 2 cannot occur n 2 times in the hypergraph given that pairs 12 and 1 occur n 2 times. To see this, suppose that 2 does occur n 2 times in the hypergraph. Then the hyperedges 12, 24, 25,...,2n must be in the hypergraph. Since the hyperedges 12, 124, 14, 24 are in the hypergraph, 124 is a K4 in the hypergraph. In addition, the hyperedges 12, 125, 15, 25 are also in the hypergraph implying 125 is a K4. This contradicts observation 2 on Page 2. Let ij be a pair of elements where i, j {1, 2, }. Suppose that the pair ij occurs in n 2 hyperedges in the hypergraph. Note that the hyperedges 12i, 12j, 1ij and 2ij are in the hypergraph. In addition, the hyperedges 1i, 1j, 1ij and ij are in the hypergraph. These two facts imply that 12ij and 1ij are K4s in the hypergraph which contradicts the fact that the K4 s in a friendship hypergraph must be disjoint. Therefore the ij pairs must occur in exactly two hyperedges of the hypergraph. Notice we have not handled pairs of the form i where 4 i n. Suppose some pair i for 4 i n occurs in n 2 hyperedges of the hypergraph. Then 2i must be one of these hyperedges. As the pair 2 occurs in exactly two hyperedges see the paragraph before the previous paragraph and it occurs in 12 and 2i, thenno other pair j where j i, j 4 occur in a hyperedge with element 2. This means that these pairs j must occur in exactly two hyperedges of the hypergraph. So, we have shown that at most one pair of the form i for 4 i n mayoccurinn 2 hyperedges. By symmetry, at most one pair of the form 2i for 4 n may occur in n 2 hyperedges of the hypergraph. That means there are at most 4 pairs that occur n 2 times in the hypergraph. But that contradicts the fact that there must be exactly n 1suchpairs. 78 P.C. LI AND G.H.J. VAN REES Acknowledgements We would like the thank the referees for their careful reading of the paper and their suggestions which improved the clarity of this paper. References [1] S. G. Hartke and J. Vandenbussche, On a question of Sós about -uniform friendship hypergraphs, J. Combin. Des , [2] V. T. Sós, Remarks on the connection of graph theory, finite geometries and block designs, in: Colloquio Internationale sulle Teorie Combinatorie Roma, 197, Tomo II, Atti dei Convegni Lincei, No. 17, Acad. Naz. Lincie, Rome, [] P. C. Li, G. H. J. van Rees, Stela H. Seo and N. M. Singhi, Friendship -Hypergraphs, Discrete Math , Received 15 May 2012
Similar documents
View more...
Search Related
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks