# Minimizing the set of “wrong” edges in $K_\omega$ with $\{0,1\}$-weights

For any set $$X$$, let $$[X]^2 = \big\{\{x,y\}:x\neq y\in X\big\}$$.

Let $$f:[\omega]^2\to\{0,1\}$$ be a function. The principal goal is to find a partition of $$\omega$$ such that if $$m\neq n\in \omega$$ are in the same block of the partition, then $$f(\{m,n\}) = 0$$, and if $$m,n$$ are not in the same block, then $$f(\{m,n\})= 1$$.

It is easy to see that given $$f:[\omega]^2\to\{0,1\}$$ it is not always possible to find such a "perfect" partition that meets the requirement above.

So for any partition $$P$$ of $$\omega$$ we define the collection of wrong members of $$[\omega]^2$$, denoted by $$W_P\subseteq [\omega]^2$$ in the following way.

• $$W_P^{(0)} = \big\{e\in[\omega]^2\setminus\big(\bigcup\{[b]^2:b \in P\}\big): f(e) = 0\big\}$$, that is the set $$W_P^{(0)}$$ is the set of all $$e\in[\omega]^2$$ such that $$e$$ is not inside some block, but $$f(e) = 0$$ , and

• $$W_P^{(1)} = \big\{e\in\bigcup\{[b]^2:b \in P\}: f(e) = 1\big\}$$, that is the set $$W_P^{(0)}$$ is the set of all $$e\in[\omega]^2$$ such that $$e$$ is indeed inside some block, but $$f(e) = 1$$.

The intuition is that the members of $$W_P^{(0)}$$ are "falsely" labelled with $$0$$ by $$f$$, and the members of $$W_P^{(1)}$$ are "falsely" labelled with $$1$$ by $$f$$. Finally, we let $$W_P = W_P^{(0)} \cup W_P^{(1)}.$$

Question. Is there $$f:[\omega]^2\to\{0,1\}$$ with the following property?

Given any partition $$P$$ of $$\omega$$, is it always possible to find a partition $$P_2$$ of $$\omega$$ such that $$W_{P_2}\subseteq W_P$$ and $$W_{P_2} \neq W_P$$.

I believe not: let $$f$$ be any colouring and take a maximal equivalence relation $$\sim$$ on $$\omega$$ with the property that $$m\sim n$$ implies $$f(\{m,n\})=0$$. Note that $$\sim$$ can be extreme: the identity relation if $$f$$ is constant with value $$1$$, and $$\sim$$ is $$\omega^2$$ of $$f$$ is constant with value $$0$$. For the corresponding partition $$P$$ we have $$W^{(1)}_P=\emptyset$$. This means that if $$Q$$ is a partition with $$W_Q\subseteq W_P$$ then $$W^{(1)}_Q=\emptyset$$. Therefore we have $$\bigcup\{[c]^2:c\in Q\}\subseteq f^{-1}(0)$$ and since $$W^{(0)}_Q\subseteq W^{(0)}_P$$ we get $$\bigcup\{[b]^2:b\in P\}\subseteq\bigcup\{[c]^2:c\in Q\}$$ and this implies that $$\sim$$ is a subset of the equivalence relation that determines $$Q$$; by maximality it follows that $$P=Q$$.