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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.$