A390645 Triangle read by rows: T(n,r) is maximal such that there exists a family F of subsets of {1,...,n} of size T(n,r) such that the intersection of no two sets in F has r elements.

1, 1, 2, 2, 3, 4, 4, 4, 7, 8, 8, 6, 11, 15, 16, 16, 11, 16, 26, 31, 32, 32, 23, 22, 42, 57, 63, 64, 64, 45, 37, 64, 99, 120, 127, 128, 128, 94, 67, 93, 163, 219, 247, 255, 256, 256, 187

Offset

0,3

Comments

For fixed r and n(r) sufficiently large Frankl and Füredi proved that T(n,r) is maximized by taking F such that for all A in F: |A| > (n+r)/2 or |A| < r when n+r is odd, and|A\{1}| >= (n+r)/2 or |A| < r when n+r is even.

Earlier Frankl proved that for r=1 and all n>3.

Links

Table of n, a(n) for n=0..46.

Thomas Bloom, Problem #703, Erdős Problems.

Péter Frankl, An intersection problem for finite sets, Acta Math. Acad. Sci. Hungar. (1977), 371-373.

Péter Frankl and Zoltån Füredi, On hypergraphs without two edges intersecting in a given number of vertices, J. Combin. Theory Ser. A (1984), 230-236.

Péter Frankl and Vojtěch Rödl, Forbidden intersections, Trans. Amer. Math. Soc. (1987), 259-286.

Formula

T(n,0) = 2^(n-1).

T(n,1) = A045621(n+1) + 1 for n > 3.

T(n,n) = 2^n.

T(n,n-1) = 2^n - 1.

T(n,n-2) = A000295(n) for n > 2.

Example

The triangle begins:
  1,
  1,  2,
  2,  3,  4,
  4,  4,  7,  8,
  8,  6,  11, 15, 16,
  16, 11, 16, 26, 31, 32,
  32, 23, 22, 42, 57, 63,  64,
  64, 45, 37, 64, 99, 120, 127, 128...

Mathematica

T[n_, r_]:= Length[FindClique[RelationGraph[DigitSum[BitAnd[#1, #2], 2]!=r&, Range[2^n]]][[1]]];

Crossrefs

Cf. A000295, A045621.

Sequence in context: A049980 A359897 A384886 * A209698 A141525 A209764

Adjacent sequences: A390642 A390643 A390644 * A390646 A390647 A390648

Keyword

nonn,tabl,more

Author

Elijah Beregovsky, Dec 21 2025

Status

approved