Return to Question

We have some subsets $A_1,\dots,A_k$ of $A=\{1,2,\dots,n\}$. For each permutation $\sigma$ of $A$, define $f(\sigma) = \sum_{i=1}^k g(\sigma,A_i)$, where if the earliest element of $A_i$ in $\sigma$ appears in position $j$, then $g(\sigma,A_i)= 1/j$. Let $\sigma_1$ be the permutation maximizing $f(\sigma)$, breaking ties lexicographically.

Now, we add an element $r\not\in A_1$ to $A_1$, and let $\sigma_2$ be the permutation maximizing $f(\sigma)$. Does it always hold that $r$ appears no later in $\sigma_2$ than in $\sigma_1$?

A natural approach is to show that if $r$ appears later in $\sigma_2$ than in $\sigma_1$, then upon adding $r$ to $A_1$, $f(\sigma_1)$ increases by at least as much as $f(\sigma_2)$. But this may not be true, because there may already be an element in $A_1$ that appears in $\sigma_1$ before $r$  .

We have some subsets $A_1,\dots,A_k$ of $A=\{1,2,\dots,n\}$. For each permutation $\sigma$ of $A$, define $f(\sigma) = \sum_{i=1}^k g(\sigma,A_i)$, where if the earliest element of $A_i$ in $\sigma$ appears in position $j$, then $g(\sigma,A_i)= 1/j$. Let $\sigma_1$ be the permutation maximizing $f(\sigma)$, breaking ties lexicographically.

Now, we add an element $r\not\in A_1$ to $A_1$, and let $\sigma_2$ be the permutation maximizing $f(\sigma)$. Does it always hold that $r$ appears no later in $\sigma_2$ than in $\sigma_1$?

A natural approach is to show that if $r$ appears later in $\sigma_2$ than in $\sigma_1$, then upon adding $r$ to $A_1$, $f(\sigma_1)$ increases by at least as much as $f(\sigma_2)$. But this may not be true, because there may already be an element in $A_1$ that appears in $\sigma_1$ before $r$. Still, it does not clearly lead to a counterexample either.

We have some subsets $A_1,\dots,A_k$ of $A=\{1,2,\dots,n\}$. For each permutation $\sigma$ of $A$, define $f(\sigma) = \sum_{i=1}^k g(\sigma,A_i)$, where if the earliest element of $A_i$ in $\sigma$ appears in position $j$, then $g(\sigma,A_i)= 1/j$. Let $\sigma_1$ be the permutation maximizing $f(\sigma)$, breaking ties lexicographically.

Now, we add an element $r\not\in A_1$ to $A_1$, and let $\sigma_2$ be the permutation maximizing $f(\sigma)$. Does it always hold that $r$ appears no later in $\sigma_2$ than in $\sigma_1$?

We have some subsets $A_1,\dots,A_k$ of $A=\{1,2,\dots,n\}$. For each permutation $\sigma$ of $A$, define $f(\sigma) = \sum_{i=1}^k g(\sigma,A_i)$, where if the earliest element of $A_i$ in $\sigma$ appears in position $j$, then $g(\sigma,A_i)= 1/j$. Let $\sigma_1$ be the permutation maximizing $f(\sigma)$, breaking ties lexicographically.

Now, we add an element $r\not\in A_1$ to $A_1$, and let $\sigma_2$ be the permutation maximizing $f(\sigma)$. Does it always hold that $r$ appears no later in $\sigma_2$ than in $\sigma_1$?

A natural approach is to show that if $r$ appears later in $\sigma_2$ than in $\sigma_1$, then upon adding $r$ to $A_1$, $f(\sigma_1)$ increases by at least as much as $f(\sigma_2)$. But this may not be true, because there may already be an element in $A_1$ that appears in $\sigma_1$ before $r$ .