A365910 Minimum number of parts in a partition of all 4-subsets of an n-element set such that the intersection of any two subsets from the same part has size at most 1.

1, 5, 15, 18, 35, 42

Offset

4,2

Comments

a(n) >= binomial(n-2,2).

a(n) >= binomial(n,4) / A004037(n).

For n >= 7, a(n) <= (3*n-11) * (n-4).

Links

Table of n, a(n) for n=4..9.

ArtOfProblemSolving et al., What is the best way to partition the 4-subsets of {1,2,3,...,n}?, MathOverflow, 2020.

ArtOfProblemSolving et al., What is the best way to partition the 4-subsets of {1,2,3,...,n}?, Mathematics StackExchange, 2020.

Prog

(Sage) def A365910(n): return Graph([Subsets(n, 4), lambda u, v: u!=v and len(u&v)>1]).chromatic_number()

Crossrefs

Cf. A004037.

Sequence in context: A174598 A022417 A102180 * A045520 A032472 A290551

Adjacent sequences: A365907 A365908 A365909 * A365911 A365912 A365913

Keyword

nonn,hard,more

Author

Max Alekseyev, Sep 23 2023

Status

approved