# Permutation function based on subsets

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.

## 1 Answer

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.