Maximum number of sizes of maximal cliques for a graph?

Question

I was wondering what is the maximum possible number of distinct sizes of maximal cliques in a graph with fixed order $N$, and if anyone can share or point me to a proof or literature on this topic. To clarify, if a graph has 4 vertices, it could have maximal cliques of size 1 and 2, or 1 and 3, (or all maximal cliques of size 4, all of size 3, all of size 2, etc.) but we can't have more than 2 distinct sizes of maximal cliques.

I've found a way to build graphs with $\left\lfloor\frac{N + 1}{2}\right\rfloor$ sizes of maximal cliques (start at isolated vertex, then add two more vertices as an edge, then add two more vertices linked to each other and to 1 of the vertices of the edge to form a triangle, then add two more vertices linked to each other and to 2 of the vertices of the triangle to form a maximal 4-clique, etc.) My hunch is that we can't do better than $\left\lfloor\frac{N + 1}{2}\right\rfloor$ sizes of maximal cliques, but I'm not sure how to prove this or even if it is true because there are so many possible intersections between maximal cliques going on at once with higher number of vertices, and maybe there are better ways of having the maximal cliques intersect to save space than the method I described above. Any help would be much appreciated.

Answer 1

(Too long for a comment.) You can reuse some vertices. For example, you can make maximal cliques of cardinalities $\{\, 1, 2, 3, 4, 5, 6\,\}$ using $10$ vertices only. Let the graph have vertices $\{\,1, 2, \ldots, 10\,\}$, maximal cliques $\{\,\{\,1\,\}, \{\,2, 3\,\}, \{\,2, 4, 5\,\}, \{\,4, 5, 6, 7\,\}, \{\,5, 6, 7, 8, 9\,\}, \{\,3, 6, 7, 8, 9, 10\,\}\,\}$ and no other edges. Here instead of adding the vertex $11$ I reuse the vertex $3$.

The vertex $4$ can be reused after eliminating vertices $3$ and $6$–$9$, i. e., graph on $21$ vertices can have maximal cliques of $12$ distinct cardinalities.

The vertex $2$ can be used together with the vertex $4$ right after eliminating vertex $10$, thus graph on $22$ vertices can have maximal cliques of $13$ distinct cardinalities.

It is hard to estimate usefulness of this modification, but it definitely gives something like $\frac{n}{2} + \Omega(\sqrt n)$ of distinct cardinalities of maximal cliques for a graph on $n$ vertices. Note that vertices can be reused more than once, and this complicates everything even more.

---

Another idea allows to get maximal cliques of cardinalities $\{\, 1, 2, 3, 4, 5\,\}$ using $8$ vertices only. Let the graph have vertices $\{\,1, 2, \ldots, 8\,\}$, maximal cliques $\{\,\{\,1\,\}, \{\,2, 3\,\}, \{\,2, 4, 5\,\}, \{\,3, 6, 7, 8\,\}, \{\,4, 5, 6, 7, 8\,\}\,\}$ and no other edges.

It allows to get $8$ distinct cardinalities of maximal cliques on $13$ vertices only: $\{\,\{\,1\,\}, \{\,2, 3\,\}, \{\,2, 4, 5\,\}, \{\,3, 6, 7, 8\,\}, \{\,2, 9, 10, 11, 12\,\}, \{\,4, 6, 7, 8, 9, 10\,\}, \{\,5, 6, 7, 8, 11, 12, 13\,\}, \{\,6, 7, 8, 9, 10, 11, 12, 13\,\}\,\}.$

Here I started from the maximum clique and added smaller maximal cliques, using vertices of the maximum one and one new, until I could use these new vertices to make smaller components. Again we have $\frac{n}{2} + \Omega(\sqrt n)$ of distinct cardinalities of maximal cliques for a graph on $n$ vertices. And again reusing existing vertices is not limited by any constant number of times.

Maybe in some cases it even makes sense not to use the isolated vertex. I mean if adding two vertices would give three new cardinalities, we can remove the isolated vertex and probably add it later. There are many options to consider.

On the other hand I don't see any good upper bound.

Answer 2

The maximum number of maximal clique cardinalities in graph on $n$ vertices is $n - \Theta(\log n)$.

Firstly let construct such a graph. Let $k$ be an integer such that $2^{k - 1} + 2(k - 1) < n \le 2^k + 2k$. Then $k = \log_2 n + o(\log n)$. The graph $G$ has two cliques $\{\,1, 2, \ldots, n - k\,\}$ and $\{\,n - k + 1, n - k + 2, \ldots, n\,\}$, big and small. Also it has some edges between vertices of these two cliques. Vertex $n - k + i$ ($1 \le i \le k$) is adjacent to all vertices except $\{\,2^{i - 1} + i - 1, 2^{i - 1} + i, \ldots, \min\{\,2^i + i - 1, n - k\,\}\,\}$. I. e., the $i$th vertex from the small clique (except the $k$th vertex) is not adjacent to $2^{i - 1} + 1$ vertices from the big clique, and these sets are non-intersecting. Each vertex from the big clique is not adjacent to exactly one vertex from the small clique. If a clique contains all vertices of the small clique, then it is maximal one of cardinality $k$. If a clique contains all vertices of the small clique except $n - k + 1$, then it's maximum superclique has also vertices $1$ and $2$, and cardinality $k + 1$. And so on. If a clique contains all vertices of the small clique except $v_1 < v_2 < \cdots < v_{\ell}$, then it's maximum superclique includes also $\bigcup_{i = 1}^{\ell}\{\,2^{v_i - 1} + v_i - 1, 2^{v_i - 1}, \ldots, \min\{\,2^{v_i} + v_i - 1, n\,\}\,\}$, i. e., has cardinality $$k - \ell + 2^{v_1} + 1 + 2^{v_2} + 1 + \cdots + 2^{v_{\ell - 1}} + 1 + \min\{\,2^{v_\ell}, n - 2k - 2^{k - 1} + 1\,\} + 1 \\= k + 2^{v_1} + 2^{v_2} + \cdots + 2^{v_{\ell - 1}} + \min\{\,2^{v_\ell}, n - 2k - 2^{k - 1} + 1\,\}.$$ It means that every number from $\{\,k, k + 1, \ldots, n - k\,\}$ is a cardinality of some maximal clique in the graph $G$. (Just take a number $x$, represent $x - k$ as a sum of powers of $2$ and take vertices of the small clique corresponding to missing powers together with all possible vertices of the big clique; however if vertex $n$ is also not included, then represent the number $x - k - n + 2k + 2^{k - 1} - 1$ as a sum of powers of $2$ and so on.) Thus for $n$ vertices we have $n - 2k + 1 = n - 2\log_2 n + o(\log n)$ different cardinalities of maximal cliques.

Secondly let's prove an upper bound. Note that if there are two different maximal cliques $C_1$ and $C_2$, then there exist vertices $v_1 \in C_1 \setminus C_2$ and $v_2 \in C_2 \setminus C_1$. Suppose that a graph $G$ on $n$ vertices contains maximal cliques of $q > n - \lfloor\log_2 n\rfloor$ cardinalities. Therefore it has a clique $C$ (may be not maximal) of cardinality $n - \lfloor\log_2 n\rfloor + 1$. Let's consider the set $S = V(G) \setminus C$ with the remaining $k = \lfloor\log_2 n\rfloor - 1$ vertices. There are at most $2^k$ cliques containing vertices from $S$ only. Each such clique has at most one way to become maximal being augmented by some vertices from $C$. Therefore the graph $G$ contains at most $2^k$ maximal cliques. But $$q \le 2^k = 2^{\lfloor \log_2 n\rfloor - 1} \le 2^{\log_2 n - 1} = \frac{n}{2} \le n - \log_2 n \le n - \lfloor\log_2 n\rfloor< q$$ for all $n \ge 4$. This contradiction proves that for $n \ge 4$ any graph on $n$ vertices contains maximal cliques of at most $n - \log_2 n$ cardinalities.

P. S. I guess that the remaining gap should be closed by making better upper bound.