Timeline for Bounding a graph invariant
Current License: CC BY-SA 3.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S May 2, 2017 at 13:25 | history | suggested | Peter Heinig | CC BY-SA 3.0 |
Improved most recent edits by the OP to make them consistent with the notational suggestion in one of the anwers. In particular, the OP's main interest, namely $q(G)$, has been given a simpler notation, not emphasizing the `relativeness' of it (since this is what the OP is interested in anyway).
|
| May 2, 2017 at 13:23 | review | Suggested edits | |||
| S May 2, 2017 at 13:25 | |||||
| May 2, 2017 at 12:05 | history | edited | A Simmons | CC BY-SA 3.0 |
edited body
|
| May 2, 2017 at 12:00 | history | edited | A Simmons | CC BY-SA 3.0 |
added 118 characters in body
|
| May 2, 2017 at 10:14 | answer | added | Ben Barber | timeline score: 0 | |
| May 2, 2017 at 9:48 | history | edited | A Simmons | CC BY-SA 3.0 |
added 143 characters in body
|
| Apr 29, 2017 at 15:52 | answer | added | Peter Heinig | timeline score: 2 | |
| Apr 28, 2017 at 18:48 | comment | added | David Roberson | Well, now we know we can restrict to minimal transversals. So no more irritation. | |
| Apr 28, 2017 at 18:19 | comment | added | Peter Heinig | One can take the view that the structure of the set of structures being optimized over, and in particular the structure of the optimizers, is at least as important as the bare value of the objective function. From that point of view, the admissibility of non-minimal transversals is irritating. It adds non-meaningful noise to the set of structures being optimized over. | |
| Apr 28, 2017 at 17:59 | comment | added | David Roberson | 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. | |
| Apr 28, 2017 at 17:57 | comment | added | David Roberson | @PeterHeinig I don't understand your comment with $T$ and $T^+$. You are taking min over $T$ and $A$, so in the case you describe the invariant will be equal to zero, and $T^+$ does not "contribute" to it. In general there is no need to consider non-minimal $T$ because if $T' \subseteq T$ is a transversal then it will give a value at least as good as $T$ in the min. This is because if $A$ is an independent set contained in $T$, then $|T'| - |T' \cap A| \le |T| - |A|$. | |
| Apr 28, 2017 at 17:29 | comment | added | Peter Heinig | The latter is not contradictory, but the non-minimality of $T$ might be offputting to some of your readers. Some more statements of what is intended in your problem-statement might be encouraging for people to seriously consider the question. | |
| Apr 28, 2017 at 17:27 | comment | added | Peter Heinig | Had another look. The question has become better. Question: is it intentional that the transversal is not required to be inclusion-minimal w.r.t. the property of being a transversal? It appears strange not to require this, for several reasons. One of them is: there are $G$ having $T$ which themselves are independent, and hence are hit by the full force of the penalty-subtraction, hence contribute nothing, but which can artificially be extended by another vertex not in any maximum clique to another transversal $T^+\supseteq T$ which does induce an edge, and then this $T^+$ contributes. | |
| Apr 28, 2017 at 15:26 | history | edited | A Simmons | CC BY-SA 3.0 |
deleted 45 characters in body
|
| Apr 28, 2017 at 15:20 | comment | added | Peter Heinig | And, less nomenclaturally speaking: "$A$ is an independent set in the subgraph induced by restriction of $G$ to the vertices is $T$" is, while not contradictory, logically redundant and potentially confusing: if a set $A$ of vertices is an independent set within any induced subgraph of any graph, then $A$ is itself an independent set in the ambient graph. (By requiring that the intermediate subgraph be induced, you have already ruled out that $A$ could induce a non-independent set in the ambient graph. It will improve the question to simply write "and $A$ is an independent set in $G$." | |
| Apr 28, 2017 at 15:17 | comment | added | A Simmons | @PeterHeinig, thanks, I've taken your advice. I had used $d$ because it's the quantum dimension for the motivating problem, but obviously clarity here is more important. | |
| Apr 28, 2017 at 15:14 | history | edited | A Simmons | CC BY-SA 3.0 |
deleted 10 characters in body
|
| Apr 28, 2017 at 15:12 | comment | added | Peter Heinig | 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$". | |
| Apr 28, 2017 at 14:09 | comment | added | David Roberson | Sorry, I should have said that maybe $\chi(G) - \xi(G)$ upper bounds your invariant. | |
| Apr 28, 2017 at 13:09 | comment | added | David Roberson | 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? | |
| Apr 28, 2017 at 13:00 | comment | added | A Simmons | @DavidE.Roberson pretty much spot on | |
| Apr 28, 2017 at 12:58 | comment | added | David Roberson | 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? | |
| Apr 28, 2017 at 12:56 | review | First posts | |||
| Apr 28, 2017 at 13:01 | |||||
| Apr 28, 2017 at 12:49 | history | asked | A Simmons | CC BY-SA 3.0 |