# Property testing of a complete multipartite graph

Propose and prove an $$\epsilon$$-test for the following property in the dense graph model: $$G=(V,E)$$ is a complete multipartite graph. That is, there exists a partition $$V=V_1\cup\ldots\cup V_\ell$$ such that $$uw\in E$$ if and only if there are $$i\neq j$$ such that $$u\in V_i$$ and $$w\in V_j$$.

I have been stuck at trying to solve this question for a few days. I tried to devise an algorithm along the lines GGR98 for bipartiteness testing (such as here), where we sample a sets $$U$$ and $$S$$ of size $$\mathrm{poly}(1/\epsilon)$$ and try to "self-correct" $$S$$ based on a small number of "partitions" induced by $$U$$. In particular, I am not sure how to define "violating edges with respect to $$U$$" for the above mentioned property. Any help?

EDIT: The number $$\ell$$ is not given to the algorithm as input. In other words, the task is to determine if there exists an $$\ell$$ such that the graph is complete $$\ell$$-partite.

• Try using the following: if $(x,y),(x,z) \notin E$ then $(y,z) \notin E$. May 18, 2021 at 13:18
• I can't see why this is sufficient. Suppose we delete a single edge from a complete bipartite graph, then this violating vertex pair will not be detected by this criterion, right? May 18, 2021 at 14:25
• Every tester which doesn’t sample a linear fraction of edges will miss such a small change. Same goes for other properties, such as bipartiteness. Are you suggesting that bipartite isn’t testable? Perhaps you should take a closer look at the definition of an $\epsilon$-tester. May 18, 2021 at 14:30
• I see now. It was easier for me to solve the problem of the graph being a union of cliques, as it was more similar to the GGR98 construction, in conjunction with the criterion you suggested. Thank you! May 18, 2021 at 17:16
• A graph is complete multipartite iff its complement is a disjoint union of cliques. May 18, 2021 at 17:44

The following answer construct a tester for a graph being complete $$\ell$$-partite for a fixed value of $$\ell$$.

Consider the following tester:

• Choose $$\ell+1$$ vertices at random.
• Verify that the edges between them are consistent with a complete $$\ell$$-partite graph, that is, there is a way to color the vertices using $$\ell$$ colors such that there is an edge between two vertices iff they have different colors.

We claim that for every $$\epsilon>0$$ there exists $$\delta>0$$ such that if the test succeeds with probability at least $$1-\delta$$, then the graph is $$\epsilon$$-close to complete $$\ell$$-partite. To show this, we assume that the test succeeds with probability at least $$1-\delta$$, and show that the graph is $$\epsilon(\delta)$$-close to complete $$\ell$$-partite, where $$\epsilon(\delta) \to 0$$ as $$\delta \to 0$$. Moreover, the proof is by induction on $$\delta$$, the case $$\ell = 1$$ being trivial.

Let $$\gamma$$ be the probability that $$\ell-1$$ randomly chosen points form a clique. If $$\gamma \leq \sqrt{\delta}$$ then the graph passes the test for being complete $$(\ell-2)$$-partite with probability at least $$1-\sqrt{\delta}-\delta$$, and we complete the proof by induction. Assume, therefore, that $$\gamma \ge \sqrt{\delta}$$.

The expected failure probability of the test given that the first $$\ell-1$$ points form a clique is at most $$\delta/\gamma \leq \sqrt{\delta}$$. In particular, we can find a clique $$x_1,\ldots,x_{\ell-1}$$ such that with probability $$1-\sqrt{\delta}$$ over the choice of $$x_\ell,x_{\ell+1}$$, the graph induced by $$x_1,\ldots,x_{\ell+1}$$ is consistent with a complete $$\ell$$-partite graph.

Define the color $$c(x)$$ of a point $$x \neq x_1,\ldots,x_{\ell-1}$$ as follows. If $$x$$ is connected to all but $$x_i$$, then $$c(x) = i$$. If $$x$$ is connected to all, then $$c(x) = \ell$$. Otherwise, $$c(x) = \bot$$. Then with probability $$1-\sqrt{\delta}$$, the following holds:

• Either $$c(x_\ell) = c(x_{\ell+1}) \neq \bot$$ and $$(x_\ell,x_{\ell+1})$$ is not an edge,
• Or $$c(x_\ell) \neq c(x_{\ell+1})$$, $$c(x_\ell),c(x_{\ell+1}) \neq \bot$$, and $$(x_\ell,x_{\ell+1})$$ is an edge.

This shows that we can partition all but $$\sqrt{\delta} n$$ of the vertices into $$\ell$$ sets, such that the induced graph differs from the corresponding complete $$\ell$$-partite one in an $$O(\sqrt{\delta})$$-fraction of edges.

• Thanks for the answer! I meant for $\ell$ to be some unknown number, which is not given as input to the algorithm. I will edit the question to reflect this. May 18, 2021 at 13:13