Conference rusure::math

Would someone be willing to remind us of what "graphs" and "complementary"
and "dual" are in this context, so we can understand the question a bit
better ?

Thanks.

/Eric

    I believe for the purposes of this problem, a graph is an ordered pair
    (V,E) where V is a set of vertices and E is a set of ordered pairs in
    VxV.  (E is a set of edges from vertex to vertex.)  Typically E does
    not include any pairs of the form (v,v), which are called loops.  The
    complement of a graph is the graph with the same vertices but all the
    edges, and only those edges, that aren't in the original, but also
    excluding edges that are loops.
    
    The dual is a graph with a vertex for each edge in the original graph,
    and two vertices in the dual are joined by an edge iff the
    corresponding two edges in the original meet at a vertex.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.

    >I believe for the purposes of this problem, a graph is an ordered pair
    >(V,E) where V is a set of vertices and E is a set of ordered pairs in
                                                          -------
    >VxV.  (E is a set of edges from vertex to vertex.)  Typically E does
    >not include any pairs of the form (v,v), which are called loops.  The
    >complement of a graph is the graph with the same vertices but all the
    >edges, and only those edges, that aren't in the original, but also
    >excluding edges that are loops.
    
    I think this is called a "directed graph" or digraph. I think a "graph"
    has edges which are unordered pairs. If a graph is like a street map
    from the 1800s where traffic can pass in either direction, a digraph is
    like a modern city plan consisting entirely of freeways and one way
    streets.
    
    Anyway, the answer is "yes". For a graph on n vertices, there are
    n(n-1)/2 possible edges. The edges of the graph and its complement
    form a partition of these possible edges. A self-complementary graph
    obviously has the same number of edges as its complement, so we can
    deduce that a self-complementary graph on n points has n(n-1)/4 edges.
    
    If the graph is also self-dual then its number of vertices equals its
    number of edges, ie n = n(n-1)/4. This implies it has 5 points and 5
    edges.
    
    Looking at graphs on 5 points, the 5-cycle (draw it as a regular
    pentagon taking vertices and edges in the obvious way) fits the bill.
    It is obviously self-dual, and its complement is the inscribed
    pentagram, which can be "unfolded" into a regular pentagon.
    
    A quick exhaustive search shows no other graph on 5 points has these
    properties.
               
    For digraphs, there are n(n-1) possible edges and there's a sort of
    solution with n=3 as a triangle with all edges directed in the same
    sense. The complement is the same with the edges in the opposite sense,
    but the dual is not well defined.
    
    That exhausts the finite case, any speculations on infinite, self-dual,
    self-complementary graphs?

    Re .3:
    
    Oops, you're right, the edges should be unordered sets with two
    elements.  There is one other finite solution:  trivially, the empty
    graph.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.

Thanks for the clarification !  Kind of like spaghetti code...

/Eric

    I think what I wrote in .3 is rubbish.
    
    I believe the graph defined as the "dual" in .2 is actually the "edge
    graph", which has some other name or symbol that I can't remember. I'll
    drag Harrary out of the loft and check.
    
    A "dual" of any sort normally has the property of being self-inverse,
    ie the dual of the dual of a thing is isomorphic to the original thing.
    The edge grpah does not have this property, so is unlikely to be called
    a dual.
    
    The one sort of dual I do know about for graphs is the dual of a finite
    planar graph. Informally, you get this by embedding the graph in a
    sphere and taking each enclosed region to be a vertex of the dual. Two
    vertices are connected iff the corresponding regions share a common
    edge. Thus if the original graph has v vertices, e edges and f faces,
    the dual has f vertices, e edges and v faces. There's also some
    complicated combinatorial criterion due to Whitney which ammounts to
    the same thing. Duality in this sense is not a 1-1 relation, since
    different embeddings of a graph may give rise to different duals. It
    is, however, symmetric.
    
    For a self-dual graph we must have f = v. Since it is planar, it
    also obeys Euler's formula f + v = e + 2. Thus e = 2(v-1). If it is
    self-complementary we have e = v(v-1)/4, as in .3. Hence any self-dual,
    self-complementary graph must be a planar graph on 8 points with 14
    edges.
    
    Let the number of edges meeting at the i'th vertx be ni, i=1..8. Then
    by the dfinition of complement each vertex can be paired with another
    vertex where (7-ni) edges meet. This probably narrows down the problem
    to a point where you can finish it off by exhaustive search.
    
    Andy.

    Re .6:
    
    > I believe the graph defined as the "dual" in .2 is actually the "edge
    > graph", which has some other name or symbol that I can't remember.
    
    Could be.  Before entering the problem, I looked up "dual" in two graph
    theory books, and it wasn't in either.  So the definition I gave was my
    best guess at the time.  But the solution in .3 does seem too easy.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.

	re .6
        
>    I think what I wrote in .3 is rubbish.
    
	This reminds me...a long time ago in this conference someone
        wrote reply N, then later the same author wrote reply M
        blasting the author of reply N (without indicating, as you
        did, that both notes had the same author).  Someone else
        replied that if that's how we treat each other here then we
        just lost a noter!
        
        Dan

Sometimes while I play tennis, I hear someone on the adjacent court
chastizing themself after missing a shot:

	You idiot, HIT the ball!


I think of asking them if they would treat someone else that way, and
if not, why treat themself that way.

Kind of a reverse golden rule (no, *not* the one saying "do unto others before
they do unto you"), something like:

	do unto yourself as you would others


If he were coaching someone *else* in tennis, he would certainly have some
nicer way of criticising the shot.

(personally, I'm not quite as bad to myself.  When I miss a shot, I
yell single words like "crapiola" or "shiteroni", refering to the missed
shot and not to myself, although I admit my own self criticism could
use some work...)

oh yeah, this is the *math* conference, sorry...

/Eric

No, It can't be done.

By previous work, such a graph must have 8 vertices and 14 edges.

In order for the dual to be well defined, each vertex must have degree at least
3. (If degree = 0, the graph is not connected. If degree = 1 the dual has an
edge joining a vertex to itself, which is not allowed. If degree = 2, the dual
has more than one edge joining a pair of vertices, which is not allowed.)

By self-complementarity, each vertex of degree 3 is paired with a vertex of
degree 4, so the graph has exactly 4 vertices of degree 3 and 4 of degree 4.

Consider the possible connections for a vertex of degree 3: It cann connect to
vertices of degree 3,3,3 ; 3,3,4 ; 3,4,4 or 4,4,4. If it connects to 3,3,3 then
in the complement it _does not_ connect to the images of 3,3,3 ie it does not
connect to vertices of degree 4,4,4. In the complement it has degree 4, so it
must connect to all of the remaining 4 vertices, ie 3,3,3,3. But this implies
that all 4 vertices of degree 3 are connected to at least this one vertex of
degree 4, including the original one. This is a contradiction.

Using the symbol "c:" for "is connected to" and "!c:" for "is not connected
to,", we have for the remaining cases:

3 c: 3,3,4 <=> 4 !c: 4,4,3 <=> 4 c: 4,3,3,3	(A)
3 c: 3,4,4 <=> 4 |c: 4,3,3 <=> 4 c: 4,4,3,3	(B)
3 c: 4,4,4 <=> 4 !c: 3,3,3 <=> 4 c: 4,4,4,3	(C)

Ie, the graph consists of pairs of vertices of degree 3 and 4, each connected
as in (A), (B) or (C).

Let A, B, C be the numbers of each type of pair. There are 4 pairs in total, so

	A + B + C = 4.				(I)

Consider the total number of connections to vertices of degree 3. There are 4
of these, and each has 3 connections for a total of 12. Similarly there are a
total of 16 connections to vertices of degree 4.

Each pair of type (A) contributes 2 connections to vertices of degree 4 and 5
connections to vertices of degree 3. Type (B) pairs contribute 3 and 3
respectively, and type (C) pairs 6 and 1. This give two equations:

	2A + 3B + 6C = 16			(II)

	5A + 3B + C  = 12			(III)

Equations I, II and II can be solved to give A = 2, B = 0 and C = 2. Thus the
connections of the graph must be:

3 c: 4,4,4
3 c: 4,4,4
3 c: 3,3,4
3 c: 3,3,4
4 c: 4,4,4,3
4 c: 4,4,4,3
4 c: 4,3,3,3
4 c: 4,3,3,3

But this is not possible because the two 4,4,4,3 each connect to all the other
degree 4 vertices, implying every degree 4 vertex has connections to at least 2
other degree 4 vertices, which is not the case.

Therefore no such graph exists.

Andy.

> No, it can't be done.

	Suppose you start with a cubic cage (8 vertices, 12 edges, 6 faces).
Now pick 2 opposite faces and stick a diagonal across each, so that the 2 
diagonals are parallel to one another.
	
	I'm pretty sure this gives us a self-dual self-complementary plane 
graph. Draw it, label the vertices, and see.

	So where does our thinking diverge?
    	
> By previous work, such a graph must have 8 vertices and 14 edges.
> The graph has exactly 4 vertices of degree 3 and 4 of degree 4.

	Good stuff so far.
        
>	2A + 3B + 6C = 16			(II)
	     ^
	This should be 4. Unfortunately, this means that your 3 equations are
no longer linearly independent.


Regards,
Guess who.

	There are exactly 3 plane, self-dual, self-complementary graphs.


(1)	How to construct them.

	(i) Take a cubic cage. Add 2 edges to it, as parallel diagonals of
2 opposite faces.

	(ii) Take a tetrahedral cage, with vertices A, B, C & D. Add vertices 
E, F, G & H at the centre of each face: ABC, ABD, ACD & BCD respectively. 
Remove edges AB & CD. Add edges: AE, BE, AF, BF, EF;  CG, DG, CH, DH, GH.

	(iii) Take a tetrahedral cage, with vertices A, B, C & D. Add vertices
E & F at the midpoints of AB & CD respectively (so edge AB is replaced by
edges AE & EB;  and the same deal applies to CD). Add vertices G & H at the
midpoints of faces ABC & BCD respectively. Add edges. AG, CG, EG;  BH, DH, FH.


(2) 	How to prove that these are your only men.

	It's shown in a previous reply that if such a graph, G, exists, it must
have 8 vertices, of which 4 have degree 3, and 4 have degree. Partition, V,
the vertex set into V3 & V4, the sets of vertices of degree 3 & 4 respectively.
Let Eij (i =< j) be the set of edges which link vertices from Vi with vertices
from Vj.

	By self-complementarity, |E34| = 8. By considering the degrees of the 
V3 members |E33| = 2. Similarly |E44| = 4.

	Now do the two edges in E3 touch?

	No. Consider f, a morphism from G to itself which reverses the
existence of edges (ie, which demonstrates that G is self-complementary). A 
simple lemma shows that the order of each orbit of G under f is a multiple of 4
(*EXCEPT* for one orbit of order 1 iff |G| == 1 mod 4.)

	So, if the two edges in E3 touch, then G is not symmetric enough.
Consider the unique element of V3 which is not adjacent to any other in V3. Its
orbit under any f could only be 2.

	Similarly, the 4 edges in E4 form a cycle. Now, it's a matter of a
few minutes to check the possible graphs satisfying the above constraints.
There are two criteria we can use to prune the search.

	(i) some graphs admit a K3,3. Since this is non-planar, we can
discount these graphs immediately.

	(ii) when we draw the plane graphs which can correspond to the
abstract graphs, we look at the triangles. These must come in two adjacent
pairs. If they don't, discount the graph immediately.

	There are 3 survivors, and it's easy to check they are indeed
solutions. 

Regards,
Andrew.