This paper studies the following question: Given a surface $\Sigma$ and an integer $n$, what is the maximum number of cliques in an $n$-vertex graph embeddable in $\Sigma$? We characterise the extremal graphs for this question, and prove that the answer is between $8(n-\omega)+2^{ \omega}$ and $8n+{ 3/2} 2^{ \omega}+o(2^{ \omega})$, where $\omega$ is the maximum integer such that the complete graph $K_\omega$ embeds in $\Sigma$. For the surfaces $\mathbb{ S}_0$, $\mathbb{ S}_1$, $\mathbb{ S}_2$, $\mathbb{ N}_1$, $\mathbb{ N}_2$, $\mathbb{ N}_3$ and $\mathbb{ N}_4$ we establish an exact answer.

Categories: math.CO

The maximum number of cliques in a graph embedded in a surface