co.combinatorics - Making a non-monotone function monotone

Consider a function $f: {0,1}^n rightarrow {1..R}$. This function can be interpreted as a coloring $Color(v)$ of vertices in a unit n-dimensional hypercube in $R$ colors.

We say there is a directed edge $(v1, v2)$ in the hypercube if $v1$ and $v2$ differ in only one coordinate in n-dimensional space and this coordinate is equal to $0$ for $v1$ and to $1$ for $v2$.

Let's define $E(f)$ to be the number of non-monotone directed edges in this hypercube, i.e. edges $(v1, v2)$, such that $Color(v1) > Color(v2)$. Having a non-monotone function $f$ we want to make it monotone, changing its values in as few points of domain as possible. Let's denote $M(f)$ to be the minimal number of points where we need to change the values to make the function monotone.

There is a hypothesis that $M(f) le E(f)$ that I'm trying to prove.

Known results:

0) There exist such $f$ that $M(f) ge E(f)$ (if $E(f)$ is not too large, say $E(f) le 2^{n-1}$). This one is an easy exercise.

1) For $R=2$ the hypothesis is true. The method I know is rather difficult to describe briefly. If necessary, I can give a link (see EDIT).

2) For general $R$ it can be proved that $M(f) le E(f) log{R}$. The proof involves construction for $R=2$ and some range reduction technique.

I am interested in what techniques can be applied to prove or disprove this hypothesis. Any result better than $M(f) le E(f) log{R}$ (like $M(f) = O(E(f))$) will be interesting.

EDIT: Here is a link to M.Sc. thesis by Sofya Raskhodnikova, where results 1) and 2) can be found in Chapters 3 and 5 respectively.

EDIT: Here is a link to some informal description of motivation for this problem.

• Next matrices - Random products of projections: bounds on convergence rate?
• Previous co.combinatorics - Red-blue alternating paths