Talk:Parity graph

Permutations and transpositions

Consider a graph whose vertices are bijections from {1, ..., n} to itself, and two vertices ƒ and g are connected by an edge precisely if the composition of either of them with some transposition (i.e. some bijection with exactly two non-fixed points, which simply interchanges those two points) yields the other. Then that is a parity graph. Should that example be mentioned in the article? Michael Hardy (talk) 17:12, 28 September 2016 (UTC)[reply]

That graph (a certain Cayley graph for the symmetric group) is bipartite — each edge connects vertices representing opposite permutation parity. All bipartite graphs are parity graphs, of course, but as bipartite graphs are so much more familiar I doubt that listing specific instances of them would make good examples here. —David Eppstein (talk) 17:25, 28 September 2016 (UTC)[reply]

I didn't have in mind specific instances of them, but just the general concept. The fact that different ways of factoring the same permutation into transpositions always yield number of factors having equal parity is probably the first place where many undergraduates encounter this idea, even though they wouldn't see a definition of "parity graph" or anything in graph-theoretic language. Michael Hardy (talk) 23:43, 29 September 2016 (UTC)[reply]

The point is that it's a different concept. The parity of a permutation defines a two-coloring of the graph of permutations, and graphs that can be two-colored should be thought of as bipartite graphs. Parity graphs are not (graphs whose vertices have parity), they are (graphs whose pairs of vertices have parity), a more general concept that this example doesn't illustrate. In the meantime, I have added an illustration to the graph that I hope gets the concept across more clearly. —David Eppstein (talk) 00:11, 30 September 2016 (UTC)[reply]