[seqfan] Re: Antichains and RAM
Brendan McKay
Brendan.McKay at anu.edu.au
Mon May 11 16:09:36 CEST 2020
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/
More information about the SeqFan
mailing list