[seqfan] Re: Antichains and RAM
israel at math.ubc.ca
israel at math.ubc.ca
Mon May 11 15:56:53 CEST 2020
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/
>
>
More information about the SeqFan
mailing list