[seqfan] Re: Antichains and RAM
Brendan McKay
Brendan.McKay at anu.edu.au
Mon May 11 11:00:47 CEST 2020
I will add a(7) for A305857 and A305855 shortly.
The case of a(8) will be substantially more difficult. A relevant
question is the following:
Given a universal set U of size n, what is the maximum number of
non-empty subsets
of U such that none of the subsets is contained in another and each pair
of the subsets
has non-empty intersection?
In the case that n is odd, the answer is binomial(n,(n+1)/2) with the
unique solution
being all the subsets of size (n+1)/2.
I don't know the answer for n even. A lower bound is binomial(n,n/2)/2
since one
can take all the subsets of size n/2 that contain a fixed element of U.
Is it possible
to do better? This is surely known.
Brendan.
On 11/5/20 5:34 pm, Elijah Beregovsky wrote:
> Tim, thank you for the time spent!
>
> I’d thought about the isomorphism you propose, but I couldn’t come up with any way to use it to speed up computations. There are loads of sequences on the OEIS, though, that count the equivalence classes. https://oeis.org/A305857, or https://oeis.org/A305855, for example. You could maybe extend some of them with your program.
> Best,
> Elijah
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list