Revisions - MathOverflow

Return to Question

simplified (& furthered) analysis of 1 special case

view source

edited Jan 8 2011 at 3:50

$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$).

fixed typos

view source

edited Jan 8 2011 at 3:40

Jay Howard
31●3

$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.

added special cases

view source

edited Jan 26 2010 at 9:33

Jay Howard
31●3

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.