Suppose there exists a Conway-99 graph G, that is, an SRG(99,14,1,2). Let a and b be vertices of G such that a and b are neighbours. Then:
Thus the graph G' on a,b and their neighbours consists of 27 vertices (a, b, their mutual neighbour, 12 neighbours of a but not b, and 12 neighbours of b but not a). In this workbook, we determine (up to isomorphism) the possibilities for this graph induced by the lambda = 1, mu = 2 constraints on G.
For convenience, we fix a numbering:
Moreover, we introduce these vertices sequentially using the 'fanblade' structures centred at vertices 0 and 1:
Finally, we note that each of the vertices i = 15...26 is not adjacent to vertex 0, thus (by mu = 2) there must be two mutual neighbours of 0,i in G. But as all neighbours of 0 are in G', namely vertices 1...14, we know that each vertex i = 15...26 is adjacent to precisely 2 of the vertices 1...14.
Our task then essentially reduces to determining j for each i=16...26, whilst satisfying all our other conditions.
%pylab inline
import numpy as np
from conway99 import *
import pydot
from networkx.drawing.nx_pydot import write_dot
We start from an arbitrary vertex and its neighbours. These can necessarily be arranged as 7 blades of a fan; we fix a numbering with vertex 0 the centre, 1-14 its neighbours, and blade edges 1-2, 3-4, 5-6, 7-8, 9-10, 11-12, 13-14
seed15 = np.empty((15,15), dtype='int')
for i in range(15):
for j in range(15):
seed15[i,j] = 0
# 1-14 all nhbrs of 0
for i in range(1,15):
seed15[0,i] = 1
seed15[i,0] =1
# By fixing an ordering, a single representative suffices
for i in [1,3,5,7,9,11,13]:
seed15[i,i+1] = 1
seed15[i+1,i] = 1
# review
print(seed15)
plot_given_edges(seed15)
# Verify some details
assert len(seed15)*len(seed15) == num_known_zeros(seed15) + num_known_ones(seed15) + num_unknowns(seed15)
assert not(has_unknown_values(seed15))
assert lambda_compatible(seed15)
assert mu_compatible(seed15)
assert meets_adjacency_requirements(seed15, debug=True)
assert graph_is_valid(seed15)
(NB, as we started numbering at 0, this is our 16th vertex)
wlog (see intro, or consider how the plot below would be equivalent for any alternative choice for second neighbour amongst 3...14), we may assume this is a neighbour of vertices 1 and 3.
%time rep16 = find_valid_supergraphs([seed15], forced_edges=[(1,15), (15,3)])
# confirm this is what we expected:
plot_given_edges(rep16[0])
Note that we no longer make any direct assumptions about the second neighbour j in 3...14; we determine representatives of the possibilities dictated by the lambda, mu conditions.
We know one of the blades centred at vertex 1; namely 1-0-2-1.
We also have part of another, containing vertex 15.
wlog, let vertex 16 be the other vertex of that blade (so we force 1-16, and 15-16)
%time rep17 = find_valid_supergraphs(rep16, forced_edges=[(1,16),(15,16)], verbose=False)
Vertex 17 necessarily starts a new blade, so only forcing 1-17
%time rep18 = find_valid_supergraphs(rep17, forced_edges=[(1,17)], verbose=False)
However, we can then force vertex 18 to be the other vertex of that blade
%time rep19 = find_valid_supergraphs(rep18, forced_edges=[(1,18),(17,18)], verbose=False)
Continue in this fashion until we have all nhbrs of vertex 1, with forced fan pattern 0-2, 15-16, 17-18, 19-20, 21-22, 23-24, 25-26
%time rep20 = find_valid_supergraphs(rep19, forced_edges=[(1,19)], verbose=False)
%time rep21 = find_valid_supergraphs(rep20, forced_edges=[(1,20), (19,20)], verbose=False)
%time rep22 = find_valid_supergraphs(rep21, forced_edges=[(1,21)], verbose=False)
%time rep23 = find_valid_supergraphs(rep22, forced_edges=[(1,22), (21,22)], verbose=False)
%time rep24 = find_valid_supergraphs(rep23, forced_edges=[(1,23)], verbose=False)
%time rep25 = find_valid_supergraphs(rep24, forced_edges=[(1,24), (23,24)], verbose=False)
%time rep26 = find_valid_supergraphs(rep25, forced_edges=[(1,25)], verbose=False)
%time rep27 = find_valid_supergraphs(rep26, forced_edges=[(1,26),(25,26)], verbose=False)
Up to equivalence, we have 11 possibilities. We first review an arbitrary example, then consider how the others differ.
plot_given_edges(rep27[0])
def describe_differences(rep1, rep2):
order = min(len(rep1),len(rep2))
for i in range(order):
for j in range(i, order):
if rep1[i,j] > rep2[i,j]:
print('First graph has edge {}-{} absent from second'.format(i,j))
if rep1[i,j] < rep2[i,j]:
print('First graph lacks edge {}-{} present in second'.format(i,j))
for i in range(1, 11):
print('Comparing rep 0 to rep {}'.format(i))
describe_differences(rep27[0],rep27[i])
print('\n------\n')
Which edges are consistent across all reps?
for i in range(27):
for j in range(i,27):
if min([r[i,j] for r in rep27]) == 1:
print('Edge {}-{} appears in all representatives'.format(i,j))
This is just our assumed numbering of:
So these assumptions do not inevitably force any other edges; various branches arise as each succesive vertex 16..26 is considered.
# Export base example for plotting
G = graph_from_mat(rep27[0])
write_dot(G, "rep27_0.dot")
Note that rep 0 has a particularly pleasing pattern - for each i = 15...26, the neighbour j from 3...14 satisfies i = j + 12
(i.e. consistent throughout with our choice of vertex 3 as neighbour of vertex 15.)
G.edges