Ways of choosing k items out of n with exactly one symbol in common - MathOverflow

Ways of choosing k items out of n with exactly one symbol in common

2012-11-05T02:54:51Z

This is inspired by a card-game – the game involves cards with 8 different symbols printed on each, with the property that each pair of cards has exactly 1 symbol in common. That set us thinking – given an $n$-alphabet, what's the maximum number of $k$-sets of symbols such that each pair of $k$-sets has exactly one symbol in common? Formally:

Given $k,\ n,\ A = \{a_1, …, a_n\}$, maximise $s = s(k,n)$ such that

$∃ S=\{S_1, S_2, …, S_s\}$, and
$∀ 1 ≤ t ≤ s,\ |S_t| = k ∧ S_t - A = ∅$, and
$∀ 1 ≤ u, v ≤ s, |S_u ∩ S_v| = 1 $

Or a dual problem: to generate $m$ $k$-sets with the above property between any $2$ $k$-sets, how big must the alphabet be?

Answer by Douglas Zare for Ways of choosing k items out of n with exactly one symbol in common

2012-11-05T05:56:38Z

The condition that every pair of cards has precisely one symbol in common describes a linear space or pairwise balanced design, where your cards correspond to points, and symbols to lines. A linear space is a set of points and lines so that every pair of points is contained by a unique line. To avoid triviality, there are at least $2$ points, and some people assume there are $3$ noncollinear points. So, every pair of cards contains a unique symbol in common means there is a unique line containing those points. The additional condition that all cards have the same number of symbols means each point of the linear space is contained in the same number of lines. I think this condition is that the linear space is regular.

Examples include affine and projective $d$-dimensional spaces over finite fields, and more generally block designs with $t=2$ and $\lambda=1$. Those examples have the same number of points on each line. For example, there are Steiner triple systems on $19$ points. These correspond to a set of $19$ cards with $9$ symbols on each so that any pair of cards shares one symbol in common. There are examples which don't have the same number of points on the same line, such as the induced geometry from taking any subset of the points, which corresponds to removing cards from a valid deck.

If you specify $n$ but not $k$, you are asking how many points you can have for a fixed number of lines. The DeBruijn-Erdős Theorem (also Fisher's inequality) says that the number of points in a linear space is at most the number of lines, and that equality holds only for projective planes and near pencils (and near pencils don't have the same number of lines through each point).

Answer by Yuichiro Fujiwara for Ways of choosing k items out of n with exactly one symbol in common

2012-11-05T07:45:08Z

The kind of object you're looking at is exactly an $(r, \lambda)$-design for $\lambda = 1$ in combinatorial design theory.

An $(r, \lambda)$-design is an ordered pair $(V, \mathcal{B})$, where $\mathcal{B}$ is a collection of subsets of finite set $V$ such that every element of $V$ appears in exactly $r$ elements of $\mathcal{B}$, and every pair of distinct elements of $V$ appears in exactly $\lambda$ elements of $\mathcal{B}$.

Usually, the cardinalitys $\vert V \vert$ and $\vert \mathcal{B} \vert$ are written as $v$ and $b$ respectively. We call the elements of $V$ points and those of $\mathcal{B}$ blocks.

To see the equivalence, call each card a point, and each symbol a block. The set $A =\lbrace a_1, \dots, a_n \rbrace$ is the set $\mathcal{B}$ of blocks here, and you say a point is contained in block $a_i$ if the corresponding card has the symbol $a_i$ on it. Then setting $r = k$ and $\lambda = 1$, the above definition defines exactly what you described in the language of cards with symbols on them; every card has $k$ symbols (= every point appears $r$ times) and every pair of cards share exactly one symbol of $A$ (= every pair of points appear exactly once in a block in $\mathcal{B}$). The question you asked can be understood as "What's the maximum number of points in a $(k,1)$-design when the number of blocks is $n$?" To answer this, the basic relation between parameters of a nontrivial $(r, \lambda)$-design is:

$v \leq r(r-1)+1$ with equality if $r-\lambda$ is the order of a finite projective plane.

The following might also be helpful if you ask the same kind of question by fixing some parameters:

$b \geq v r^2/(r+\lambda(v-1))$,

$c_i(r-\lambda+\lambda v - \lambda k_i) \leq (r-\lambda)(r-\lambda +\lambda v)$, (c_i is the size of the $i$th block or equivalently the number of cards that have the symbol $i$).

You can find more about $(r, \lambda)$-designs in chapter "(r, \lambda)-designs" by G.H.J. van Rees in the book "Handbook of Combinatorial Designs" edited by C.J. Colbourn and J. Dinitz.

Edit: The correct definition should allow the same subset of $V$ appearing more than once in $\mathcal{B}$, so $\mathcal{B}$ shouldn't be a set but a collection.