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](http://www.cse.psu.edu/~sofya/masters.ps) 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](http://yaroslavtsev.wordpress.com/2010/03/10/monotonicity-testing/) to some informal description of motivation for this problem.



Making a non-monotone function monotone
A combinatorial proof was found last year by Chakrabarty and Seshadhri: <http://eccc.hpi-web.de/report/2012/030/download>. In Theorem 3 they show that indeed $E(f) = \Omega(M(f))$.


