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

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

Offset

4,1

Comments

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.

Links

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

Richard K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Department of Mathematics, University of Calgary, January 1967. [Annotated and scanned copy, with permission]

Haim Hanani, On quadruple systems, Canadian Journal of Mathematics, 12 (1960), 145-157.

Jeremy Tan, An attack on Zarankiewicz's problem through SAT solving, arXiv:2203.02283 [math.CO], 2022.

Formula

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

Example

a(6) = 9 because of the following optimal collection of 4-subsets:
  1 2 3 4
  2 3 4 5
  3 4 5 6
  4 5 6 1
  5 6 1 2
  6 1 2 3
  1 2 4 5
  2 3 5 6
  3 4 6 1

Crossrefs

Cf. A001839-A001843 for other packing sequences discussed in Richard K. Guy's paper.

Sequence in context: A176691 A339554 A274355 * A054253 A045649 A267694

Adjacent sequences: A351097 A351098 A351099 * A351101 A351102 A351103

Keyword

nonn,hard,more

Author

Jeremy Tan, Jan 31 2022

Status

approved