meditationatae

Just another WordPress.com site

“Best candidate” graph, 14 vertices, udg

I modified my searcher of unit distance graphs for 13 vertices, so that it works on searching and solving 14-vertex unit distance graphs. I look for 14-vertex unit distance graphs that:

(a) are not 3-colorable and

(b) have the least possible 4-colorings, up to permutation of the 4 colors, which can be done be 4! = 24 ways.

My best candidate in that sense is decribed from file below:

$ cat nano
adjacency matrix:
0 0 1 0 0 0 1 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 0 0
1 0 0 1 1 0 0 1 0 0 0 0 1 0
0 0 1 0 0 0 0 0 0 0 0 1 1 0
0 0 1 0 0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 1 0 0 1 0 1 0
1 0 0 0 0 1 0 0 0 0 0 1 1 0
0 0 1 0 1 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 1
0 1 0 0 0 0 0 0 1 0 1 0 0 1
0 1 0 0 1 1 0 0 0 1 0 0 0 0
0 1 0 1 0 0 1 0 0 0 0 0 0 1
0 0 1 1 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 1 0 0

post adjacency matrix:
0 1 1 0 0 0 1 1 1 0 0 1 0 0
1 0 0 0 0 0 0 0 0 1 1 1 0 0
1 0 0 1 1 0 0 1 0 0 0 0 1 0
0 0 1 0 0 0 0 0 0 0 0 1 1 0
0 0 1 0 0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 1 0 0 1 0 1 0
1 0 0 0 0 1 0 0 0 0 0 1 1 0
1 0 1 0 1 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 1
0 1 0 0 0 0 0 0 1 0 1 0 0 1
0 1 0 0 1 1 0 0 0 1 0 0 1 0
1 1 0 1 0 0 1 0 0 0 0 0 0 1
0 0 1 1 0 1 1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 1 0 1 0 0
total_finds = 629
Tests count = 4 has_converged_step = 1788 max_has_converged_step = 1788
rec_diff1 = 39.680992
rec_diff25 = 39.884218
rec_diff50 = 17.695808
rec_diff100 = 15.382953
rec_diff200 = 9.138731
rec_diff400 = 0.066954
rec_diff800 = 0.0000007847509167
rec_diff1200 = 0.0000000000828210
probable_unit_lengths = 29
graph is 3-colorable:no.
count_4_colorings = 1114 num_4_colorings_mod_24 = 0
Matrix of distances vertex to vertex:
A B C D E F G H I J K L M N
A 0.000 1.000 1.000 0.457 1.732 0.457 1.000 1.000 1.000 0.292 0.737 1.000 0.577 1.242
B 1.000 0.000 1.457 0.577 1.568 0.737 1.732 0.577 1.979 1.000 1.000 1.000 1.568 1.859
C 1.000 1.457 0.000 1.000 1.000 1.370 1.915 1.000 1.568 1.291 0.457 1.947 1.000 2.189
D 0.457 0.577 1.000 0.000 1.457 0.457 1.370 0.577 1.457 0.577 0.577 1.000 1.000 1.568
E 1.732 1.568 1.000 1.457 0.000 1.915 2.731 1.000 2.524 1.979 1.000 2.432 1.947 2.971
F 0.457 0.737 1.370 0.457 1.915 0.000 1.000 1.000 1.291 0.292 1.000 0.577 1.000 1.155
G 1.000 1.732 1.915 1.370 2.731 1.000 0.000 1.947 0.737 0.792 1.732 1.000 1.000 0.292
H 1.000 0.577 1.000 0.577 1.000 1.000 1.947 0.000 1.979 1.155 0.577 1.457 1.457 2.140
I 1.000 1.979 1.568 1.457 2.524 1.291 0.737 1.979 0.000 1.000 1.568 1.568 0.577 1.000
J 0.292 1.000 1.291 0.577 1.979 0.292 0.792 1.155 1.000 0.000 1.000 0.737 0.737 1.000
K 0.737 1.000 0.457 0.577 1.000 1.000 1.732 0.577 1.568 1.000 0.000 1.568 1.000 1.979
L 1.000 1.000 1.947 1.000 2.432 0.577 1.000 1.457 1.568 0.737 1.568 0.000 1.457 1.000
M 0.577 1.568 1.000 1.000 1.947 1.000 1.000 1.457 0.577 0.737 1.000 1.457 0.000 1.291
N 1.242 1.859 2.189 1.568 2.971 1.155 0.292 2.140 1.000 1.000 1.979 1.000 1.291 0.000

=====

Added :   Mon Feb 20 19:13:27 EST 2017

Re: post adjacency matrix for graph in file nano

The “post adjacency matrix” is obtained by filling in the

adjacency matrix with 1s for “new unit length edges” that are “probably of length 1” , such as the represented by the vertices A and L above, which are  1.000 after convergence of the system with springs of length 1 joining edges we want to be 1 apart.

In the adjacency matrix at the top, A is required to be at unit distance from vertices C, G, and I. As it turns out, A is also at practically unit distance from vertices B, H, and L also, in one solution to the unit distance graph equations.

Proving this rigorously would be difficult, so I’m content to call it “probably true”, provisionally.

Another program I wrote finds 9 triangles, also known as complete graphs on 3 vertices, or type K3:

Complete graph at Wikipedia:

https://en.wikipedia.org/wiki/Complete_graph

The output:

adjacency matrix:

A B C D E F G H I J K L M N
A 0 1 1 0 0 0 1 1 1 0 0 1 0 0
B 1 0 0 0 0 0 0 0 0 1 1 1 0 0
C 1 0 0 1 1 0 0 1 0 0 0 0 1 0
D 0 0 1 0 0 0 0 0 0 0 0 1 1 0
E 0 0 1 0 0 0 0 1 0 0 1 0 0 0
F 0 0 0 0 0 0 1 1 0 0 1 0 1 0
G 1 0 0 0 0 1 0 0 0 0 0 1 1 0
H 1 0 1 0 1 1 0 0 0 0 0 0 0 0
I 1 0 0 0 0 0 0 0 0 1 0 0 0 1
J 0 1 0 0 0 0 0 0 1 0 1 0 0 1
K 0 1 0 0 1 1 0 0 0 1 0 0 1 0
L 1 1 0 1 0 0 1 0 0 0 0 0 0 1
M 0 0 1 1 0 1 1 0 0 0 1 0 0 0
N 0 0 0 0 0 0 0 0 1 1 0 1 0 0

( 29 edges )

Triangles found:

triangle ACH
triangle CEH
triangle BJK
triangle ABL
triangle AGL
triangle CDM
triangle FGM
triangle FKM
triangle IJN

9 triangles in all

=====

Added:

Mon Feb 20 16:19:25 EST 2017

The “Best candidate” has been improved: the latest is not 3-colorable, and has 811 4-colorings, up to permutations of the 4 colors:

adjacency matrix:
0 0 0 0 0 1 0 0 1 0 0 1 0 0
0 0 0 1 0 1 0 0 1 1 0 0 0 1
0 0 0 0 1 0 1 0 0 0 1 1 0 0
0 1 0 0 0 0 0 0 0 1 0 1 0 0
0 0 1 0 0 1 0 0 0 0 1 0 0 0
1 1 0 0 1 0 0 0 1 0 1 0 0 0
0 0 1 0 0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 1 0 0 1 1
1 1 0 0 0 1 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 1 0 0 0 0 1 1
0 0 1 0 1 1 1 0 0 0 0 0 0 0
1 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 1 0 0 0 0
0 1 0 0 0 0 0 1 0 1 0 0 0 0

post adjacency matrix:
0 0 0 0 0 1 0 0 1 0 0 1 0 0
0 0 0 1 0 1 0 0 1 1 0 0 0 1
0 0 0 0 1 0 1 0 0 0 1 1 0 0
0 1 0 0 1 0 0 0 0 1 0 1 0 0
0 0 1 1 0 1 0 0 0 0 1 0 0 0
1 1 0 0 1 0 0 0 1 0 1 0 0 0
0 0 1 0 0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 1 0 0 1 1
1 1 0 0 0 1 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 1 0 0 1 1 1 1
0 0 1 0 1 1 1 0 0 1 0 0 0 0
1 0 1 1 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 1 0 1 0 1 0 0
0 1 0 0 0 0 0 1 0 1 0 0 0 0
total_finds = 854
Tests count = 15 has_converged_step = 1399 max_has_converged_step = 1568
rec_diff1 = 39.680992
rec_diff25 = 39.884218
rec_diff50 = 17.695808
rec_diff100 = 17.881124
rec_diff200 = 9.138731
rec_diff400 = 0.066954
rec_diff800 = 0.0000007847509167
rec_diff1200 = 0.0000000000828210
probable_unit_lengths = 29
graph is 3-colorable:no.
count_4_colorings = 811 num_4_colorings_mod_24 = 0
Matrix of distances vertex to vertex:
A B C D E F G H I J K L M N
A 0.000 1.732 0.737 0.737 0.457 1.000 1.291 2.524 1.000 1.568 0.577 1.000 1.979 2.432
B 1.732 0.000 2.354 1.000 1.915 1.000 2.180 1.732 1.000 1.000 1.370 1.732 2.000 1.000
C 0.737 2.354 0.000 1.370 1.000 1.732 1.000 2.731 1.444 1.915 1.000 1.000 1.947 2.887
D 0.737 1.000 1.370 0.000 1.000 0.577 1.444 2.000 0.457 1.000 0.457 1.000 1.732 1.732
E 0.457 1.915 1.000 1.000 0.000 1.000 1.732 2.929 1.370 1.947 1.000 1.457 2.432 2.731
F 1.000 1.000 1.732 0.577 1.000 0.000 2.000 2.432 1.000 1.457 1.000 1.568 2.291 1.947
G 1.291 2.180 1.000 1.444 1.732 2.000 0.000 1.915 1.191 1.370 1.000 0.457 1.000 2.354
H 2.524 1.732 2.731 2.000 2.929 2.432 1.915 0.000 1.568 1.000 1.947 1.732 1.000 1.000
I 1.000 1.000 1.444 0.457 1.370 1.000 1.191 1.568 0.000 0.577 0.457 0.737 1.291 1.457
J 1.568 1.000 1.915 1.000 1.947 1.457 1.370 1.000 0.577 0.000 1.000 1.000 1.000 1.000
K 0.577 1.370 1.000 0.457 1.000 1.000 1.000 1.947 0.457 1.000 0.000 0.577 1.457 1.915
L 1.000 1.732 1.000 1.000 1.457 1.568 0.457 1.732 0.737 1.000 0.577 0.000 1.000 2.000
M 1.979 2.000 1.947 1.732 2.432 2.291 1.000 1.000 1.291 1.000 1.457 1.000 0.000 1.732
N 2.432 1.000 2.887 1.732 2.731 1.947 2.354 1.000 1.457 1.000 1.915 2.000 1.732 0.000

=====

Added:  Mon Feb 20 20:14:02 EST 2017

Re: K3’s , or triangles, found in “post adjacency matrix” with graph having 811 4-colorings

I ran my triangle counter program on the 14-vertex, 29-edge graph whose adjacency matrix is the one labelled “post-(convergence) adjacency matrix” above.

It finds 11 complete graphs on three vertices, or K3’s:

adjacency matrix:

XXA B C D E F G H I J K L M N
A 0 0 0 0 0 1 0 0 1 0 0 1 0 0
B 0 0 0 1 0 1 0 0 1 1 0 0 0 1
C 0 0 0 0 1 0 1 0 0 0 1 1 0 0
D 0 1 0 0 1 0 0 0 0 1 0 1 0 0
E 0 0 1 1 0 1 0 0 0 0 1 0 0 0
F 1 1 0 0 1 0 0 0 1 0 1 0 0 0
G 0 0 1 0 0 0 0 0 0 0 1 0 1 0
H 0 0 0 0 0 0 0 0 0 1 0 0 1 1
I 1 1 0 0 0 1 0 0 0 0 0 0 0 0
J 0 1 0 1 0 0 0 1 0 0 1 1 1 1
K 0 0 1 0 1 1 1 0 0 1 0 0 0 0
L 1 0 1 1 0 0 0 0 0 1 0 0 1 0
M 0 0 0 0 0 0 1 1 0 1 0 1 0 0
N 0 1 0 0 0 0 0 1 0 1 0 0 0 0

(29 edges)

Triangles found:

triangle AFI
triangle BFI
triangle BDJ
triangle CEK
triangle EFK
triangle CGK
triangle DJL
triangle HJM
triangle JLM
triangle BJN
triangle HJN

11 triangles in all

=====

Added: Tue Feb 21 23:20:03 EST 2017
Re: possible unit distance graphs with 14 vertices

Below, the adjacency matrix for a graph with vertices labeled A to N,
and a matrix of distances vertex to vertex to 3 decimals with 33 edges
listed as of length 1.000 ; the program checks that the l_1 norm
of the vector (1, 1, 1, … 1) – (d_1, d_2, … d_33) is
less than about 1E-15, where d_1, d_2, … d_33 are the 33 edge lengths.

About graph and its embedding in R^2:

– 14-vertex, 33-edge graph.
– Not 3-colorable.
– Has 324 4-colorings, up to permutation of colors.
– Possibly a unit distance graph, according to numerical evidence.
– “count_4_colorings” below is the total number of 4-colorings, divided by 24; so this counts permuted colors as giving equivalent colorings.
adjacency matrix after “convergence” of the discrete dynamical system:

xxAxBxCxDxExFxGxHxIxJxKxLxMxN
A 0 0 0 0 0 1 1 1 0 0 0 0 1 0
B 0 0 1 0 1 1 0 0 0 0 0 0 0 1
C 0 1 0 0 0 0 0 1 0 0 1 0 0 0
D 0 0 0 0 0 1 0 1 0 1 1 1 0 0
E 0 1 0 0 0 0 1 1 0 1 0 0 0 1
F 1 1 0 1 0 0 0 0 0 0 0 1 1 0
G 1 0 0 0 1 0 0 1 1 0 0 1 0 0
H 1 0 1 1 1 0 1 0 0 0 1 0 0 0
I 0 0 0 0 0 0 1 0 0 0 1 1 1 1
J 0 0 0 1 1 0 0 0 0 0 0 1 0 1
K 0 0 1 1 0 0 0 1 1 0 0 0 1 1
L 0 0 0 1 0 1 1 0 1 1 0 0 0 0
M 1 0 0 0 0 1 0 0 1 0 1 0 0 0
N 0 1 0 0 1 0 0 0 1 1 1 0 0 0

total_finds = 263
Tests count = 20 has_converged_step = 1155 max_has_converged_step = 1334
rec_diff1 = 38.851687
rec_diff25 = 38.971383
rec_diff50 = 16.526850
rec_diff100 = 15.400758
rec_diff200 = 4.882370
rec_diff400 = 0.051505
rec_diff800 = 0.0000007203509511
rec_diff1200 = 0.0000000000803201

probable_unit_lengths = 33
graph is 3-colorable:no.
count_4_colorings = 324 num_4_colorings_mod_24 = 0

Matrix of distances vertex to vertex:

xxxxxAxxxxxBxxxxxCxxxxxDxxxxxExxxxxFxxxxxGxxxxxHxxxxxIxxxxxJxxxxxKxxxxxLxxxxxMxxxxxNx
A 0.000 0.737 0.457 1.915 1.732 1.000 1.000 1.000 0.457 2.354 1.370 1.370 1.000 1.444
B 0.737 0.000 1.000 1.568 1.000 1.000 0.457 0.577 0.577 1.732 1.457 0.737 1.568 1.000
C 0.457 1.000 0.000 1.732 1.915 0.737 1.370 1.000 0.457 2.354 1.000 1.444 0.577 1.370
D 1.915 1.568 1.732 0.000 1.457 1.000 1.947 1.000 1.457 1.000 1.000 1.000 1.947 0.577
E 1.732 1.000 1.915 1.457 0.000 1.568 1.000 1.000 1.457 1.000 1.947 0.577 2.432 1.000
F 1.000 1.000 0.737 1.000 1.568 0.000 1.457 0.577 0.577 1.732 0.457 1.000 1.000 0.737
G 1.000 0.457 1.370 1.947 1.000 1.457 0.000 1.000 1.000 1.915 1.915 1.000 1.947 1.370
H 1.000 0.577 1.000 1.000 1.000 0.577 1.000 0.000 0.577 1.370 1.000 0.457 1.457 0.457
I 0.457 0.577 0.457 1.457 1.457 0.577 1.000 0.577 0.000 1.947 1.000 1.000 1.000 1.000
J 2.354 1.732 2.354 1.000 1.000 1.732 1.915 1.370 1.947 0.000 1.915 1.000 2.731 1.000
K 1.370 1.457 1.000 1.000 1.947 0.457 1.915 1.000 1.000 1.915 0.000 1.370 1.000 1.000
L 1.370 0.737 1.444 1.000 0.577 1.000 1.000 0.457 1.000 1.000 1.370 0.000 1.915 0.457
M 1.000 1.568 0.577 1.947 2.432 1.000 1.947 1.457 1.000 2.731 1.000 1.915 0.000 1.732
N 1.444 1.000 1.370 0.577 1.000 0.737 1.370 0.457 1.000 1.000 1.000 0.457 1.732 0.000

 

Added: Fri Feb 24 02:10:46 EST 2017

A graphic representation of the 14-vertex, 33-edge graph embedded in the Euclidean plane, rendered using PostScript:

graph33ascreenshot

Advertisements

Written by meditationatae

February 20, 2017 at 6:29 pm

Posted in History

%d bloggers like this: