# On Finding and Enumerating Maximal and Maximum \(k\)-Partite Cliques in \(k\)-Partite Graphs
## 3 The Asymptotic Optimality of MMCE  
It is well known [19; 20] that the maximum number of maximal cliques in a graph with \(n\) vertices is \(3^{n/3}\). The same asymptotic bound holds for the maximum number of maximal bicliques [21]. In the case of bipartite graphs, however, the upper limit on the number of maximal bicliques drops to \(2^{n/2}\)[22]. This prompts the following question: how many \(k\)-partite cliques can reside in a \(k\)-partite graph when \(k\) exceeds 2? We now resolve this issue, and in so doing establish that MMCE achieves the best possible asymptotic complexity. Specifically, we will prove that the number of maximal \(k\)-partite cliques in a \(k\)-partite graph can essentially be as large as \(3^{n/3}\) whenever \(k\) is at least 3, and thus that any algorithm to enumerate these cliques must take at least \(\Omega(3^{n/3})\) time in the worst case. To make this precise, we employ asymptotic equality, denoted by \(\sim\) (tilde), which is defined as follows: \(f(n)\sim g(n)\) iff \(\lim\limits_{n\to\infty}\left(\frac{f(n)}{g(n)}\right)=1\). **Theorem 2. ** _For each \(k\geq 3\), there are infinitely many \(k\)-partite graphs for which the number of maximal \(k\)-partite cliques is \(\sim\)\(3^{n/3}\)._  
**Proof of Theorem 2. ** An upper bound of \(3^{n/3}\) is achieved by combining Observation 2.1 and the aforementioned result for general graphs from [19; 20]. Our task thus reduces to showing that this bound is asymptotically tight for an infinite set of \(k\)-partite graphs whenever \(k\) exceeds 2. For this, we construct balanced \(k\)-partite graphs specific to \(k=3\), \(k=4\), \(k=5\), and \(k\geq 6\), each with \(\Omega(3^{n/3})\) maximal \(k\)-partite cliques. For the \(k=3\) case, let \(n\) be evenly divisible by 3, and let \(p=n/3\). Let \(G\) result from the removal of the edges of \(p\) disjoint triangles from a balanced complete tripartite graph of order \(n\). More formally, let \(G\) denote a tripartite graph whose vertices are arranged in partite sets \(X\), \(Y\), and \(Z\), each set of cardinality \(p\), with \(X=\{x_{1},\,x_{2},\,\ldots,\,x_{p}\}\), \(Y=\{y_{1},\,y_{2},\,\ldots,\,y_{p}\}\) and \(Z=\{z_{1},\,z_{2},\,\ldots,\,z_{p}\}\), and whose edges are \(\{(x_{i}\),\(y_{j})\,|\,i\
eq j\}\cup\{(x_{i},z_{k})\,|\,i\
eq k\}\cup\{(y_{j},z_{k})\,|\,j\
eq k\}\). Inspired by the technique pioneered in [20], we consider any tripartition \(\{I,J,K\}\) of the set \(S=\{1,\,2,\ldots,\,p\}\). \(I,J\) and \(K\) are therefore nonempty, pairwise disjoint subsets whose union is \(S\). Observe that \(\{A=\{x_{i}\,|\,i\in I\}\), \(B=\{y_{j}\,|\,j\in J\}\), \(C=\{z_{k}\,|\,k\in K\}\}\) denotes a maximal triclique in \(G\). We take advantage of this natural bijection between tripartitions of \(S\) and maximal tricliques in \(G\), enumerating the former in order to count the latter. Setting \(a=\,|\,A\,|\,=\,|\,1\,|\) and \(b=\,|\,B\,|\,=\,|\,1\,|\), nonemptiness requires that every tripartition satisfies \(1\leq a\leq p-2\) and \(1\leq b\leq p-a-1\). For any fixed \(a\) and \(b\), the number of distinct tripartitions is \(\left( \begin{array}{c}p\\ a\end{array} \right)\left( \begin{array}{c}p-a\\ b\end{array} \right)\). Thus, the total number of tripartitions of \(S\) is \(\sum_{a=1}^{p-2}\sum_{b=1}^{p-a-1}\left( \begin{array}{c}p\\ a\end{array} \right)\left( \begin{array}{c}p-a\\ b\end{array} \right)\) which, as we show in Appendix A, equals \(3^{n/3}-3(2^{n/3}-1)\). Assigning this function to \(f(n)\) and \(3^{n/3}\) to \(g(n)\), it follows that \(\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}=1\), from which we conclude that the number of maximal tricliques in the family of graphs described by \(G\) is \(\sim\)\(3^{n/3}\). For the \(k=4\) case, let \(n\) be evenly divisible by 12, and let \(p=n/12\).