Generalized degrees and densities for families of sets

Details Generalized degrees and densities for families of sets Generalized degrees and densities for families of sets

1994-11-08

arxiv.org/abs/math/9411220v1

Mathematics

Combinatorics

106 pages

Scientific paper

Let F be a family of subsets of {1,2,...,n}. The width-degree of an element x in at least one member of F is the width of the family {U in F | x in U}. If F has maximum width-degree at most k, then F is locally k-wide. Bounds on the size of locally k-wide families of sets are established. If F is locally k-wide and centered (every U in F has an element which does not belong to any member of F incomparable to U), then |F| <= (k+1)(n-k/2); this bound is best possible. Nearly exact bounds, linear in n and k, on the size of locally k-wide families of arcs or segments are determined. If F is any locally k-wide family of sets, then |F| is linearly bounded in n. The proof of this result involves an analysis of the combinatorics of antichains. Let P be a poset and L a semilattice (or an intersection-closed family of sets). The P-size of L is |L^P|. For u in L, the P-density of u is the ratio |[u)^P|/|L^P|. The density of u is given by the [1]-density of u. Let p be the number of filters of P. L has the P-density property iff there is a join-irreducible a in L such that the P-density of a is at most 1/p Which non-trivial semilattices have the P-density property? For P=[1], it has been conjectured that the answer is: "all" (the union-closed sets conjecture). Certain subdirect products of lower-semimodular lattices and, for P=[n], of geometric lattices have the P-density property in a strong sense. This generalizes some previously known results. A fixed lattice has the [n]-density property if n is large enough. The density of a generator U of a union-closed family of sets L containing the empty set is estimated. The estimate depends only on the local properties of L at U. If L is generated by sets of size at most two, then there is a generator U of L with estimated density at most 1/2.

Affiliated with

Also associated with

No associations

Rating

Generalized degrees and densities for families of sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generalized degrees and densities for families of sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalized degrees and densities for families of sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-230448