Timeline for Complete graph invariants?
Current License: CC BY-SA 2.5
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 2, 2023 at 9:15 | comment | added | The Amplitwist | Reposting a link mentioned in a previous comment so that it appears in the "Linked" questions list: Natural models of graphs? | |
| Jan 11, 2013 at 20:46 | comment | added | Aaron Meyerowitz | If the spectrum was part of the mix, would that be as the Characteristic polynomial or as a multiset of reals? In the latter case, who knows how far you would have to go to be sure that you did have a match. I imagine one could devise a very long procedure returning a real number which would be unique to each isomorphism class, even if truncated 10^10^10^10^10^|G| places out to give a rational | |
| Sep 19, 2012 at 10:56 | answer | added | Hans-Peter Stricker | timeline score: 3 | |
| Jul 15, 2011 at 7:19 | answer | added | Wesley Calvert | timeline score: 4 | |
| Jan 14, 2010 at 17:37 | vote | accept | Harrison Brown | ||
| Jan 14, 2010 at 2:07 | answer | added | Greg Kuperberg | timeline score: 29 | |
| Jan 13, 2010 at 21:57 | answer | added | Douglas S. Stones | timeline score: 8 | |
| Jan 13, 2010 at 20:12 | comment | added | Gil Kalai | I do not see how to compare chromatic symmetric polynomials in P. In some sense comparing them (I am not even talking about calculating them) is more complicated than comparing the trees. You can regard the deck of isomorphism types of edge-deleted subgraphs (or vertex deleted subgraphs) as a kind of graph invariant of the type you want. | |
| Jan 13, 2010 at 14:01 | comment | added | Harrison Brown | Gil: Qiaochu's example was one of the things I had in mind in asking the question. I don't know about planar graphs. | |
| Jan 13, 2010 at 13:26 | comment | added | Qiaochu Yuan | Gil: one suggestion for trees is the chromatic symmetric polynomial (garden.irmacs.sfu.ca/?q=op/…). | |
| Jan 13, 2010 at 13:23 | comment | added | Gil Kalai | This seems to be a very difficult problem. You can think about the case of bounded degree graphs where it is known that graph isomorphism is in P. Still no set of invariants is known. (Do you have any suggestions for trees? for planar graphs?) For general graphs although there are good reasons to believe that graph isomorphism is in co NP there are also reasons to believe that showing it will be very hard. "Under deradomization" is not something to take lightly. (Here are some examples: gilkalai.wordpress.com/2009/12/06/four-derandomization-problems ) | |
| Jan 13, 2010 at 11:43 | comment | added | Hans-Peter Stricker | That's funny: In <a href="mathoverflow.net/questions/11647/… most recent post</a> I try to make sense of this notion of naturality. And more than that: I definitely had your question at the top of my pipeline, but now I will postpone it and watch the discussion here. | |
| Jan 13, 2010 at 10:58 | history | edited | Harrison Brown | CC BY-SA 2.5 |
added 882 characters in body
|
| Jan 13, 2010 at 8:53 | comment | added | Thorny | Enumerate the finite graphs, assign to each graph its index in the sequence. Comparing the invariant is easy, calculating it, not so much. I assume you wanted some kind of restriction on the invariants, so this is excluded? | |
| Jan 13, 2010 at 7:05 | answer | added | Mariano Suárez-Álvarez | timeline score: 7 | |
| Jan 13, 2010 at 6:37 | history | edited | Harrison Brown | CC BY-SA 2.5 |
added 420 characters in body
|
| Jan 13, 2010 at 6:28 | history | asked | Harrison Brown | CC BY-SA 2.5 |