# C1: Monotonicity Testing

In this post, we will see how to use Yao’s minmax principle in Property Testing.

## Definitions

We say that a function \(f: \{0,1\}^n \to \{0,1\}\) is monotone if \(f(x) \leq f(y)\) for all \(x \leq y\) (i.e., \(x_i \leq y_i ,\forall i\in[n]\)).

Now, let us consider monotone functions and graph labelings. Let \(\vec{G}= (V, E)\) be a directed graph. We say \(f\) is monotone on \(\vec{G}\) if \(f(u) \leq f(v)\) for all \((u,v) \in E\). A pair of vertices \((u,v)\) is violated if \(u \leq v\) and \(f(u) > f(v)\).

Notice that monotonicity of labelings of acyclic graphs corresponds to monotonicity of functions on posets.

A poset is a set \(P\) equipped with a binary relation \(\leq\) satisfying the following three properties:

- If \(x\in P\), then \(x\leq x\) in \(P\)(reflexive property)
- If \(x,y,z\in P\), \(x\leq y\) in \(P\) and \(y\leq x\) in \(P\), then \(x=y\)(antisymmetric)
- If \(x,y,z\in P\), \(x\leq y\) in \(P\) and \(y \leq z\) in \(P\), then \(x\leq z\) in \(P\) (transitive property)

The following graph is extremely useful.

\(\textbf{Ruzsá-Szemerédi Graph}\)(RS graph) Let \(U\) be an undirected graph. A matching \(M\) in \(U\) is called induced if the induced subgraph \(U[V(M)]\) contains only the edges of \(M\). A (bipartite) graph \(U = (X, Y; E)\) is called \((s,t)\)-Ruzsá-Szemerédi if its edge set can be partitioned into at least \(s\) induced matching \(M_1,\ldots, M_s\), each of which has size \(t\).

## Lower Bounds

\(\textbf{Lemma}\). For infinitely many \(n\), there is an \((a,b)\)-RS graph \(U = (L, R;E)\) where \(a = n^{\Omega(\frac{1}{\log \log n})}, b = n/3 -o(1), \lvert L \rvert = \lvert R \rvert = n.\)

The above lemma shows the existence of the RS graph with large average degree. We will use such a RS graph to prove the lower bound.

\(\textbf{Theorem}\). Let \(U = (L, R; E)\) be an \((X, \epsilon n)\)-RS graph with \(\lvert L \rvert = \lvert R \rvert = n\). After directing all edges of \(U\) from \(L\) to \(R\), we obtain a DAG \(\vec{G}\). Then, any non-adaptive tester for monotonicity on \(G\) requires \(\Omega(\sqrt{X})\) queries.

To be continued.

## Reference

[1]. Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R. and Samorodnitsky, A., 2002, May. Monotonicity testing over general poset domains. In *Proceedings of the thiry-fourth annual ACM symposium on Theory of computing* (pp. 474-483).