VOOZH about

URL: https://oeis.org/A390645

⇱ A390645 - OEIS


login
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.
0
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
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
Sequence in context: A049980 A359897 A384886 * A209698 A141525 A209764
KEYWORD
nonn,tabl,more
AUTHOR
Elijah Beregovsky, Dec 21 2025
STATUS
approved