-10
$\begingroup$

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?

$\endgroup$
5
  • 6
    $\begingroup$ Downvoting because this seems to be a silly question, as explained in, for example, Mariano's and Tony's answers below. It seems to admit the answer "because that's the wrong notion of isomorphic". $\endgroup$ Mar 2, 2010 at 0:07
  • 1
    $\begingroup$ Scott -- this seems a silly question to you, but do you understand it? (I know I don't, which is why I don't have an opinion on it.) $\endgroup$
    – algori
    Mar 2, 2010 at 0:13
  • $\begingroup$ @Scott: I admit that my question is kind of "polemic", and I know the standard definition of "isomorphic". But nevertheless I cannot find my question "silly": there is a conceptual knot that should be cut. My question was: WHY is this a wrong notion of isomorphic (even when it seems not totally senseless at first sight)? Just because I have to (why?) consider an ordered triple instead of an unordered one? $\endgroup$ Mar 2, 2010 at 0:39
  • 9
    $\begingroup$ Notions do not just jump out of thin air. The notions of graphs and their isomorphisms has a history which motivates it and justifies it. The reason this question seems silly is it is sort of assumes that the value of definitions is independent of their use and their history. Pick a name for the kind of objects you have in mind (sets $X$ with a partition of $X\times X$ in two parts), study them and make much of it. But arguing that your object and its natural notion of isomorphism is the only sensible one is, well, silly. $\endgroup$ Mar 2, 2010 at 1:45
  • $\begingroup$ OK, I agree. In fact I did not want to argue that my object and its notion of isomorphism is the only sensible one, even if my question may sound like this. (In fact, I asked where I run into trouble arguing this way, now I know.) $\endgroup$ Mar 2, 2010 at 8:13

5 Answers 5

14
$\begingroup$

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.

$\endgroup$
0
7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Why "false"? (I dare to object, that this answer isn't sound.) $\endgroup$ Mar 1, 2010 at 23:10
  • 4
    $\begingroup$ Hans, you claim that «any sensible definition of "graph isomorphism" should make any graph isomorphic to its complement» and I exhibited a counter-example, namely, the usual definition of graph isomorphim. $\endgroup$ Mar 1, 2010 at 23:11
  • $\begingroup$ OK, I agree. I misunderstood "your second to last paragraph": I understood "everything from your second until your last paragraph" = "almost everything". $\endgroup$ Mar 1, 2010 at 23:15
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I would have liked to accept two answers (yours and Greg's), but... $\endgroup$ Mar 2, 2010 at 8:31
4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ No, I mean more than that. But obviously I didn't manage to make this clear. $\endgroup$ Mar 1, 2010 at 23:46
  • $\begingroup$ Consider person A describes her graph with the relational symbol R, person B with S (with Sxy iff Rxy) and person C with T (with Txy iff ~Rxy). Why should B's graph be "more" isomorphic to A's than C's? It would seem that isomorphism is a relation between descriptions of graphs (more than a relation between graphs as such. Is this the lesson to be learned?). $\endgroup$ Mar 1, 2010 at 23:51
  • $\begingroup$ I'm sorry then, Hans, if I have misunderstood. $\endgroup$ Mar 1, 2010 at 23:53
  • $\begingroup$ Persons A and B are describing the same graph, whereas person C is describing the complementary graph. So all three descriptions have the same information, and all logically determine the graph/complement graph pair, but C is focused on the complement and A,B are focused on the graph itself. So we only want to say that A and B are isomorphic, and not (necessarily) with C. $\endgroup$ Mar 1, 2010 at 23:57
  • $\begingroup$ So, A and B have the same focus on the graph and C has a complementary (sic!) focus on the very same (=isomorphic) graph. $\endgroup$ Mar 2, 2010 at 0:38
3
$\begingroup$

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$ ).

$\endgroup$
9
  • $\begingroup$ But why should we be interested in what edges and non-edges actually are? We should only be interested in the difference (between edge and non-edge). $\endgroup$ Mar 1, 2010 at 23:18
  • $\begingroup$ Because usually there is a different cost in "building a road between city A and city B" and not building it, and you usually want to know which of the two you are going to pay... $\endgroup$ Mar 1, 2010 at 23:26
  • $\begingroup$ No we're not. Because this difference is of course the same when you pass to the complement $\endgroup$ Mar 1, 2010 at 23:40
  • $\begingroup$ @Mariano: That's not really a mathematical argument, is it? Maybe one in "economical" disguise? $\endgroup$ Mar 1, 2010 at 23:55
  • $\begingroup$ @Andrea: We're not what? If "to be interested in the difference (above)": what you say is exactly what I wanted to claim. $\endgroup$ Mar 1, 2010 at 23:58

Not the answer you're looking for? Browse other questions tagged or ask your own question.