Consider the set $S = \binom{[n]}{2}$ of all the unordered couples formed by any two elements in $[n] = \{1,\ldots,n\}$, with $n \ge 4$.
Let $\mathcal{P}(S)$ be a partition of $S$ in at most $n$ parts.
Let $X_k(\mathcal{P}(S))$, $k \in [n]$ be a subset of $S$ of minimal size, with the following properties:
- $k \in X_k(\mathcal{P}(S))$;
- for any $x \in X_k(\mathcal{P}(S))$, if there exists $\{x,x'\} \in X \in \mathcal{P}(S)$, then for any $\{y,z\} \in X$, it must be $y \in X_k(\mathcal{P}(S))$ or $z \in X_k(\mathcal{P}(S))$.
Can we find an example of a partition such that:
$$\max_{1 \le k \le n} |X_k(\mathcal{P}(S))| \lt \Big\lfloor \frac{n+1}{2} \Big\rfloor \space \space ?$$
For example for $n=4$ and $\mathcal{P}(S) = \{\{\{1,2\},\{2,4\}\},\{\{1,3\},\{3,4\}\},\{\{1,4\}\},\{\{2,3\}\}\}$ we have $X_1(\mathcal{P}(S)) = \{1,4\}$, $X_2(\mathcal{P}(S)) = \{2\}$, $X_3(\mathcal{P}(S)) = \{3\}$, $X_4(\mathcal{P}(S)) = \{1,4\}$ and the maximum is $2 = \lfloor (n+1)/2 \rfloor$.
