Let $ \mathcal{T}= \{A \subset \{1,2,\ldots,9 \} \ ; \ |A|=5 \}$. Find $n_{\min}$...

Question

Let $ S=\{1,2,\ldots,9 \}$ and $ \mathcal{T}= \{A \subset S \ ; \ |A|=5 \}$. Find the minimum value of $n$ such that for any $ \mathcal{U} \subset \mathcal{T} $ with $|\mathcal{U}|=n$ there exist two sets $A,B \in \mathcal{U}$ so that $ |A \cap B|=4$.

Let $\mathcal{F}=\{A_1,A_2,\ldots,A_k\} \subset \mathcal{T}$ be a family of $5$-element subsets of $S$ such that: $$|A\cap B|\leq 3\;\;\;\;\;\;\forall A,B \in \mathcal{F}, A\neq B$$ Now we are interested in $k_{\max}$.

Make a following bipartite graph. Connect $A_i$ with a $4$-element subset $B\subset S$ if and only if $B\subset A_i$.

Then the degree of any $B$ is at most $1$, while the degree of each $A_i$ is $ {5\choose 4}=5$. So we have $1\cdot {9\choose 4}\geq 5 \cdot k$, and so $k\leq 25$. Thus the partial answer is $n_{min}\leq 26$.

Now I don't know how to find a configuration for $n=26$. If I understand we are searching for Steiner system $S(4,5,9)$?

Answer 1

Continuing the thread in my comment above, I did a computer search for a counterexample using this Python implementation of Algorithm X. I found no solutions. You can run the program yourself here. To help convince you I coded everything correctly, I used the same algorithm to find $S(5,6,12)$ by brute force. You can play with the code to see it find/not find $S(k-1,k,n)$ for other values of $k,n$, and verify this agrees with the (non)existence of Steiner $k$-tuple systems for your chosen $n$.

In short, I think $n_{\text{min}}\le 25$.

Answer 2

The question admits two interpretations from well-studied topics, see the references.

The first is combinatorial, concerning $A(n, d, w)$, which is the maximal possible number of binary vectors of length $n$, (Hamming) distance at least $d$ apart, and constant weight (that is, the number of $1’$s) $w$. It is also related with $A(n, d)$, the maximal possible number of binary vectors of length $n$ and distance at least $d$ apart (with no restriction on weight). Now we see that $k_{\max}=A(9,4,5)$. This value (18) was known already in 1990, see, for instance, [BSSS, Table I-A]. Before I found this reference, my program based on a random choice computed a few maximal systems of size 18 of binary vectors of length $9$, weight $5$, and distance at least $4$ between any two distinct vectors, see below. Another proof of their optimality follows from an observation that $A(9,4)=20$ [Be] and that when we add to any such system binary vectors $(0,\dots,0)$ and $(1,\dots,1)$ we obtain a system of $20$ binary vectors of length $9$ and distance at least $4$ apart. Remark that Hougardy has found that there are only two non-equivalent even $(9,4)$ codes of the maximal size $20$ ([Z, p.10]).

The second topic belongs to graph theory considering so-called uniform subset graphs. Namely, a uniform subset graph $G(n,k,r)$ has a vertex-set consisting of all $k$-element subsets of the set $[n]$ and any two vertices $v$ and $u$ of $G$ are adjacent iff $|v\cap u|=r$. Then $k_{\max}=\alpha(G(9,5,4))$ is the independence number of the graph $G(9,5,4)$. This is a special case of a uniform subset graphs for which $r=k-1$. It is called a Johnson graph $J(n,k)$. According to [ACLR], “The Johnson graphs have been studied from several approaches, see for example [A, R, T]. In particular, the determination of the exact value of the independence number $\alpha(J(n, k))$ of the Johnson graph, as far as we know, remains open in its generality, albeit it has been widely studied [Br, BE$_2$, BE, J, MPP]”.

xx...x.xx  x.x.x.x.x  x.x.xx..x  .xx.x.xx.  .x..xxxx.  .xx.xx.x.
xx.xx..x.  .x.x.x.xx  xxx....xx  xx.x.xx..  ..x.xxx.x  x.x.xxx..
x.x..xx.x  .xxxxx...  x.xxx.x..  x..xxx..x  x.xx...xx  ...x.xxxx
..xxx.x.x  ..x.xxxx.  .xx.xx.x.  ...x.xxxx  xx...xx.x  .x..x.xxx
x.x.x.xx.  ..xx..xxx  .x...xxxx  ..xxxxx..  ..xxx.xx.  x.x...xxx
xxx.x...x  ...xxxx.x  ..xxx..xx  xx....xxx  .xx..x.xx  xx.x.x..x
.xx..xxx.  xx..xxx..  xxxx.x...  x.x..x.xx  x..xxx..x  xx.xx..x.
x.xx.x.x.  x.xx.x..x  xx..xxx..  xxxx....x  x...x.xxx  ..xxx.xx.
.xxxxx...  x.xxx..x.  ...xxxxx.  x.x.x.x.x  .xxxxx...  x..xx.x.x
x..x..xxx  xxxx..x..  .xxx..xx.  xx.xx..x.  xx.xx.x..  .x.xxxx..
...xxxxx.  .x.xx.xx.  xx.xx..x.  .xxx.x.x.  xx.x.x.x.  xx...xxx.
.x..x.xxx  x...xx.xx  xx.x..x.x  .x.xx.x.x  x.x.xx.x.  xxx.x...x
xx..xxx..  xx.xx...x  ..xx.xx.x  .x..xx.xx  x.xx.xx..  x.xx.x.x.
.xxx...xx  .xx.x..xx  x...x.xxx  ..xxx..xx  ...x.xxxx  ..xxxx..x
xxxx..x..  xxx..x.x.  x..x.x.xx  xxx.xx...  .x.xx..xx  .xxx...xx
..x.xx.xx  .xx..xx.x  .x.xxx..x  .xx..xx.x  xxx...xx.  xxxx..x..
x..xxx..x  x..x.xxx.  x.x..xxx.  x.xx..xx.  .xxx..x.x  x...xx.xx
.x.x.xx.x  xx....xxx  .xx.x.x.x  x...xxxx.  xxx.x...x  .xx..xx.x

References

[A] S. H. Alavi, A generalization of Johnson graphs with an application to triple factorisations, Discrete Math. 338:11 (2015), 2026-2036.

[ACLR] Hernán de Alba, Walter Carballosa, Jesús Leaños, Luis Manuel Rivera, Independence and matching numbers of some token graphs.

[Be] M. R. Best, Optimal codes, in Packing and Covering in Combinatorics, ed. A. Schrjiver, Mathematical Centre Tracts 106 (1979), 119-140.

[Br] A. E. Brouwer, Bounds on A(n, 4,w).

[BE] S. Bitan, T. Etzion, On the chromatic number, colorings, and codes of the Johnson graph, Discrete Appl. Math. 70:2 (1996), 163-175.

[BE$_2$] A. E. Brouwer, T. Etzion, Some new distance-4 constant weight codes, Adv. Math. Commun., 5:3 (2011), 417-424.

[BSSS] A. E. Brouwer, Lames B. Shearer, N. I. A. Sloane, Warren D. Smith, A new table of constant weight codes, IEEE Trans. Inform. Theory., 36:6 (1990), 1335-1380.

[E] Joakim Ekberg, Geometries of Binary Constant Weight Codes, Master thesis, Karlstadt Universitet, Faculty 2 Department of Mathematics, 2006.

[EV] Tuvi Etzion, Alexander Vardy, A New Construction for Constant Weight Codes.

[J] S. M. Johnson, A new upper bound for error-correcting codes, IRE Trans. Inform. Theory 8:3 (1962), 203-207.

[MPP] K. G. Mirajkar, K. G. and Y. B. Priyanka, Traversability and Covering Invariants of Token Graphs, Mathematical Combinatorics 2 (2016), 132-138.

[R] H. Riyono, Hamiltonicity of the graph g(n; k) of the Johnson scheme, Jurnal Informatika 3 (2007), 41-47.

[T] P. Terwilliger, The Johnson graph $J(d, r)$ is unique if $(d, r)\ne (2; 8)$, Discrete Math. 58:2 (1986), 175-189.

[Z] Günter M. Ziegler. Coloring Hamming Graphs, Optimal Binary Codes, and the 0/1-Borsuk Problem in Low Dimensions.