Bounding a graph invariant

Question

We are given a graph $G=(V,E)$, which has clique number $k$. The graph invariant in question is given by

$$q_{\mathrm{a}}(G)=\min_T \min_{A\subset T} |T|-|A|$$

where $T$ is a transversal of the maximum cliques of $G$; that is, a set with nonempty intersection with every $k$-clique, and $A$ a subset of $T$ that is an independent set in $G$. The question is: how large can $q_{\mathrm{a}}(G)$ get compared to the number of vertices $|V|$? The key figure of merit is

$$q_k= \sup_{G, \, \omega(G)=k}q(G) ,$$ where $$q(G)=\frac{q_{\mathrm{a}}(G)}{|G|}.$$

Both upper and lower bounds are of great interest.

This problem is motivated by quantum foundations considerations, that I could elucidate if helpful.

Answer 1

The supremum $q$ of the quantity $q(G)$ you are interested in, over the class of all finite graphs, is at least $\frac13$.

For the time being, I do neither know whether $q$ is larger than $\frac13$, nor whether the value $\frac13$ can be attained by any finite graph.

Here are some details.

It can be proved that there is a sequence of finite graphs on which the quantity converges to $\frac13$.

This sequence consists of triangle-free, three-colorable, Cayley graphs only: the sequence $\mathrm{And}_t$ of Andrásfai graphs (cf. e.g. the book of Godsil and Royle on algebraic graph theory).

Let $q_{\mathrm{absolute}}(G)$ denote the graph invariant (FiniteGraphs)$\longrightarrow$ $\mathbb{N}$ you defined.

Let $q(G) := q_{\mathrm{relative}}(G) := \frac{1}{\lvert G\rvert} q_{\mathrm{absolute}}(G)$ the quantity about which you asked how large it can get when $G$ ranges over all finite graphs.

It can be proved that the supremum of $q(G)$ over the class of all graphs is at least $\frac13$.

Since $\mathrm{And}_t$ is triangle-free, i.e., $\omega(\mathrm{And}_t)=2$, a transversal of the maximum cliques is equivalent to a cover of the edges by vertices (usually, and somewhat counterintuitively, called a vertex cover in contemporary graph theory texts).

So for any triangle-free graph $G$, the quantity $\min_T\lvert T\rvert$, in your sense, without the penalty-subtrahend, is just $\tau(G)$, the covering number of $G$.

This will now be used to give a rough lower bound on your quantity $q(G)$. The penality-subtrahend will just be estimated away, making use of the fact that Andrásfai graphs have relatively small independence number, using a bound in terms of the independence number (I decided not to think about how much the bound of $\frac13$ can be improved if one does not do this; this would require an analysis of the structure of the set of all independent sets of $\mathrm{And}_t$, which should be a straightforward task).

For every natural number $t$, the $t$-th Andrásfai graph $\mathrm{And}_t$ has

$\lvert \mathrm{And}_t\rvert = 3t-1$,

$\alpha(\mathrm{And}_t) = t = \tfrac13(\lvert \mathrm{And}_t\rvert+1)$,

$\tau(\mathrm{And}_t) = 2t-1 = \lvert \mathrm{And}_t\rvert - t$.

We can now argue as follows, abbreviating $n_t:=\lvert\mathrm{And}_t\rvert$,

$q$ $=$ $\sup_{\text{allfinitegraphs}} q(G)$

$\geq$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{n_t}(\min_T \min_{A\subseteq T} \lvert T\rvert - \lvert A\rvert)(\mathrm{And}_t)$

$\geq$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{n_t}(- \alpha( \mathrm{And}_t ) + (\min_T \lvert T\rvert )(\mathrm{And}_t) )$

$=$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{n_t}(- \tfrac13(n_t+1) + n_t - \frac13(n_t+1)) $

$=$

$\sup_{t\in\mathbb{Z}_{\geq 2}}(\tfrac13 - \frac{2}{3n_t} )$

$=$

$\frac13$

the latter since arbitrarily large Andrásfai graphs exist.

Now let us write, for any natural number $k$,

$$q_k := \sup_{\text{all finite graphs $G$ with $\omega(G)=k$}}q_{\mathrm{relative}}(G) $$

for the quantity you are more intersted in. A more important question than what value the single universal constant $q\in[\frac13,1]$ has, is to analyse the function

$$ S: \mathbb{N}\rightarrow [0,1] $$ $$ k\mapsto q_k$$.

It would be helpful for systematic reasons if others would use this notation.

Answer 2

Random graphs might show that this parameter can be at least as large as $n/ \log n$. As is often the case there are some details to be checked, but I'd try the following.

Let $G \sim G_{n,1/2}$. Then the clique and independence number of $G$ are both around $2\log_2 n$ with high probability, and the chromatic number is around $n / 2\log_2 n$. Bollobás's proof of this fact goes by showing that the independence number of $G$ remains around $2\log_2 n$ even after we've already removed a large number of independent sets of that size. So I expect $G$ to contain about $n / 2\log_2 n$ disjoint maximal cliques, giving $|T| \geq n / 2\log_2 n$. (And $|A| \leq 2\log_2 n$ as are there are no larger independent sets in $G$.)

It seems unlikely that the maximal cliques are conspiring to share vertices. More worrying is that the maximal cliques might not all have the same size, but perhaps enough of them do, or can be fixed up without doing too much damage to the independence number.