1
$\begingroup$

Let us consider a design $\mathcal{D} = (V,\mathcal{B})$ with points in $V$ and blocks in $\mathcal{B}$. I am interested in the special case of a $t-(v,k,\lambda)$ design for $k=3$, i.e., all blocks contain exactly $3$ points.

Consider a subset $S$ of $s$ points such that $S \subset V$ and $s<\frac{v}{2}$. My goal is to pick an appropriate choice of $S$ such that the number of blocks with the majority of their elements belonging to $S$ is maximized. I am mostly interested in the maximum such number of blocks rather than a systematic choice of $S$. Formally,

$$b^{\max} := \max_S|\{B\in\mathcal{B}: |B \cap S| \geq 2\}|$$

Based on some experiments with design constructions, I suspect that in order to maximize this quantity we should not pick a set $S$ such that some block is a subset of $S$, i.e., that $S$ should be an independent set of $s$ points.

I am trying to show this using the inclusion-exclusion principle but I cannot reach the desired result. My thought is as follows. Let $X = \{B\in\mathcal{B}: |B \cap S| \geq 2\}$ and $Y = \{B\in\mathcal{B}: |B \cap S| = 3\}$. Then, \begin{eqnarray} b^{\max} &\leq&|X-Y|\\ &=&|X| - |X\cap Y|\\ &=&|\{B\in\mathcal{B}: |B \cap S| = 2 \text{ or } |B \cap S|=3\}| - |Y|\\ &=&|X\cup Y| - |Y|\\ &=&|X|+|Y| \end{eqnarray}

An example is the Fano plane which is a $2-(7,3,1)$ design with blocks (assuming that the points are $V = \{0,1\dots,6\}$) $$\mathcal{B} = \{\{0,1,2\},\{0,3,4\},\{0,5,6\},\{2,3,6\},\{2,4,5\},\{1,3,5\},\{1,4,6\}\}$$ Let $s=3$. If we choose $S=\{0,1,2\}$ then only the block $\{0,1,2\}$ has the desired property. But this is not the best we can do. If we instead pick $S = \{0,1,3\}$ then the blocks $\{0,1,2\}$, $\{0,3,4\}$ and $\{1,3,5\}$ all have the desired property since they contain at least $2$ elements from $S$.

If it helps in the analysis, I would be interested in the special case of $t=k=3$ so that the following value is a constant [Combinatorial Designs, Stinson, 2004]: $$b_s=|\{B\in\mathcal{B}: S\subset B\}| = \lambda\frac{\binom{v-s}{t-s}}{\binom{k-s}{t-s}}$$ which holds for $0\leq s \leq t$.

Can you help me prove (or disprove) the aforementioned arguments?

$\endgroup$

0

You must log in to answer this question.