Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: On the shadow of squashed. | On the shadow of squashed families of k-sets Frederic Maire maire@f Neurocomputing Research Center Queensland University of Technology Box 2434 Brisbane Qld 4001 Australia Abstract The shadow of a collection A of k-sets is defined as the collection of the k 1 -sets which are contained in at least one k-set of A. Given A the size of the shadow is minimum when A is the family of the first k-sets in squashed order by definition a k-set A is smaller than a k-set B in the squashed order if the largest element of the symmetric difference of A and B is in B . We give a tight upper bound and an asymptotic formula for the size of the shadow of squashed families of k-sets. Submitted January 15 1995 Accepted August 25 1995. AMS Subject Classification. 04A20 03E05 05A20. 1 Introduction A hypergraph is a collection of subsets called edges of a finite set S. If a hypergraph A is such that Ai Aj 2 A implies Aị 2 Aj then A is called an antichain. In other words A is a collection of incomparable sets. Antichains are also known under the names simple hypergraph or clutter. The shadow of a collection A of k-sets set of size k is defined as the collection of the k 1 -sets which are contained in at least one k-set of A. The shadow of A is denoted by A A . In the following we assume that S is a set of integers. The squashed order is defined on the the set of k-sets. Given two k-sets A and B we say that A is smaller than B in the squashed order if the largest element of the symmetric difference of A and B is in B. The first 3-sets in the squashed order are 1 2 3 1 2 4 1 3 4 2 3 4 1 2 5 1 3 5 . Let Fk x denote the family of the first x k-sets in the squashed order. We will prove the following. THE ELECTRONIC .JOURNAL OF COMBINATORICS 2 1995 R16 2 Theorem 1 If x then A Fk x kx - x x - 1 X Qntk where k n -1 n k n k 1 Equality holds when x 0 or x 0 Theorem 2 When x 1 A Fk x -p x1 k The squashed order is very useful when dealing with the size of the shadow of a collection .
