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.


1 Answer 1


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))$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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