login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Maximum number of 4-subsets of an n-set such that every 3-subset is covered at most twice.
0

%I #22 Oct 18 2022 13:05:02

%S 2,5,9,15,28,40,60,80,108,143,182,225,280,340,405

%N Maximum number of 4-subsets of an n-set such that every 3-subset is covered at most twice.

%C Maximum number of K_4^3's that can be packed in a doubled K_n^3, where K_n^m is the complete m-uniform hypergraph on n vertices.

%H Richard K. Guy, <a href="/A001197/a001197.pdf">A problem of Zarankiewicz</a>, Research Paper No. 12, Department of Mathematics, University of Calgary, January 1967. [Annotated and scanned copy, with permission]

%H Haim Hanani, <a href="https://doi.org/10.4153/CJM-1960-013-3">On quadruple systems</a>, Canadian Journal of Mathematics, 12 (1960), 145-157.

%H Jeremy Tan, <a href="https://arxiv.org/abs/2203.02283">An attack on Zarankiewicz's problem through SAT solving</a>, arXiv:2203.02283 [math.CO], 2022.

%F a(n) >= 2*A001843(n). Equality holds if n = 6k+2 or 6k+4 (Hanani).

%e a(6) = 9 because of the following optimal collection of 4-subsets:

%e 1 2 3 4

%e 2 3 4 5

%e 3 4 5 6

%e 4 5 6 1

%e 5 6 1 2

%e 6 1 2 3

%e 1 2 4 5

%e 2 3 5 6

%e 3 4 6 1

%Y Cf. A001839-A001843 for other packing sequences discussed in _Richard K. Guy_'s paper.

%K nonn,hard,more

%O 4,1

%A _Jeremy Tan_, Jan 31 2022