3
$\begingroup$

Let $X = \{ 1, \dots, n = sk \}$ be a finite set. Let $\mathscr P, \mathscr Q$ be equi-partitions of $X$ into $k$ sets of size $s$. Denote by $V(\mathscr P, \mathscr Q)$ the maximum size of intersection between sets in $\mathscr P$ and sets in $\mathscr Q$, i.e.,

$$ V(\mathscr P, \mathscr Q) = \max_{P \in \mathscr P, Q \in \mathscr Q} \{ | P \cap Q | \} $$

Fix an integer $1 \leq \lambda \leq s$ and let $v(\lambda, s, k)$ be the size of the largest family of partitions $\{ \mathscr P_i \}$ of $X$ such that for every $i < j$, $V(\mathscr P_i, \mathscr P_j) \leq \lambda$.

I have not seen this studied in the literature on extremal combinatorics (though it is referenced as open in Table 2 of this 2004 paper of Bessiere et al.) I am interested in known bounds on $v(\lambda, s, k)$, particularly any trivial lower bounds that follow from related quantities in extremal combinatorics. I have been thinking of some constructions for specific values of $\lambda$ to lower bound the quantity, but for the sake of making this question direct I am only asking about the relation to the existing extremal combinatorics literature.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.