6
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
+50
$\begingroup$

I have a counterexample, showing that $r$ can appear later in $\sigma_2$ than in $\sigma_1$.

I'm going to write this counterexample with weights on the sets, but because the weights are rational it can easily be converted to an unweighted counterexample by duplicating sets.

Counterexample: 3x{AC}, 2x{AB}, 2x{BD}, 2x{CD}, 11/8x{C}, 1x{A}, 1x{D}.

Calculations

The initial maximum value of $f$ is $215/24$, achieved by the permutations ADCB, CBAD, CBDA. By the tiebreaker, $\sigma_1$ is ADCB.

Now, we will add the element D to the set {A}, changing it to the set {AD}.

The new maximum value of $f$ is $217/24$, achieved by the permutations CBDA, CDAB, CDBA. By the tiebreaker, $\sigma_2$ is CBDA.

We added the element D to a set, but $\sigma_1$ has D in position 2, while $\sigma_2$ has D in position 3.


Note that while this counterexample relies on the tiebreaker, it can be lightly modified to not rely on the tiebreaker.

To do so, add the subsets {A} and {B} each with an equal weight $\epsilon$ to the set system, for some $\epsilon$ very close to 0. This increases the value of ADCB by $(5/4)\epsilon$, while CBAD and CBDA increase by $(5/6)\epsilon$ and $(3/4)\epsilon$, respectively. As a result, ADCB is $\sigma_1$ without a tiebreaker needed.

The values of CDAB and CDBA increase by $(7/12)\epsilon$, which is smaller than CBDA's $(3/4)\epsilon$, so CBDA is $\sigma_2$ with no tiebreaker needed.


The way I came up with the counterexample is by starting with the 2 element sets, which I designed to force the optimal permutation to start with either AD or CB. At this point, adding a D to an A subset would benefit a CBD permutation but not an AD permutation, which would make the CBD permutation the new optimum, and form a counterexample. I then futzed around with the weights on the single subsets to get the optima to work out right.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.