If a graph has exponentially many maximal cliques, what can we say about how many maximal cliques each vertex belongs to?

69 Views Asked by At

My question is motivated by the following example: For $n \geq 1$, let $G$ be the complete $n$-partite graph on $2n$ vertices, i.e., every vertex of $G$ is connected to all others except one. Then $G$ has $2^n$ maximal cliques, with each one formed by choosing a vertex from each of the $n$ pairs of disconnected nodes. In this case, it is easy to see from the structure of $G$ that each vertex belongs to $2^n/2 = 2^{n-1}$ maximal cliques.

More generally, what can we say (if anything) about the number of maximal cliques each vertex of $G$ belongs to, if we do not know its structure, but only that $G$ is connected and has exponentially many maximal cliques?

In short, I would like to find out to what extent it is possible to derive local information about maximal clique involvement of vertices in $G$ from the global property of the number of maximal cliques $G$ has.

My hypothesis is the following, though I am unsure about the quantifiers and asymptotics.

Let $G$ be an $n$-vertex connected graph with $\Omega(f(n))$ maximal cliques for some exponential function $f(n)$. Then there always exists a subset $S$ of $\Omega(n)$ vertices such that each vertex of $S$ belongs to $\Omega(f(n))$ maximal cliques.

Proof. Suppose not. That is, suppose that for all subsets $S$ of $G$ containing $\Omega(n)$ vertices, each vertex of $S$ belongs to $O(g(n))$ maximal cliques for some subexponential function $g(n)$. By definition, there exist constants C,D > 0 such that for $n$ sufficiently large we have the following: For all subsets $S$ of size at least $Cn$, each vertex of $S$ belongs to at most $Dg(n)$ maximal cliques. Since $|G|=n$, we can assume that $0 < C \leq 1$. Then letting $S=X$, we have that each vertex of $X$ belongs to at most $Dg(n)$ maximal cliques, so the total number is at most $n\cdot Dg(n)$. However, we have that $n\cdot Dg(n) \neq \Omega(f(n))$, since $f(n)$ is exponential and $g(n)$ is subexponential, a contradiction.

1

There are 1 best solutions below

0
On BEST ANSWER

The proof in the question does not work, because it assumes that in a set $S$, either every vertex lies in at least $\Omega(f(n))$ maximal cliques, or at most $O(g(n))$ maximal cliques. This is a false dichotomy for two reasons: not every vertex in $S$ has to do the same thing, and there is a large gap between $\Omega(f(n))$ and $O(g(n))$.


However, we can still prove a result along these lines. I have not stated it asymptotically, but we could do that too.

Theorem. For all $c>1$ there is an $\epsilon>0$ with the following property: if an $n$-vertex graph $G$ has $c^n$ maximal cliques, then there is a subset $S \subseteq V(G)$ with $|S| \ge \epsilon n$ such that every vertex in $S$ lies in at least $\epsilon c^n$ maximal cliques.

Proof. For convenience, let the clique degree $\operatorname{cd}(v)$ of a vertex $v$ be the number of maximal cliques of $G$ containing $v$.

Given $c$, we choose $\epsilon$ to satisfy, for all positive integers $n$ at once, the inequality $$\sum_{k=0}^{4\epsilon n} \binom nk < \frac12 c^n.$$ (See the answers to this question for details. It's enough to satisfy the inequality for all sufficiently large $n$, because if we can do that, we can adjust $\epsilon$ to also be sufficiently small to address the finitely many smaller exceptions.)

The result is that if an $n$-vertex graph $G$ has $c^n$ maximal cliques, then at most $\frac12 c^n$ of them can have size less than $4\epsilon n$. Therefore $$\sum_{v \in V(G)} \operatorname{cd}(v) > 2\epsilon n c^n,$$ because a clique of size $k$ is counted $k$ times by this sum, and there are more than $\frac12 c^n$ cliques that are counted at least $4\epsilon n$ times.

Suppose for the sake of contradiction that fewer than $\epsilon n$ vertices have clique degree more than $\epsilon c^n$. Each of those vertices still has clique degree at most $c^n$; that's how many maximal cliques there are! Therefore the vertices with large clique degree contribute at most $\epsilon n \cdot c^n$ to the sum. The remaining vertices have clique degree at most $\epsilon c^n$, and there's at most $n$ of them, so they contribute at most $n \cdot \epsilon c^n$ to the sum.

We get a total of less than $2\epsilon nc^n$, which contradicts our lower bound on the sum! So there must be at least $\epsilon n$ vertices with clique degree at least $\epsilon c^n$.