# Bounding a graph invariant

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.

• Do the max cliques correspond to measurements (presumably von Neumann measurements in dimension d)? The edges are between mutually exclusive (i.e. orthogonal) measurement outcomes, The invariant is 0 if an only if there is an independent set hitting every max clique, i.e., the set is not a Kochen-Specker set? So the invariant gives a combinatorial measure of how non-classical a collection of measurements are? Am I close? – David Roberson Apr 28 '17 at 12:58
• @DavidE.Roberson pretty much spot on – A Simmons Apr 28 '17 at 13:00
• Cool. Nice idea. If G is the orthogonality graph of any set of vectors in dimension d (that contains at least one full measurement), then you will have $\chi(G) \ge \xi(G) = \omega(G) = d$ where $\chi$, $\xi$, and $\omega$ are the chromatic number, orthogonal rank, and clique number respectively. If it is a KS set, then you will have $\chi(G) > \xi(G) = d$ (the converse is not true). So maybe $\chi(G) - \xi(G)$ is somehow related to your invariant, perhaps it lower bounds it? – David Roberson Apr 28 '17 at 13:09
• It will improve the question if you polished the terminology a bit: the usual term for "has maximum cliques of size $d$" in contemporary graph theory is "has clique number $k$". The present formulation grates a bit in three respects: "clique" is often taken as a synonym for "inclusion-maximal complete subgraph", "size" often as a synonym for "number of edges" (while you mean "order", i.e., number of vertices), and the letter "$d$" usually refers to some $d$edgree. It would improve the question if you wrote "has clique number $k$". – Peter Heinig Apr 28 '17 at 15:12
• And personally I think the question is fine. Also, I use $k$ for degree all the time, so maybe he should change it back to $d$ :P. – David Roberson Apr 28 '17 at 17:59

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.

• I reckon that to make your question into a resarch question, you should filtrate your question by asking for the dependence of $\sup q$ on the clique number. More precisely, you are probably more interested in what the value of $\sup_{\text{all finite graphs$G$with$\omega(G)=k$}} q_{\mathrm{relative}}(G)$ is. This then would rule out any answer that focuses one one value of the clique number only, in particular, would rule out answering your question by triangle-free graphs (which already provide a non-trivial lower-bound on your number, though). – Peter Heinig Apr 29 '17 at 17:43
• What a nice start! I'd personally been trying to use the Hadamard graphs as an example family with low independence number but was finding it hard to calculate the $|T|$. I agree with you regarding the dependence on $k$. I'll update the OP. – A Simmons May 2 '17 at 9:47
• Good. Added notation for this. If you like it, then you could introduce the $q$-notation right from the start, to make this thread more systematic.$q$ both for $q$uantity and $q$uantum. – Peter Heinig May 2 '17 at 11:30

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.