# On Finding and Enumerating Maximal and Maximum \(k\)-Partite Cliques in \(k\)-Partite Graphs
## 3 The Asymptotic Optimality of MMCE
We begin by letting \(G\) denote an edgeless 4-partite graph whose vertices are arranged in partite sets \(W\), \(X\), \(Y\), and \(Z\), each set of cardinality \(3p=n/4\), with \(W=\{w_{1},\,w_{2},\,\ldots,\,w_{3p}\}\), \(X=\{x_{1},\,x_{2},\,\ldots,\,x_{3p}\}\), \(Y=\{y_{1},\,y_{2},\,\ldots,\,y_{3p}\}\) and \(Z=\{z_{1},\,z_{2},\,\ldots,\,z_{3p}\}\). For notational convenience, we partition \(W\) into \(W_{1}=\{w_{1},\,w_{2},\,\ldots,\,w_{p}\}\), \(W_{2}=\{w_{p+1},\,w_{p+2},\,\ldots,\,w_{2p}\}\) and \(W_{3}=\{w_{2p+1},\,w_{2p+2},\,\ldots,\,w_{3p}\}\), and partition \(X\), \(Y\), and \(Z\) in similar fashion. We nowplace in \(G\) every interpartite edge except those in the \(4p\) disjoint triangles \(\{w_{i},x_{i+p},y_{i+2p}\}\), \(\{x_{i},y_{i+p},z_{i+2p}\}\), \(\{y_{i},z_{i+p},w_{i+2p}\}\), and \(\{z_{i},w_{i+p},X_{i+2p}\}\), where \(1\leq i\leq p\). See Figure 1. Let \(M\) denote the set of all maximal \(4\)-partite cliques in \(G\) containing at least one vertex from each of \(W_{i}\), \(X_{i}\), \(Y_{i}\), and \(Z_{i}\), \(1\leq i\leq 3\). Following the reasoning of the \(k=3\) case, there are \(3^{n/12}-3(2^{n/12}-1)\) ways to choose clique candidate vertices from each of \(\{W_{1},X_{2},Y_{3}\}\), \(\{X_{1},Y_{2},Z_{3}\}\), \(\{Y_{1},Z_{2},W_{3}\}\), and \(\{Z_{1},W_{2},X_{3}\}\). Since these four sets do not overlap, we apply the product rule and conclude that \(M\) contains \((3^{n/12}-3(2^{n/12}-1))^{4}\) elements. Assigning this function to \(f(n)\) and \(3^{n/3}\) to \(g(n)\), it follows that \(\lim\limits_{n\to\infty}\frac{f(n)}{8(n)}=1\), which we show in Appendix B. Letting \(F(n)\) denote the number of maximal \(4\)-partite cliques in \(G\), we have \(f(n)\leq F(n)\leq g(n)\). By the squeeze theorem of calculus, \(\lim\limits_{n\to\infty}\frac{F(n)}{8(n)}=1\), from which we conclude that the number of maximal \(4\)-partite cliques in the family of graphs described by \(G\) is \(\sim\)\(3^{n/3}\). In the \(k=5\) case, let \(n\) be evenly divisible by \(15\), and let \(p=n/15\). We begin by letting \(G\) denote an edgeless \(5\)-partite graph whose vertices are arranged in partite sets \(V\), \(W\), \(X\), \(Y\), and \(Z\), each set of cardinality \(3p=n/5\), with \(V=\{v_{1},v_{2},\ldots,v_{3p}\}\), \(W=\{w_{1},w_{2},\ldots,w_{3p}\}\), \(X=\{x_{1},x_{2},\ldots,x_{3p}\}\), \(Y=\{y_{1},y_{2},\ldots,y_{3p}\}\) and \(Z=\{z_{1},z_{2},\ldots,z_{3p}\}\). We partition \(V\) into \(V_{1}=\{v_{1},v_{2},\ldots,v_{p}\}\), \(V_{2}=\{v_{p+1},v_{p+2},\ldots,v_{2p}\}\) and \(V_{3}=\{v_{2p+1},v_{2p+2},\ldots,v_{3p}\}\), and partition \(W\), \(X\), \(Y\), and \(Z\) in similar fashion. We now place in \(G\) every interpartite edge except those in the \(5p\) disjoint triangles \(\{v_{i},w_{i+p},x_{i+2p}\}\), \(\{w_{i},x_{i+p},y_{i+2p}\}\), \(\{x_{i},y_{i+p},z_{i+2p}\}\), \(\{y_{i},z_{i+p},v_{i+2p}\}\), and \(\{z_{i},w_{i+p},w_{i+2p}\}\), where \(1\leq i\leq p\). See Figure 2. Let \(M\) denote the set of all maximal \(5\)-partite cliques in \(G\) containing at least one vertex from each of \(V_{i}\), \(W_{i}\), \(X_{i}\), \(Y_{i}\) and \(Z_{i}\), \(1\leq i\leq 3\). Again following the reasoning of the \(k=3\) case, there are \(3^{n/15}-3(2^{n/15}-1)\) ways to choose clique candidate vertices from each of \(\{V_{1},W_{2},X_{3}\}\), \(\{W_{1},X_{2},Y_{3}\}\), \(\{X_{1},Y_{2},Z_{3}\}\), \(\{Y_{1},Z_{2},V_{3}\}\), and \(\{Z_{1},V_{2},W_{3}\}\). Since these five sets do not overlap, we apply the product rule and conclude that \(M\) contains \((3^{n/15}-3(2^{n/15}-1))^{5}\) elements. Assigning this function to \(f(n)\) and \(3^{n/3}\) to \(g(n)\), it follows that \(\lim\limits_{n\to\infty}\frac{f(n)}{8(n)}=1\), which we address in Appendix B. Letting \(F(n)\) denote the number of maximal \(5\)-partite cliques in \(G\), we have \(f(n)\leq F(n)\leq g(n)\). By the squeeze theorem of calculus, \(\lim\limits_{n\to\infty}\frac{F(n)}{8(n)}=1\), from which we conclude that the number of maximal \(5\)-partite cliques in the family of graphs described by \(G\) is \(\sim\)\(3^{n/3}\).