login
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

%I #31 Sep 25 2023 08:44:42

%S 1,5,15,18,35,42

%N 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.

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

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

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

%H ArtOfProblemSolving et al., <a href="https://mathoverflow.net/q/363026">What is the best way to partition the 4-subsets of {1,2,3,...,n}?</a>, MathOverflow, 2020.

%H ArtOfProblemSolving et al., <a href="https://math.stackexchange.com/q/3717109">What is the best way to partition the 4-subsets of {1,2,3,...,n}?</a>, Mathematics StackExchange, 2020.

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

%Y Cf. A004037.

%K nonn,hard,more

%O 4,2

%A _Max Alekseyev_, Sep 23 2023