Return to Question

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

$$q(g)=\min_T \min_{A\subset T} |T|-|A|$$

Where $T$ is a transversal of the maximum cliques; 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 this: how large can this quantity get compared to the number of vertices $|V|$, of the graph $G$? The key figure of merit is

$$q_k= \sup_{G, \, \omega(G)=k}q_r(G) ,$$ where $$q_r(G)=\frac{q(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.

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.

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

$$q(g)=\min_T \min_{A\subset T} |T|-|A|$$

Where $T$ is a transversal of the maximum cliques; 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 this: how large can this quantity get compared to the number of vertices $|V|$, of the graph $G$? The key figure of merit is

$$q_k= \sup_{G, \, \omega(G)=k}q_r(G) .$$ where $$q_r(G)=\frac{q(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.

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

$$q(g)=\min_T \min_{A\subset T} |T|-|A|$$

Where $T$ is a transversal of the maximum cliques; 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 this: how large can this quantity get compared to the number of vertices $|V|$, of the graph $G$? The key figure of merit is

$$q_k= \sup_{G, \, \omega(G)=k}q_r(G) ,$$ where $$q_r(G)=\frac{q(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.

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

$$\min_T \min_{A\subset T} |T|-|A|$$

Where $T$ is a transversal of the maximum cliques; 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 this: how large can this quantity get compared to the number of vertices $|V|$, of the graph $G$?

In particular, I would also be interested in how this varies with the clique number $k$. Both upper and lower bounds are of great interest.

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

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

$$q(g)=\min_T \min_{A\subset T} |T|-|A|$$

Where $T$ is a transversal of the maximum cliques; 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 this: how large can this quantity get compared to the number of vertices $|V|$, of the graph $G$? The key figure of merit is

$$q_k= \sup_{G, \, \omega(G)=k}q_r(G) .$$ where $$q_r(G)=\frac{q(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.