# Upper and lower bounds on the number of certain subsets of the power set

Let $$A$$ be a set with $$n$$ elements. Call a subset $$C$$ of the power set of $$A$$ "good" if

• Each element of $$C$$ has at least three elements.

• If $$P, Q\in C$$ and $$P\cap Q$$ has more than one element, then $$P=Q$$.

I've been interested in finding good upper and lower bounds of the number of good collections, but I haven't made any headway. Does anyone know of any?

Edit: I've gotten some good answers here that tell me that these conditions give too many collections for what I'm trying to do. I'm trying to get an asymptotic formula for the logarithm of the number of isomorphism classes of intervals in weak order of length $$n$$ in a Coxeter group. The weak order intervals are almost distributive lattices, and the basic underlying structure is a partially ordered set (similar to the Birkhoff representation theorem). I think the extra structure characterizing the weak order interval doesn't add anything asymptotically to the logarithm, so I think it is asymptotically $$\frac {n^2}4$$. A collection of this sort in addition to the partially ordered set structure would characterize the isomorphism class, but the conditions I'm giving are very loose. It turns out that the logarithm of the number of these collections is asymptotically bigger than $$n^2$$, so that's no good to get the result I want.

The structure characterizing the weak order interval is the inversion set of the element in the root system. A reduced word for the element is obtained by certain orderings of the inversion set, and the partial ordering arises as the relation that $$x\leq y$$ if $$x$$ comes before $$y$$ in every ordering of the inversion set corresponding to a reduced word. The remaining antichains are then covered by dihedral subsystems corresponding to braid moves in the words, and the ways of arranging these are what I'm trying to count. By default here we assume they are of size $$2$$, hence the restriction to size at least $$3$$. They are intersections of two dimensional subspaces with the inversion set, so if their intersection contains two elements then they are equal. There are very heavy restrictions, for example, if the entire inversion set is an antichain; in that case the inversion set is a direct sum of irreducible finite root systems, which have a very small number of isomorphism classes. I have some ideas for stronger restrictions on the collections using the classification of finite root systems, but nothing that fully characterizes the inversion set so far.

If anyone has any ideas on the more detailed problem, I'd be happy to hear them. I'm not going to invalidate the existing answers though, so I'll leave this as is.

I've done some very small computations on the actual number of isomorphism classes, as I can't think of a good way to do it with a computer. https://oeis.org/A185349. Compare to https://oeis.org/A000112.

• A lower bound is the number of connected (labeled or unlabeled, depending on your interest in collections or collection types) graphs on n points. I suspect the main contribution comes from good collections which have many 2-sets. Gerhard "Pairs Rule The Good Collections" Paseman, 2019.02.02. – Gerhard Paseman Feb 2 at 17:08
• @Gerhard Hmm. Trying to think if there are more than $2^{n^2/4}$ of those. – Matt Samuel Feb 2 at 17:11
• A good collection will partition the set of pairs of n elements. However, these partitions are special, so I am not sure how good a bound results. Gerhard "Hasn't Counted The Special Ones" Paseman, 2019.02.02. – Gerhard Paseman Feb 2 at 18:12
• @Gerhard This makes me realize that I'd really care more about the collections where the first restriction is removed and we add the requirement that the sets have at least three elements. – Matt Samuel Feb 2 at 18:22
• @Gerhard Since nobody has answered the question, it won't invalidate anything if I change it. So here goes. – Matt Samuel Feb 2 at 18:31

Here is a quick and dirty upper bound. Estimate the number of subsets of $$n$$ with three or more elements by $$2^n$$. Any good collection has at most $$n^2/6$$ of these sets since the smallest contains 3 of the $$n$$ choose 2 pairs of elements and no two sets can share a pair. So a good collection can have at most $$2^n$$ choose $$n^2/6$$ possibilities for a subcollection consisting of sets with three or more elements. Multiply this by the fewer than $$2^{n^2}$$ possibilities for collections of subsets of size at most 2, and you get $$2^{n^3}$$ as a weak upper bound.

Gerhard "Leaves The Generalization To You" Paseman, 2019.02.02.

• Oops. I just changed it because there were no answers. You can leave this, if you'd like I can change it back and ask a new question. – Matt Samuel Feb 2 at 18:33
• Actually this contains an answer to the new question too. – Matt Samuel Feb 2 at 18:34
• I'll leave this unchanged. Unless this does not help, I recommend you clean up by adding your own answer and refer to this one. While you are at it, you can tighten up the reasoning and estimates. Gerhard "Prefers Being An Idea Man" Paseman, 2019.02.02. – Gerhard Paseman Feb 2 at 18:39
• This is something I'm trying to apply to an algebraic problem, and most of the good collections won't apply to the problem. I'm trying to find something that characterizes the algebraic structures the logarithm of the number of which is $o(n^2)$. Thanks for your answer. – Matt Samuel Feb 2 at 18:39
• I think I found a characterization with size bounded by $n^{3n}(n!)^2$, which is good enough. Just need to let it sit for awhile to make sure it's right. – Matt Samuel Feb 4 at 19:00

These objects are called linear hypergraphs or partial Steiner systems. However, almost all work on them is confined to the case where the sets (edges, blocks) are all of the same size. This is called $$k$$-uniform.

Let $$H(n,k)$$ be the number of $$k$$-uniform linear hypergraphs on $$n$$ vertices. Then Grable proved $$\log H(n,k) \sim \frac{k-2}{k(k-1)} n^2\log n.$$ See this paper for a fairly simple proof.

I don't know of any similar result when all block sizes are allowed at once, but it could be fruitful to try the same approach.

I have two submitted papers, not yet published, with different coauthors, that obtain precise asymptotics when the number of edges is specified. One is for $$k$$-uniform, $$k=k(n)$$, with $$o(k^{-3}n^{3/2})$$ edges. The other is when the number of edges of each size $$2,\ldots,k$$ is specified, when $$k$$ is fixed and the total number of edges is $$o(n^{4/3})$$. These bounds on the number of edges are not high enough to allow inference of the counts with no restriction on the number of edges.

Here is a better upperbound. Let $$n$$ be given, and choose $$h$$ large so that if one chooses $$h$$ many sets each with $$h$$ or more elements from $$n$$, one cannot choose another set without intersecting one of the other sets in two or more elements. $$(h^2\gt 2n$$ should work.) Then one has at most $$2^n$$ choose $$h$$ possibilities for these largish sets in a good collection. The log of this number is near $$n^{3/2}$$.

Now we need only choose from small sets fewer than $$n^2/6$$ of them. Since $$h$$ is much smaller than $$n$$, there are fewer than $$n$$ choose $$h$$ of these sets. The log for the number of these choices is $$(h \log n)(n^2/6)$$. So we get a better approximation of 2 to the power approximately $$O(n^{5/2}\log n)$$.

Gerhard "Still Looking For Better Bounds" Paseman, 2019.02.02.

• The algebraic structures are partially ordered sets, and the elements of $C$ have to be antichains. There's a lot more going on than that though, because if the partially ordered set is an antichain, then there are very strong restrictions that are well known (the sets are intersections of two dimensional vector subspaces with the positive roots of a finite root system). I'm trying to estimate the logarithm of the number of isomorphism classes, and I think the extra structure adds nothing asymptotically to the logarithm. Every partially ordered set has a trivial structure. – Matt Samuel Feb 2 at 21:34
• Well, I appreciate your extracting sub problems that I can tackle. If you present another version of this with another constraint, I will consider bounds on that. Gerhard "Likes Doing Approximate Upper Bounds" Paseman, 2019.02.02. – Gerhard Paseman Feb 2 at 22:03
• Thanks. For full disclosure, these are inversion sets of elements of Coxeter groups, and the properties I'm abstracting determine the isomorphism class of the lower order ideal of the element in weak order. The set has a partial product operation, and the product is defined if and only if the elements are incomparable. You're only guaranteed that all possible products of at most two elements will exist. If you have a three element antichain, the product of two of the elements could be comparable to the third. But the isomorphism class is determined by the "good" collections and the ordering. – Matt Samuel Feb 2 at 22:11
• My inability to predict when products exist is what is making this hard. If every antichain generated an antichain closed under the product operation, it would be very easy to get the result. – Matt Samuel Feb 2 at 22:14
• A bound of $o(n^2)$ on this would solve the problem. It's quite possible though that this is too loose a condition, and there is no such bound. Then I have to find ways to further restrict it. – Matt Samuel Feb 2 at 22:22

For $$n$$ of the form $$6k+1$$ or $$6k+3,$$ a weak lower bound on the number you want is STS$$(n)$$, the number of Steiner Triple Systems from a set $$A$$ of size $$n$$. Such a system is a family of $$\frac{n(n-1)}6$$ subsets of $$A$$, all of size $$3$$, so that each pair is in exactly one triple. It is known that $$STS(n) \gt \left(\frac{n}{e^2}\right)^{n^2/6}.$$ There are better lower bound on STS$$(n)$$, but the number you want seems as if it should be much larger than STS$$(n).$$

Later With regard to “up to isomorphism”, that would cut the numbers down by a factor of $$n!$$ which is of order $$(\frac{n}{\ln n})^n$$ which wouldn’t drastically change the asymptotics. I’m pretty sure that most systems have no automorphisms so one really would get a reduction of that order, it just doesn’t change things.

Since you mention algebraic structures, I will recall that, given a Steiner Triple System, defining a multiplication by $$xy=z$$ when $$\{x,y,z\}$$ is a triple (and $$xx=x$$) makes $$A$$ into a commutative idempotent quasigroup with the additional property that $$xy=z$$ implies $$xz=y.$$

• Thanks, this tells me that the number is definitely too big. Going to have to try to tighten my definition. (+1) – Matt Samuel Feb 3 at 3:29
• Does the number decrease much if we say two collections are the same if there is a permutation of the set taking one to the other? I would guess not. It seems this rough estimate of what I'm actually counting is too rough. I'm struggling to come up with something to estimate that closely models the situation. I can't really just post what I'm actually trying to count because there are too many axioms for someone to get an estimate without spending a long time trying to understand it. Not really appropriate for a question. – Matt Samuel Feb 3 at 14:43
• It's not just axioms for a collection of sets, it's trying to find isomorphism classes of an algebraic structure. – Matt Samuel Feb 3 at 14:44