[seqfan] Re: Antichains and RAM

[Brendan McKay]

Thanks. It matches my construction, which shows that for n even
the optimum solution can be either uniform or non-uniform.

I have updated A305857 and A305855 for n=7.  It took about 12
CPU-hours.  The case n=8 would take years and I'm not going to try.

B/

On 11/5/20 11:56 pm, israel at math.ubc.ca wrote:
> See Anderson, Combinatorics of Finite Sets, Cor. 5.3.3 : If A is an 
> intersecting antichain of subsets of an n-set, then |A| <= binomial(n, 
> floor(n/2)+1). References are to Brace and Daykin in 1972 and 
> Schonheim in 1974.
>
> Cheers,
> Robert
>
>
> On May 11 2020, Brendan McKay wrote:
>
>> 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/
>>
>> -- 
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>>
>
> -- 
> Seqfan Mailing list - http://list.seqfan.eu/