In [1]:

```
%pylab inline
import numpy as np
from conway99 import *
import pickle
```

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

In [2]:

```
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
```

In [3]:

```
# review
print(seed15)
plot_given_edges(seed15)
```

In [4]:

```
# 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, we let this be a neighbour of vertex 1

In [5]:

```
# Generate template with an additional vertex, and review
seed16 = get_supermatrix_template(seed15, forced_edges=[(1,15)])
print(seed16)
plot_given_edges(seed16)
```

In [6]:

```
# Fill in the template
%time super16 = templates_to_valid_graphs([seed16], verbose=0)
```

In [7]:

```
# Reduce to eliminate equivalent graphs
rep16 = reduce_mod_equivalence(super16, verbose=True)
```

In [8]:

```
# Turns out, there's only really one way to extend this! Let's take a look
plot_given_edges(rep16[0])
```

This was expected:

By mu=2 condition, as 15 is not a nhbr of 0, they have 2 mutual nhbrs

- As the nhbrs of 0 are 1-14, 15 nhbrs two of these.
- We assumed 1-15 already; this prevents 2-15 (else 1,2 are nhbrs with two mutual nhbrs - 0, 15 - violating lambda=1)
- So 15 nhbrs precisely 1 of vertices 3-14, and these 12 choices are equivalent
- So to fix notation we can force this nhbr to be vertex 14

Moreover, we could have applied this at the template stage to reduce the search space.

In [9]:

```
# alternative template
seed16 = get_supermatrix_template(seed15, forced_edges=[(1,15), (15,14)])
print(seed16)
plot_given_edges(seed16)
```

In [10]:

```
# Fill in the template
%time super16 = templates_to_valid_graphs([seed16], verbose=0)
```

In [11]:

```
len(super16)
```

Out[11]:

In [12]:

```
# For convenience, can wrap up the templating, search, and reduction steps for a list of seed graphs
%time rep16 = find_valid_supergraphs([seed15], forced_edges=[(1,15), (15,14)])
```

In [13]:

```
# confirm this is what we expected from the individual steps:
plot_given_edges(rep16[0])
```

We proceed with a similar approach to the other search, but now handled as part of the logic instead of prescribing (non-)edges.

Specifically, this version identifies the unsaturated vertex *v* of highest degree, picking the lowest index one if there are multiples. We then iterate over the vertices u=0,1,2,...; checking whether the correct number of mutual neighbours are present (1 if u neighbours v, 2 if it does not). We pick the minimal u such that there is a missing mutual neighbour with v, and set our newly added vertex to be that mutual neighbour.

In [14]:

```
%time rep17 = find_valid_supergraphs_greedy(rep16, verbose=False)
```

In [15]:

```
%time rep18 = find_valid_supergraphs_greedy(rep17, verbose=False)
```

In [16]:

```
%time rep19 = find_valid_supergraphs_greedy(rep18, verbose=False)
```

In [17]:

```
%time rep20 = find_valid_supergraphs_greedy(rep19, verbose=False)
```

In [18]:

```
%time rep21 = find_valid_supergraphs_greedy(rep20, verbose=False)
```

In [19]:

```
%time rep22 = find_valid_supergraphs_greedy(rep21, verbose=False)
```

In [20]:

```
%time rep23 = find_valid_supergraphs_greedy(rep22, verbose=False)
```

In [21]:

```
%time rep24 = find_valid_supergraphs_greedy(rep23, verbose=False)
```

In [22]:

```
%time rep25 = find_valid_supergraphs_greedy(rep24, verbose=False)
```

In [23]:

```
%time rep26 = find_valid_supergraphs_greedy(rep25, verbose=False)
```

In [24]:

```
%time rep27 = find_valid_supergraphs_greedy(rep26, verbose=False)
```

In [25]:

```
# Review an example
plot_given_edges(rep27[0])
```

In [26]:

```
# Confirm this has saturated vertex 1 in all examples
deg_of_1 = [sum(r[1]) for r in rep27]
assert min(deg_of_1) == 14
assert max(deg_of_1) == 14
```

The logic will now seek to introduce neighbours for vertex 3 rather than vertex 2, since it is of higher degree.

In [27]:

```
%time rep28 = find_valid_supergraphs_greedy(rep27, verbose=False)
```

In [28]:

```
%time rep29 = find_valid_supergraphs_greedy(rep28, verbose=False)
```

In [29]:

```
%time rep30 = find_valid_supergraphs_greedy(rep29, verbose=False)
```

Expect we would hit the memory issue if we proceeded with this many seeds!

In [ ]:

```
pickle.dump( rep30, open( "fullsearch_sat-30.p", "wb" ) )
```

In [ ]:

```
```