Timeline for Complete graph invariants?
Current License: CC BY-SA 2.5
14 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Feb 16, 2014 at 7:34 | comment | added | Leox | The problem becomes simpler if we consider simple unlabeled graphs. Then for $n = 5$ there are 5 polynomial invariants and for $n=6$ there are 12 ones. They distinguish non-isomorph graphs. | |
Jan 14, 2010 at 16:28 | history | edited | Mariano Suárez-Álvarez | CC BY-SA 2.5 |
added 24 characters in body
|
Jan 14, 2010 at 4:18 | comment | added | Mariano Suárez-Álvarez | It would be a very interesting development to remove the quotes around 'proving', IMO. | |
Jan 13, 2010 at 22:00 | comment | added | David E Speyer | Certainly not, you were perfectly honest about the difficulties. I was "proving" to Steven Sam that the number of polynomials should grow rapidly. | |
Jan 13, 2010 at 21:38 | comment | added | Mariano Suárez-Álvarez | David, I've never claim this is practical! :) | |
Jan 13, 2010 at 20:58 | comment | added | David E Speyer | If their number were polynomial in n, and their degrees were not too large, then Mariano's suggestion would actually be practical. Since graph isomorphism is hard, I deduce that there are either many invariants, or the invariants have high degree :). | |
Jan 13, 2010 at 20:19 | history | edited | Mariano Suárez-Álvarez | CC BY-SA 2.5 |
added 521 characters in body
|
Jan 13, 2010 at 19:29 | comment | added | Steven Sam | Very interesting answer. But the number of generating invariants should be larger than polynomial in n, no? | |
Jan 13, 2010 at 7:54 | comment | added | Mariano Suárez-Álvarez | It is very hard to explicitely compute those invariants. For $n<=4$ you can do it by hand; for $n=5$ it was intractable last time I checked. See, for example, portal.acm.org/citation.cfm?id=377612 | |
Jan 13, 2010 at 7:41 | comment | added | Harrison Brown | Good point about the spectrum. This still feels a bit like sidestepping the question, but I'll sleep on it and maybe try to work out a small case by hand tomorrow, and see if my opinion changes. | |
Jan 13, 2010 at 7:35 | comment | added | Mariano Suárez-Álvarez | By the way, this works because invariant functions separate orbits. | |
Jan 13, 2010 at 7:27 | comment | added | Mariano Suárez-Álvarez | This attaches to each graph a vector of zeroes and ones whose length depends on $n$ (but for which there are bounds), the spectrum attaches to each graph a vector of real numbers whose length also depends on $n$. | |
Jan 13, 2010 at 7:19 | comment | added | Harrison Brown | Hmm. I don't know much invariant theory, but I think I get why this "should" work. That said, I'm not actually convinced this is in the spirit of the question either -- partly because I was hoping for a number of invariants independent of the order of the graph, but mostly because "turn it into algebra" doesn't really tell you much by itself (although this does look more approachable than something like "pick a canonical labeling by AoC.") Upvoted anyway, though, since it's technically right and something I hadn't thought about. | |
Jan 13, 2010 at 7:05 | history | answered | Mariano Suárez-Álvarez | CC BY-SA 2.5 |