Isn't a graph to be considered isomorphic to its complement, actually? [closed]

Question

Consider a finite simple graph $G$ with $n$ vertices, presented in two different but equivalent ways:

1. as a logical formula $\Phi= \bigwedge_{i,j\in[n]} \neg_{ij}\ Rx_ix_j$ with $\neg_{ij} = \neg$ or $ \neg\neg$
2. as an (unordered) set $\Gamma = \lbrace [n],R \subseteq [n]^2\rbrace$

In each case the complement $G'$ of $G$ is easily presented and is of course not isomorphic to $G$ (in the usual sense) generally:

1. $ \Phi' = \bigwedge_ {i,j} \neg \neg_{ij}\ R x_i x_j $
2. $\Gamma' = \lbrace [n],[n]^2 \setminus R\rbrace$

Let's state for the moment that the presentation as a logical formula is the more "flexible" one: we can easily omit single literals, leaving it open whether $Rx_ix_j$ or not. But this can be mimicked for set presentation by making it from a pair to a triple $\lbrace[n],R,\neg R \subseteq [n]^2 \setminus R\rbrace$.

Let's call a presentation complete, if it leaves nothing open, i.e. no omitted literal and $\neg R = [n]^2 \setminus R$, resp.

Now, let a graph be given in complete set presentation $\lbrace[n],R,\neg R = [n]^2 \setminus R\rbrace$. Since order in this set should not matter, any sensible definition of "graph isomorphism" should make any graph isomorphic to its complement.

Where and how do I run into trouble when I assume - following this line of reasoning, contrary to the usual line of thinking - that every (finite) graph is isomorphic to its complement?

Answer 1

It is a strange question, but maybe a useful answer can make it a bit better.

Certainly for many purposes a graph will look totally different from its complement. For instance, a graph and its complement have completely different spectra, diameter, perfect matchings, etc. So that side of the question is kind-of lame, I agree.

On the other hand, for some purposes a graph is much the same as its complement. One obvious case is when you are interested in the automorphism group of a graph, or in the computational problem of graph isomorphism. Then you might as well think of a graph as a bicoloring of the edges of a complete graph. It then has a natural extra automorphism given by switching the two colors. More generally a colored graph with $n$ colors is equivalent, for graph isomorphism and graph automorphism questions, to a complete graph with $n+1$ colors. This viewpoint is more useful than you might first think, because a natural partial algorithm and preparatory step in the graph isomorphism and automorphism problems is to recolor every vertex by its valence, then color every edge by the colors of its vertices, etc., until the recoloring process stabilizes. Many graphs can be completely identified this way in practice. Recognizing the equivalence between a graph and its complement makes it easier to understand what these algorithms are really doing.

Even some specific graphs, such as the Higman-Sims graph, are mainly used for their automorphisms and similar purposes, and it might be better to think of them as colorings of a complete graph.

A much deeper example is the perfect graph theorem of Lovasz. The theorem is that a graph is perfect if only if its complement is perfect. For perfect graphs, taking the graph complement is closely related to the dual or polar polytope of a convex polytope.

Answer 2

The usual definition of graph isomorphism implies that in general a graph is not isomorphic to its complement, and it is generally agreed that that definition is sensible. So the claim in your second to last paragraph is false.

Answer 3

OK, I'll bite.

I've never liked the word "graph". Some people use it to mean "set $V$ of 'vertices' a collection $E$ of size-two subsets of $V$". Some mean "set $V$ and a symmetric $V\times V$ matrix valued in nonnegative integers, i.e. a map $V\times V \to \mathbb N$, telling you how often a vertex is connected to another vertex". Some people mean "(finite) one-dimensional CW complex". I tend to mean "finite set $H$ of 'half edges', a partition $E$ of $H$ into blocks of size $2$, and a partition $V$ of $H$ which is allowed to have blocks of arbitrary size (including empty blocks)". The reason I like the last one is that it's the definition that gets the correct notion of "autmorphism" for the purposes of evaluating Feynman-diagrammatic integrals. But it's the wrong one for many other applications. Note that for this definition, as for "one-dimensional CW complexes", it doesn't make sense to talk about the "complement".

So, anyway, I'm perfectly happy thinking about the category for which a generic object is a set $V$ along with a partition of $V \choose 2$ (which is the set of subsets of $V$ of size $2$) into precisely two blocks. I know, more of less, what a morphism of such objects are. A map $V \to V'$ almost induces a map ${V \choose 2} \to {V'\choose 2}$ — the problem is just the pairs that are identified, which I guess I can forget. Then I can ask that the partition of $V \choose 2$ pushes forward along this map to subsets of the two sets in the partition of $V' \choose 2$. Note that if I order the two blocks of the partition, then this category is equivalent to the category of graphs following one of the definitions above; without ordering the blocks of the partition, I think I'm getting your category.

But is it a useful category? Does it capture some intuition we (mathematicians collectively) have? To the latter question, the answer is clearly yes: you've suggested an isomorphism based on some mathematical intuition. To the former question, Greg K's answer gives some indication. But my feeling is that really, this category does not deserve to be called the category of graphs, because there are so many interesting graph-theoretic questions that mathematicians want to ask that are not isomorphism-invariant in this category.

Answer 4

Perhaps what Hans means is simply that any graph has exactly the same information as the complement graph, because if we know completely where there are no edges, then we also know completely where are the edges, and conversely.

But having the same information in this logical sense is not the same as being isomorphic in the sense of graphs, and obviously there are numerous graphs that are not graph isomorphic to their complements, the simplest example being the graph with no edges, whose complement is the complete graph.

Answer 5

The set { $[n], R, \neg R$ } does not actually specify a graph, since we cannot distinguish between edges and non-edges. The triple ($[n], R, \neg R$ ) does specify a graph since by convention we can say that the second coordinate specifies the edges and the third specifies the non-edges. Thus, ($[n], R, \neg R$ ) is not isomorphic to ($[n], \neg R, R$ ).