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)$?

  • 1
    $\begingroup$ A family $\mathcal F$ of size $25$ would not quite be a Steiner system, as the number of subsets of $\{1,\dots,9\}$ of size four contained in some element of $\mathcal F$ would be $5\cdot 25$, which is one less than $\binom94=126$. $\endgroup$ – Mike Earnest Jan 16 at 20:51
  • 1
    $\begingroup$ You want $25$ five-element sets whose four-element subsets comprise all but one of the four element subsets of $[9]$. Consider the $120\times 125$ matrix of 0's and 1's whose columns are indexed by four-element subset of $[9]$, except for $\{1,2,3,4\}$, and whose rows are indexed by five-element subsets of $[9]$, except for those who contain $\{1,2,3,4\}$. Then you want a subset of rows whose sum is the vector of $125$ ones, with a one where the row contains the column. This is solvable by Knuth's Algorithm X. $\endgroup$ – Mike Earnest Jan 16 at 21:05
  • $\begingroup$ @MikeEarnest There are ${9\choose 5}-|\{5,6,7,8,9\}|=126-5=121\ne 120$ five-element subsets of $[9]$, except for those who contain $\{1,2,3,4\}$. $\endgroup$ – Alex Ravsky May 7 at 4:00

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


[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.

  • 2
    $\begingroup$ +1 This was worth the wait. :D $\endgroup$ – antkam May 8 at 5:11

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.