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.

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.

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.

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.

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.