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.


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.