Skip to main content

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