Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: a 7-vertex graph with an unusual 3D figure (very probable)
Replies: 11   Last Post: Dec 6, 2013 12:42 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
David Bernier

Posts: 3,369
Registered: 12/13/04
a 7-vertex graph with an unusual 3D figure (very probable)
Posted: Nov 30, 2013 1:23 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

I wrote a program that produces at random "adjacency matrices" for graphs.

http://en.wikipedia.org/wiki/Adjacency_matrix

I'm looking at undirected graphs with no loops and no double edges.

Some such graphs can be "embedded" in the Euclidean plane
in such a way that adjacent vertices are always exactly
a unit-distance apart, the unit distance graphs:

http://en.wikipedia.org/wiki/Unit_distance_graph

The adjacency matrix my program came up with (that passed two
admissibility tests that I'll explain below) is this:

M =
[0 1 1 1 1 0 0]
[1 0 0 1 0 0 1]
[1 0 0 0 1 0 1]
[1 1 0 0 0 1 0]
[1 0 1 0 0 1 0]
[0 0 0 1 1 0 1]
[0 1 1 0 0 1 0]

Following the usual order of rows, I label the vertices
A, B, C, D, E, F and G.

The vertex A has 4 adjacent vertices (B, C, D and E).
Other vertices have degree 3 (3 adjacent vertices).

The graph has 7 vertices and 11 edges.

There are the 3-cycles ("triangles"), ACE and ABD.

There are the 4-cycles ("quadrangles")
ABGC,
ADFE,
BDFG and
CEFG.

The two admissibility tests for candidate unit distance graphs in 2D are:

(a) Has no subgraph isomorphic to the complete graph on 4 vertices.

This is because in a unit distance graph in the Euclidean plane,
we can have 3 points at unit distance from each other, but not 4.


(b) If X and Y are distinct vertices of the graph, there can be
two distinct vertices v1 and v2, each adjacent to X and Y,
but there cannot be three distinct vertices v1, v2 and v3
each adjacent to X and Y.

Because in the plane, if C1 and C2 are radius 1 circles about
two distinct points X and Y, then C1 and C2 intersect in two
or fewer points.

I won't check that the 7-graph with the adjacency matrix
M has properties (a) and (b), as the program did it, and
it's routine.

The graph associated to M is connected also.

Numerically, I found 7 points in R^3 with unit distances
to within precision (say 10^(-12) ), for the 11 edges
required by the matrix M.

I don't think the graph for M can be for a planar Euclidean
figure.

Also, I doubt that the presumed 3-D figure is deformable, I rather
think it should be rigid.

If we view ABGC as some sort of base quadrangle, even though
it may not fit in a plane, then

upon side AB rises the equilateral triangle ABD to a high point
at D; upon side AC rises the equilateral triangle ACE to a
high point at E; connected to the quadrangular base ABGC
of the skeleton figure along side BG is the quadrangle BDFG;
also connected to base ABGC along side CG is the quadrangle
CEFG. The quadrangle ADFE contains the base point A and the
three so-called high-points D, E and F, all in quadrangle
ADFE but not in the base quadrangle ABGC.

The presumed 3-D figure may have a plane of symmetry
passing through the three points A, F and G.

This plane of symmetry would send B to C and C to B,
and send D to E and E to D. It would also keep fixed
the three points A, F and G. There might be no
plane of symmetry if the presumed 3D figure is deformable;
I doubt that it's deformable.

From my sketch of the graph, I think it's clear that there's
a graph isomorphism that fixes A, G and F and that
permutes B with C, and D with E.

It's only after much numerical computer work that I have some
confidence that there are 7 points in R^3 which are at distance
1 when implied by matrix M; if a matrix entry in M is zero,
the corresponding distance might or might not be 1: it doesn't
matter as I view the problem.

So, I'd be curious about ways to show the corresponding graph to M
can't be made a 2D unit distance graph, can be made a 3D equivalent of
a unit distance graph, and so on.

Here are the x, y and z coordinates for points A to G in the
presumed 3-D figure:

x y z
1.384667538045070848 1.382768373981428755 0.044412611314774557 // A
0.399833591130468233 1.520541863804588859 0.149866689028978084 // B
0.970226156884894247 1.649162807406999439 0.914626577774698943 // C
1.041203194674366289 2.053898061776666813 0.701388400056488421 // D
0.405996262469059331 1.582686954821862589 0.091689406861527141 // E
1.301674189203176470 1.182510983474254957 0.285648793118733590 // F
1.172171851884524849 2.151166533083443602 0.073668674144507970 // G


David Bernier

P.S. If we have a square base ABGC in R^2, and one unit above
it a square A'DFE, and add in the 12 edges, then
remove the edge AA' and glue A and A' while letting the
other edges stretch, we're left with a 7-vertex, 11-edge
graph that looks like the graph of matrix M.

--
http://www.bibliotecapleyades.net/sociopolitica/last_circle/1.htm



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.