6 simplified (& furthered) analysis of 1 special case
• $m=1$: Denote by $x_i$ the single element of $S_i$ (i.e., $S_i = \{ x_i \}$) and $X = \{ x_1, x_2, \ldots, x_L \} = \bigcup S_i$. $\displaystyle \mathbb{E}[ \max_{1\leq \ell \leq L} |S \cap S_\ell| ] = \sum_{i=1}^L (-1)^{(i-1)} sum_{S \sum_{T cap X \subseteq X_L; |T| neq \emptyset} 1 \cdot f(S) = i1 - \sum_{S \subseteq \{ 1, 2, \ldots, n \} \left(\prod_{x setminus X} f(S) = 1 - \prod_{i \in TX} x \right)$ (inclusion exclusion). (Does this necessarily lead to 1-p_i)$, which is maximized by the greedy solution of$S_i = \{ i \}$(for$1 \leq i \leq L$) to maximize$\displaystyle \mathbb{E}[ \max_{1\leq \ell \leq L} |S \cap S_\ell| ]$?)L$).

• 5 fixed typos
• $L=1$: $S_1 = \{ p_11, p_22, \ldots, p_m m \}$ maximizes $\displaystyle \mathbb{E}[ \max_{1\leq \ell \leq L} |S \cap S_\ell| ]$.

• $m=1$: Denote by $x_i$ the single element of $S_i$ (i.e., $S_i = \{ x_i \}$) and $X = \{ x_1, x_2, \ldots, x_L \} = \bigcup S_i$. $\displaystyle \mathbb{E}[ \max_{1\leq \ell \leq L} |S \cap S_\ell| ] = \sum_{i=1}^L (-1)^{(i-1)} \sum_{T \subseteq X_L; |T| = i} \left(\prod_{x \in T} x \right)$ (inclusion exclusion). (Does this necessarily lead to the greedy solution of $S_i = \{ p_i i \}$ (for $1 \leq i \leq L$) to maximize $\displaystyle \mathbb{E}[ \max_{1\leq \ell \leq L} |S \cap S_\ell| ]$?)

• Here's how I examined a few more special cases:

This example ($(n,m,L)=(4,1,2)$) falls under the already discussed $m=1$ case, but I present it to hopefully make the presentation of subsequent examples clearer:

• Column 2: represents $S_1$ (the 1st bit is 1 iff $1 \in S$ (0 otherwise), the 2nd bit is 1 iff $1 2 \in S$, etc.)
• Column 3: represents $S_4$S_2$• This example ($(n,m,L)=(4,1,2)$) falls under the already discussed$m=1$case, but I present it to hopefully make the presentation of subsequent examples clearer: Notes: the coefficient of 2 in the degree-4 terms of the last three rows seems interesting to me. The sign of a term is the negation of$(-1)$to the parity of the degree of the term. 4 added special cases EDIT: WLOG,$p_1 \geq p_2 \geq \cdots \geq p_n$. Special cases: •$L=1$:$S_1 = \{ p_1, p_2, \ldots, p_m \}$maximizes$\displaystyle \mathbb{E}[ \max_{1\leq \ell \leq L} |S \cap S_\ell| ]$. •$m=1$: Denote by$x_i$the single element of$S_i$(i.e.,$S_i = \{ x_i \}$) and$X = \{ x_1, x_2, \ldots, x_L \} = \bigcup S_i$.$\displaystyle \mathbb{E}[ \max_{1\leq \ell \leq L} |S \cap S_\ell| ] = \sum_{i=1}^L (-1)^{(i-1)} \sum_{T \subseteq X_L; |T| = i} \left(\prod_{x \in T} x \right)$(inclusion exclusion). (Does this necessarily lead to the greedy solution of$S_i = \{ p_i \}$(for$1 \leq i \leq L$) to maximize$\displaystyle \mathbb{E}[ \max_{1\leq \ell \leq L} |S \cap S_\ell| ]$?) • Here's how I examined a few more special cases:$\binom{\binom{n}{m}}{L} = \binom{\binom{4}{1}}{2} = 6$possibilities for$(S_1,S_2)$: 1100 1ooo,o1oo, p1+p2 - p1p21010 1ooo,oo1o, p1+ p3 - p1p31001 1ooo,ooo1, p1+ p4 - p1p40110 o1oo,oo1o, p2+p3 - p2p30101 o1oo,ooo1, p2+ p4 - p2p40011 oo1o,ooo1, p3+p4 - p3p4Column 1: the sum of the subsequent$L=2$columns (I used "o" for "0" in those for readability)Column 2: represents$S_1$(the 1st bit is 1 iff$1 \in S$(0 otherwise), the 2nd bit is 1 iff$1 \in S$, etc.)Column 3: represents$S_4$Column 4:$\displaystyle \mathbb{E}[ \max_{1\leq \ell \leq L} |S \cap S_\ell| ]$(formatted to put the degree-1 terms all together first, then the degree-2 terms, etc., with spacing so you can look up and down and see which other rows share those terms).This example ($(n,m,L)=(4,1,2)$) falls under the already discussed$m=1$case, but I present it to hopefully make the presentation of subsequent examples clearer:$\binom{\binom{n}{m}}{L} = \binom{\binom{4}{2}}{2} = 15$possibilities for$(S_1,S_2)$:2110 11oo,1o1o, p1+p2+p3 - p2p32101 11oo,1oo1, p1+p2+ p4 - p2p41210 11oo,o11o, p1+p2+p3 - p1p31201 11oo,o1o1, p1+p2+ p4 - p1p42011 1o1o,1oo1, p1+ p3+p4 - p3p41120 1o1o,o11o, p1+p2+p3 - p1p21021 1o1o,oo11, p1+ p3+p4 - p1p41102 1oo1,o1o1, p1+p2+ p4 - p1p21012 1oo1,oo11, p1+ p3+p4 - p1p30211 011o,o1o1, p2+p3+p4 - p3p40121 011o,oo11, p2+p3+p4 - p2p40112 01o1,oo11, p2+p3+p4 - p2p31111 11oo,oo11, p1+p2+p3+p4 - p1p3-p1p4-p2p3-p2p4 + p1p2p3+p1p2p4+p1p3p4+p2p3p4 - 2p1p2p3p41111 1o1o,o1o1, p1+p2+p3+p4 - p1p2- p1p4-p2p3- p3p4 + p1p2p3+p1p2p4+p1p3p4+p2p3p4 - 2p1p2p3p41111 1oo1,o11o, p1+p2+p3+p4 - p1p2-p1p3- p2p4-p3p4 + p1p2p3+p1p2p4+p1p3p4+p2p3p4 - 2p1p2p3p4I separated the rows into two groups; two rows are in the same group if their first-column entries are permutations of each other.Notes: the coefficient of 2 in the degree-4 terms of the last three rows seems interesting to me. The sign of a term is the negation of$(-1)$to the parity of the degree of the term.$\binom{\binom{n}{m}}{L} = \binom{\binom{4}{2}}{3} = 20$possibilities for$(S_1,S_2,S_3)$:3111 11oo,1o1o,1oo1, p1+p2+p3+p4 - p2p3-p2p4-p3p4 + p2p3p41311 11oo,o11o,o1o1, p1+p2+p3+p4 - p1p3-p1p4- p3p4 + p1p3p41131 1o1o,o11o,oo11, p1+p2+p3+p4 - p1p2- p1p4- p2p4 + p1p2p41113 1oo1,o1o1,oo11, p1+p2+p3+p4 - p1p2-p1p3- p2p3 + p1p2p32220 11oo,1o1o,o11o, p1+p2+p3 - p1p2p32202 11oo,1oo1,o1o1, p1+p2+ p4 - p1p2p42022 1o1o,1oo1,oo11, p1+ p3+p4 - p1p3p40222 o11o,o1o1,oo11, p2+p3+p4 - p2p3p42211 11oo,1o1o,o1o1, p1+p2+p3+p4 - p1p4-p2p3- p3p4 + p1p3p4+p2p3p4 - p1p2p3p42121 11oo,1o1o,oo11, p1+p2+p3+p4 - p1p4-p2p3-p2p4 + p1p2p4+ p2p3p4 - p1p2p3p42211 11oo,1oo1,o11o, p1+p2+p3+p4 - p1p3- p2p4-p3p4 + p1p3p4+p2p3p4 - p1p2p3p42112 11oo,1oo1,oo11, p1+p2+p3+p4 - p1p3- p2p3–p2p4 + p1p2p3+ p2p3p4 - p1p2p3p41221 11oo,o11o,oo11, p1+p2+p3+p4 - p1p3-p1p4- p2p4 + p1p2p4+p1p3p4 - p1p2p3p41212 11oo,o1o1,oo11, p1+p2+p3+p4 - p1p3–p1p4-p2p3 + p1p2p3+ p1p3p4 - p1p2p3p42121 1o1o,1oo1,o11o, p1+p2+p3+p4 - p1p2- p2p4–p3p4 + p1p2p4+ p2p3p4 - p1p2p3p42112 1o1o,1oo1,o1o1, p1+p2+p3+p4 - p1p2- p2p3- p3p4 + p1p2p3+ p2p3p4 - p1p2p3p41221 1o1o,o11o,o1o1, p1+p2+p3+p4 - p1p2- p1p4- p3p4 + p1p2p4+p1p3p4 - p1p2p3p41122 1o1o,o1o1,oo11, p1+p2+p3+p4 - p1p2- p1p4-p2p3 + p1p2p3+p1p2p4 - p1p2p3p41212 1oo1,o11o,o1o1, p1+p2+p3+p4 - p1p2-p1p3- p3p4 + p1p2p3+ p1p3p4 - p1p2p3p41122 1oo1,o11o,oo11, p1+p2+p3+p4 - p1p2-p1p3- p2p4 + p1p2p3+p1p2p4 - p1p2p3p4Note: the sign of a term is the negation of$(-1)\$ to the parity of the degree of the term only in the first and third block of rows — the degree-3 terms in the 4 rows in the middle block are all negative.

 
 
 
3 fixed typo
2 fixed typo
1