[seqfan] Re: Antichains and RAM

Brendan McKay Brendan.McKay at anu.edu.au
Mon May 11 12:23:44 CEST 2020


Hmmmm, fix an element u of U.  Take all the subsets of size n/2 that 
include u,
and all the subsets of size n/2+1 that don't include u.  It comes to
(n/(n+2)) binomial(n,n/2) subsets altogether.  I don't know if this is 
best possible,
but I know it isn't possible to reach binomial(n,n/2).

Brendan.

On 11/5/20 7:00 pm, Brendan McKay wrote:
> 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/
>
> -- 
> Seqfan Mailing list - http://list.seqfan.eu/



More information about the SeqFan mailing list