A simple trace formula for graphs

Posted on 2023/09/09 by wdjoyner

Let $\Gamma=(V,E)$ be a simple, connected graph with vertices $V={0,1,\dots, n-1}$ and $n\times n$ adjacency matrix $A$ . We start with the geometric series identity

$\frac{1}{I-tA} = \sum_{\ell=0}^\infty t^\ell A^\ell,$
where $I=I_n$ is the $n\times n$ identity matrix. Let $P$ denote the orthonormal matrix of normalized eigenvectors, so that

$PAP^{-1} = D_\Gamma$ , $D_\Gamma = {diag}(\lambda_1,\dots,\lambda_n),$
where diag(…) denotes the diagonal matrix with the given entries on the diagonal. Let the multi-set

$Spec(\Gamma)={\lambda_0,\lambda_1\dots,\lambda_{n-1}}$
denote the spectrum of $\Gamma$ .

We can conjugate the above equation by $P$ to write

$\frac{1}{I-tD_\Gamma}= P\cdot [\sum_{\ell=0}^\infty t^\ell A^\ell]\cdot P^{-1}.$
Taking the trace of each side gives

$\sum_{j=0}^{n-1} \frac{1}{I-t\lambda_j} = \sum_{\ell=0}^\infty t^\ell tr(A^\ell).$
If $\Gamma$ has no eigenvalues equal to $0$ (i.e., $A$ is non-singular) then we may also write this as

$\sum_{j=0}^{n-1} \frac{\lambda_j^{-1}}{\lambda_j^{-1}-t} = \sum_{\ell=0}^\infty t^\ell tr(A^\ell).$

If we multiply both sides of the above equation by a fixed $f\in C_c^\infty({\mathbb{R}})$
and integrate over $t$ in ${\mathbb{R}}$ , we get,

$\sum_{j=0}^{n-1} \lambda_j^{-1}H(f)(\lambda_j^{-1}) = {\frac{1}{\pi}}\sum_{\ell=0}^\infty tr(A^\ell) [M(f)(\ell+1)+(-1)^\ell M(f^*)(\ell+1)],$
where $H$ denotes the Hilbert transform

$H(f)(z) = \frac{1}{\pi}P.V.\int_{-\infty}^\infty \frac{f(t)}{z-t}\, dt,$ and $M$ is the Mellin transform

$M(f)(z) = \int_{0}^\infty t^{z-1}f(t)\, dt,$
and where $f^*$ denotes the negation, $f^*(t)=f(-t)$ . Of course, if $f$ is even then $M(f)(\ell+1) = M(f^*)(\ell+1)$ , for all $\ell$ .

Note that $tr(A^\ell)$ can be expressed in terms of the number of walks on the graph: If $\Gamma$ is a connected graph and $W_\ell=W_\ell(\Gamma)$ denotes the total number of walks of length $\ell$ on $\Gamma$ then

$W_\ell = {\rm tr}(A^\ell)=\sum_{\lambda\in Spec(\Gamma)} \lambda^\ell.$

Harmonic quotients of regular graphs – examples

Posted on 2023/01/06 by wdjoyner

Caroline Melles and I have written a preprint that collects numerous examples of harmonic quotient morphisms $\phi : \Gamma_2 \to \Gamma_1$ , where $\Gamma_1=\Gamma_2/G$ is a quotient graph obtained from some subgroup $G \subset Aut(\Gamma_2)$ . The examples are for graphs having a small number of vertices (no more than 12). For the most part, we also focused on regular graphs with small degree (no more than 5). They were all computed using SageMath and a module of special purpose Python functions I’ve written (available on request). I’ve not counted, but the number of examples is relatively large, maybe over one hundred.

I’ll post it to the math arxiv at some point but if you are interested now, here’s a copy: click here for pdf.

A graph_id function in SageMath

Posted on 2022/09/07 by wdjoyner

While GAP has a group_id function which locates a “small” group in a small groups database (see the SageMath page or the GAP page for more info), AFAIK, SageMath doesn’t have something similar. I’ve written one (see below) based on the mountain of hard work done years ago by Emily Kirkman.

def graph_id_graph6(Gamma, verbose=False):
    """
    Returns the graph6 id of Gamma = (V,E).
    If verbose then it also displays the table of all graphs with
    |V| vertices and |E| edges.

    Assumes Gamma is a "small" graph.

    EXAMPLES:
    sage: Gamma = graphs.HouseGraph()
    sage: graph_id_graph6(Gamma, verbose=False)
    'Dbk'
    sage: graph_id_graph6(Gamma, verbose=True)

     graphs with 5 vertices and 6 edges:

    Graph6               Aut Grp Size         Degree Sequence     
    ------------------------------------------------------------
    DB{                  2                    [1, 2, 2, 3, 4]     
    DFw                  12                   [2, 2, 2, 3, 3]     
    DJ[                  24                   [0, 3, 3, 3, 3]     
    DJk                  2                    [1, 2, 3, 3, 3]     
    DK{                  8                    [2, 2, 2, 2, 4]     
    Dbk                  2                    [2, 2, 2, 3, 3]     


    'Dbk'

"""
n = len(Gamma.vertices())
m = len(Gamma.edges())
ds = Gamma.degree_sequence()
Q = GraphQuery(display_cols=['graph6', 'aut_grp_size', 'degree_sequence'], num_edges=['=', m], num_vertices=["=", n])
for g in Q:
    if g.is_isomorphic(Gamma):
        if verbose:
            print("\n graphs with %s vertices"%n+" and %s edges:\n"%m)
            Q.show()
            print("\n")
        return g.graph6_string()

Harmonic morphisms to P_4 – examples

Posted on 2020/03/17 by wdjoyner

This post expands on a previous post and gives more examples of harmonic morphisms to the path graph $\Gamma_2=P_4$ .
path4-0123

First, a simple remark about harmonic morphisms in general: roughly speaking, they preserve adjacency. Suppose $\phi:\Gamma_1\to \Gamma_2$ is a harmonic morphism. Let $v,w\in V_1$ be adjacent vertices of $\Gamma_1$ . Then either (a) $\phi(v)=\phi(w)$ and $\phi$ “collapses” the edge (vertical) $(v,w)$ or (b) $\phi(v)\not= \phi(w)$ and the vertices $\phi(v)$ and $\phi(w)$ are adjacent in $\Gamma_2$ . In the particular case of this post (ie, the case of $\Gamma_2=P_4$ ), this remark has the following consequence: since in $P_4$ the white vertex is not adjacent to the blue or red vertex, none of the harmonic colored graphs below can have a white vertex adjacent to a blue or red vertex.

We first consider the cyclic graph on k vertices, $C_k$ as the domain in this post. However, before we get to examples (obtained by using SageMath), I’d like to state a (probably naive) conjecture.

Let $\phi:\Gamma_1 \to \Gamma_2=P_k$ be a harmonic morphism from a graph $\Gamma_1$ with $n=|V_1|$ vertices to the path graph having $k>2$ vertices. Let $f:V_2 \to V_1$ be the coloring map (identified with an n-tuple whose coordinates are in $\{0,1,\dots ,k-1\}$ ). Associated to f is a partition $\Pi_f=[n_0,\dots,n_{k-1}]$ of n (here $[...]$ is a multi-set, so repetition is allowed but the ordering is unimportant): $n=n_0+n_1+...+n_{k-1}$ , where $n_j$ is the number of times j occurs in f. We call this the partition invariant of the harmonic morphism.

Definition: For any two harmonic morphisms $\phi:\Gamma_1 \to P_k$ , $\phi:\Gamma'_1 \to P_k$ , with associated
colorings $f, f'$ whose corresponding partitions agree, $\Pi_f=\Pi_{f'}$ then we say $f'$ and $f$ are partition equivalent.

What can be said about partition equivalent harmonic morphisms? Caroline Melles has given examples where partition equivalent harmonic morphisms are not induced from an automorphism.

Now onto the $\Gamma_1 \to P_4$ examples!

There are no non-trivial harmonic morphisms $C_5 \to P_4$ , so we start with $C_6$ . We indicate a harmonic morphism by a vertex coloring. An example of a harmonic morphism can be described in the plot below as follows: $\phi:\Gamma_1\to \Gamma_2=P_4$ sends the red vertices in $\Gamma_1$ to the red vertex of $\Gamma_2=P_4$ (we let 3 be the numerical notation for the color red), the blue vertices in $\Gamma_1$ to the blue vertex of $\Gamma_2=P_4$ (we let 2 be the numerical notation for the color blue), the green vertices in $\Gamma_1$ to the green vertex of $\Gamma_2=P_4$ (we let 1 be the numerical notation for the color green), and the white vertices in $\Gamma_1$ to the white vertex of $\Gamma_2=P_4$ (we let 0 be the numerical notation for the color white).

To get the following data, I wrote programs in Python using SageMath.

Example 1: There are only the 4 trivial harmonic morphisms $C_6 \to P_4$ , plus that induced by $f = (1, 2, 3, 2, 1, 0)$ and all of its cyclic permutations (4+6=10). This set of 6 permutations is closed under the automorphism of $P_4$ induced by the transposition (0,3)(1,2) (so total = 10). cyclic6-123210

Example 2: There are only the 4 trivial harmonic morphisms, plus $f = (1, 2, 3, 2, 1, 0, 0)$ and all of its cyclic permutations (4+7=11). This set of 7 permutations is not closed under the automorphism of $P_4$ induced by the transposition (0,3)(1,2), so one also has $f = (2, 1, 0, 1, 2, 3, 3)$ and all 7 of its cyclic permutations (total = 7+11 = 18).
cyclic7-1232100
cyclic7-1233210

Example 3: There are only the 4 trivial harmonic morphisms, plus $f = (1, 2, 3, 2, 1, 0, 0, 0)$ and all of its cyclic permutations (4+8=12). This set of 8 permutations is not closed under the automorphism of $P_4$ induced by the transposition (0,3)(1,2), so one also has $f = (1, 2, 3, 3, 3, 2, 1, 0)$ and all of its cyclic permutations (12+8=20). In addition, there is $f = (1, 2, 3, 3, 2, 1, 0, 0)$ and all of its cyclic permutations (20+8 = 28). The latter set of 8 cyclic permutations of $(1, 2, 3, 3, 2, 1, 0, 0)$ is closed under the transposition (0,3)(1,2) (total = 28).
cyclic8-12321000
cyclic8-12333210
cyclic8-12332100

Example 4: There are only the 4 trivial harmonic morphisms, plus $f = (1, 2, 3, 2, 1, 0, 0, 0, 0)$ and all of its cyclic permutations (4+9=13). This set of 9 permutations is not closed under the automorphism of $P_4$ induced by the transposition (0,3)(1,2), so one also has $f = (1, 2, 3, 3, 2, 1, 0, 0, 0)$ and all 9 of its cyclic permutations (9+13 = 22). This set of 9 permutations is not closed under the automorphism of $P_4$ induced by the transposition (0,3)(1,2), so one also has $f = (1, 2, 3, 3, 3, 2, 1, 0, 0)$ and all 9 of its cyclic permutations (9+22 = 31). This set of 9 permutations is not closed under the automorphism of $P_4$ induced by the transposition (0,3)(1,2), so one also has $f = (1, 2, 3, 3, 3, 3, 2, 1, 0)$ and all 9 of its cyclic permutations (total = 9+31 = 40). cyclic9-123210000 cyclic9-123321000 cyclic9-123332100 cyclic9-123333210

Next we consider some cubic graphs.

Example 5: There are 5 cubic graphs on 8 vertices, as listed on this wikipedia page. I wrote a SageMath program that looked for harmonic morphisms on a case-by-case basis. There are no non-trivial harmonic morphisms from any one of these 5 graphs to $P_4$ .

Example 6: There are 19 cubic graphs on 10 vertices, as listed on this wikipedia page. I wrote a SageMath program that looked for harmonic morphisms on a case-by-case basis. The only one of these 19 cubic graphs $\Gamma_1$ having a harmonic morphism $\phi:\Gamma_1\to P_4$ is the graph whose SageMath command is graphs.LCFGraph(10,[5, -3, -3, 3, 3],2). It has diameter 3, girth 4, and automorphism group of order 48 generated by (4,6), (2,8)(3,7), (1,9), (0,2)(3,5), (0,3)(1,4)(2,5)(6,9)(7,8). There are eight non-trivial harmonic morphisms $\phi:\Gamma_1\to P_4$ . They are depicted as follows:
3regular10nn-P4-1112322210
3regular10nn-P4-1112223210
3regular10nn-P4-1012322211
3regular10nn-P4-1012223211
3regular10nn-P4-2321110122
3regular10nn-P4-2321011122
3regular10nn-P4-2221110123
3regular10nn-P4-2221011123
Note that the last four are obtained from the first 4 by applying the permutation (0,3)(1,2) to the colors (where 0 is white, etc, as above).

We move to cubic graphs on 12 vertices. There are quite a few of them – according to the House of Graphs page on connected cubic graphs, there are 109 of them (if I counted correctly).

Example 7: The cubic graphs on 12 vertices are listed on this wikipedia page. I wrote a SageMath program that looked for harmonic morphisms on a case-by-case basis. If there is no harmonic morphism $\Gamma_1\to P_4$ then, instead of showing a graph, I’ll list the edges (of course, the vertices are 0,1,…,11) and the SageMath command for it.

$\Gamma_1=(V_1,E_1)$ , where $E_1=\{ (0, 1), (0, 2), (0, 11), (1, 2), (1, 6), (2, 3), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)\}$ .
SageMath command:
V1 = [0,1,2,3,4,5,6,7,8,9,10,11] E1 = [(0,1), (0,2), (0,11), (1,2), (1,6),(2,3), (3,4), (3,5), (4,5), (4,6), (5,6), (7,8), (7,9), (7,11), (8,9),(8,10), (9,10), (10,11)] Gamma1 = Graph([V1,E1])
(Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
$\Gamma_1=(V_1,E_1)$ , where $E_1=\{ (0, 1), (0, 6), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)\}$ .
SageMath command:
V1 = [0,1,2,3,4,5,6,7,8,9,10,11] E1 = [(0, 1), (0, 6), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)] Gamma1 = Graph([V1,E1])
(Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
$\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0,1),(0,3),(0,11),(1,2),(1,6),(2,3),(2,5),(3,4),(4,5),(4,6),(5,6),(7,8),(7,9),(7,11),(8,9),(8,10),(9,10),(10,11)\}$ .
SageMath command:
V1 = [0,1,2,3,4,5,6,7,8,9,10,11] E1 = [(0,1),(0,3),(0,11),(1,2),(1,6),(2,3),(2,5),(3,4),(4,5),(4,6),(5,6),(7,8),(7,9),(7,11),(8,9),(8,10),(9,10),(10,11)] Gamma1 = Graph([V1,E1])
(Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
$\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 11), (2, 3), (2, 10), (3, 4), (4, 5), (4, 8), (5, 6), (5, 7), (6, 7), (6, 9), (7, 8), (8, 9), (9, 10), (10, 11)\}$ .
SageMath command:
Gamma1 = graphs.LCFGraph(12, [3, -2, -4, -3, 4, 2], 2)
$\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 11), (2, 3), (2, 10), (3, 4), (4, 5), (4, 7), (5, 6), (5, 8), (6, 7), (6, 9), (7, 8), (8, 9), (9, 10), (10, 11)\}$ .
SageMath command:
Gamma1 = graphs.LCFGraph(12, [3, -2, -4, -3, 3, 3, 3, -3, -3, -3, 4, 2], 1)
$\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0, 1), (0, 4), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7), (6, 8), (7, 8), (7, 10), (8, 9), (9, 10), (9, 11), (10, 11)\}$ .
SageMath command:
Gamma1 = graphs.LCFGraph(12, [4, 2, 3, -2, -4, -3, 2, 3, -2, 2, -3, -2], 1)
$\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7), (6, 9), (7, 8), (7, 10), (8, 9), (8, 11), (9, 10), (10, 11)\}$ .
SageMath command:
Gamma1 = graphs.LCFGraph(12, [3, 3, 3, -3, -3, -3], 2)
(list under construction)

Harmonic morphisms to P_3 – examples

Posted on 2020/02/06 by wdjoyner

This post expands on a previous post and gives more examples of harmonic morphisms to the path graph $\Gamma_2=P_3$ .

The path graph P_3

If $\Gamma_1 = (V_1, E_1)$ and $\Gamma_2 = (V_2, E_2)$ are graphs then a map $\phi:\Gamma_1\to \Gamma_2$ (that is, $\phi: V_1\cup E_1\to V_2\cup E_2$ ) is a morphism provided

if $\phi$ sends an edge to an edge then the edges vertices must also map to each other: $e=(v,w)\in E_1$ and $\phi(e)\in E_2$ then $\phi(e)$ is an edge in $\Gamma_2$ having vertices $\phi(v)\in V_2$ and $\phi(w)\in V_2$ , where $\phi(v)\not= \phi(w)$ , and
if $\phi$ sends an edge to a vertex then the edges vertices must also map to that vertex: if $e=(v,w)\in E_1$ and $\phi(e)\in V_2$ then $\phi(e) = \phi(v) = \phi(w)$ .

As a non-example, if $\Gamma_1$ is a planar graph, if $\Gamma_2$ is its dual graph, and if $\phi:\Gamma_1\to\Gamma_2$ is the dual map $V_1\to E_2$ and $E_1\to V_2$ , then $\phi$ is not a morphism.

Given a map $\phi_E : E_1 \rightarrow E_2 \cup V_2$ , an edge $e_1$ is called horizontal if $\phi_E(e_1) \in E_2$ and is called vertical if $\phi_E(e_1) \in V_2$ . We say that a graph morphism $\phi: \Gamma_1 \rightarrow \Gamma_2$ is a graph homomorphism if $\phi_E (E_1) \subset E_2$ . Thus, a graph morphism is a homomorphism if it has no vertical edges.

Suppose that $\Gamma_2$ has at least one edge. Let $Star_{\Gamma_1}(v)$ denote the star subgraph centered at the vertex v. A graph morphism $\phi : \Gamma_1 \to \Gamma_2$ is called harmonic if for all vertices $v \in V(\Gamma_1)$ , the quantity
$\mu_\phi(v,f)= |\phi^{-1}(f) \cap Star_{\Gamma_1}(v)|$
(the number of edges in $\Gamma_1$ adjacent to $v$ and mapping to the edge $f$ in $\Gamma_2$ ) is independent of the choice of edge $f$ in $Star_{\Gamma_2}(\phi(v))$ .

An example of a harmonic morphism can be described in the plot below as follows: $\phi:\Gamma_1\to \Gamma_2=P_3$ sends the red vertices in $\Gamma_1$ to the red vertex of $\Gamma_2=P_3$ , the green vertices in $\Gamma_1$ to the green vertex of $\Gamma_2=P_3$ , and the white vertices in $\Gamma_1$ to the white vertex of $\Gamma_2=P_3$ .

Example 1:

P3-C3-V

Example 2:
D3-2110

Example 3:
cyclic4-2101

MINIMOGs and Mathematical blackjack

Posted on 2017/09/30 by wdjoyner

This is an exposition of some ideas of Conway, Curtis, and Ryba on $S(5,6,12)$ and a card game called mathematical blackjack (which has almost no relation with the usual Blackjack).

Many thanks to Alex Ryba and Andrew Buchanan for helpful discussions on this post.

Definitions

An m-(sub)set is a (sub)set with m elements. For integers $k<m<n$ , a Steiner system S(k,m,n) is an n-set X and a set S of m-subsets having the property that any k-subset of X is contained in exactly one m-set in S. For example, if $X = \{1,2,\dots,12\}$ , a Steiner system S(5,6,12) is a set of 6-sets, called hexads, with the property that any set of 5 elements of X is contained in (“can be completed to”) exactly one hexad.

Rob Beezer has a nice Sagemath description of S(5,6,12).

If S is a Steiner system of type (5,6,12) in a 12-set X then any element the symmetric group $\sigma\in Symm_X\cong S_{12}$ of X sends S to another Steiner system $\sigma(S)$ of X. It is known that if S and S’ are any two Steiner systems of type (5,6,12) in X then there is a $\sigma\in Symm_X$ such that $S'=\sigma(S)$ . In other words, a Steiner system of this type is unique up to relabelings. (This also implies that if one defines $M_{12}$ to be the stabilizer of a fixed Steiner system of type (5,6,12) in X then any two such stabilizer groups, for different Steiner systems in X, must be conjugate in $Symm_X$ . In particular, such a definition is well-defined up to isomorphism.)

Curtis’ kitten

NICOLE SHENTING – Cats Playing Poker Cards

J. Conway and R. Curtis [Cu1] found a relatively simple and elegant way to construct hexads in a particular Steiner system $S(5,6,12)$ using the arithmetical geometry of the projective line over the finite field with 11 elements. This section describes this.

Let $\mathbf{P}^1(\mathbf{F}_{11}) =\{\infty,0,1,2,...,9,10\}$ denote the projective line over the finite field $\mathbf{F}_{11}$ with 11 elements. Let $Q=\{0,1,3,4,5,9\}$ denote the quadratic residues with 0, and let $L=\cong PSL(2,\mathbf{F}_{11}),$ where $\alpha(y)=y+1$ and $\beta(y)=-1/y$ . Let $S=\{\lambda(Q)\ \vert\ \lambda\in L\}.$

Lemma 1: $S$ is a Steiner system of type $(5,6,12)$ .

The elements of S are known as hexads (in the “modulo 11 labeling”).

 	 	 	 	 		 	 	 	 	 
 	 	 	 	 	 	 	 	 	 	 
 	 	 	 	 	6	 	 	 	 	 
 	 	 	 	 	 	 	 	 	 	 
 	 	 	 	2	 	10	 	 	 	 
 	 	 	 	 	 	 	 	 	 	 
 	 	 	5	 	7	 	3	 	 	 
 	 	 	 	 	 	 	 	 	 	 
 	 	6	 	9	 	4	 	6	 	 
 	 	 	 	 	 	 	 	 	 	 
 	2	 	10	 	8	 	2	 	10	 
 	 	 	 	 	 	 	 	 	 	 
0	 	 	 	 	 	 	 	 	 	1

Curtis’ Kitten.

In any case, the “views” from each of the three “points at infinity” is given in the following tables.

6	10	3
2	7	4
5	9	8
picture at 

5	7	3
6	9	4
2	10	8
picture at 	

5	7	3
9	4	6
8	2	10
picture at

Each of these $3\times 3$ arrays may be regarded as the plane $\mathbf{F}_3^2$ . The lines of this plane are described by one of the following patterns.

		
		
			
slope 0	

		
		
			
slope infinity

		
		
			
slope -1

		
		
		
slope 1

The union of any two perpendicular lines is called a cross. There are 18 crosses. The complement of a cross in $\mathbf{F}_3^2$ is called a square. Of course there are also 18 squares. The hexads are

$\{0,1,\infty\}\cup \{{\rm any\ line}\}$ ,
the union of any two (distinct) parallel lines in the same picture,
one “point at infinity” union a cross in the corresponding picture,
two “points at infinity” union a square in the picture corresponding to the omitted point at infinity.

Lemma 2 (Curtis [Cu1]) There are 132 such hexads (12 of type 1, 12 of type 2, 54 of type 3, and 54 of type 4). They form a Steiner system of type $(5,6,12)$.

The MINIMOG description

Following Curtis’ description [Cu2] of a Steiner system $S(5,8,24)$ using a $4\times 6$ array, called the MOG, Conway [Co1] found and analogous description of $S(5,6,12)$ using a $3\times 4$ array, called the MINIMOG. This section is devoted to the MINIMOG. The tetracode words are

0	0	0	0		0	+	+	+		0	-	-	-
+	0	+	-		+	+	-	0		+	-	0	+
-	0	-	+		-	+	0	-		-	-	+	0

With ”0″=0, “+”=1, “-“=2, these vectors form a linear code over GF(3). (This notation is Conway’s. One must remember here that “+”+”+”=”-“!) They may also be described as the set of all 4-tuples in of the form
$(0,a,a,a),(1,a,b,c),(2,c,b,a),$
where abc is any cyclic permutation of 012. The MINIMOG in the shuffle numbering is the array
$\begin{array}{cccc} 6 & 3 & 0 & 9\\ 5 & 2 & 7 & 10 \\ 4 & 1 & 8 & 11 \end{array}$
We label the rows of the MINIMOG array as follows:

the first row has label 0,
the second row has label +,
the third row has label –

A col (or column) is a placement of three + signs in a column of the MINIMOG array. A tet (or tetrad) is a placement of 4 + signs having entries corresponding (as explained below) to a tetracode.

+	 	 	 
 	+	+	+
 	 	 	 
0	+	+	+

+	 	 	 
 	 	 	 
 	+	+	+


0	-	-	-

 	+	 	 
+	 	+	 
 	 	 	+

+	0	+	-

 	 	 	+
+	+	 	 
 	 	+	 

+	+	-	0

 	 	+	 
+	 	 	+
 	+	 	 


+	-	0	+

 	+	 	 
 	 	 	+
+	 	+	 

-	0	-	+

 	 	+	 
 	+	 	 
+	 	 	+

-	+	0	-

 	 	 	+
 	 	+	 
+	+	 	 


-	-	+	0

Each line in $\mathbf{F}_3^2$ with finite slope occurs once in the $3\times 3$ part of some tet. The odd man out for a column is the label of the row corresponding to the non-zero digit in that column; if the column has no non-zero digit then the odd man out is a “?”. Thus the tetracode words associated in this way to these patterns are the odd men out for the tets. The signed hexads are the combinations $6$-sets obtained from the MINIMOG from patterns of the form

col-col, col+tet, tet-tet, col+col-tet.

Lemma 3 (Conway, [CS1], chapter 11, page 321) If we ignore signs, then from these signed hexads we get the 132 hexads of a Steiner system $S(5,6,12)$ . These are all possible $6$-sets in the shuffle labeling for which the odd men out form a part (in the sense that an odd man out “?” is ignored, or regarded as a “wild-card”) of a tetracode word and the column distribution is not $0,1,2,3$ in any order.

Furthermore, it is known [Co1] that the Steiner system $S(5,6,12)$ in the shuffle labeling has the following properties.

There are $11$ hexads with total $21$ and none with lower total.
The complement of any of these $11$ hexads in $\{0,1,...,11\}$ is another hexad.
There are $11$ hexads with total $45$ and none with higher total.

Mathematical blackjack

Mathematical blackjack is a 2-person combinatorial game whose rules will be described below. What is remarkable about it is that a winning strategy, discovered by Conway and Ryba [CS2] and [KR], depends on knowing how to determine hexads in the Steiner system $S(5,6,12)$ using the shuffle labeling.

Mathematical blackjack is played with 12 cards, labeled $0,\dots ,11$ (for example: king, ace, $2$ , $3$ , …, $10$ , jack, where the king is $0$ and the jack is $11$ ). Divide the 12 cards into two piles of $6$ (to be fair, this should be done randomly). Each of the $6$ cards of one of these piles are to be placed face up on the table. The remaining cards are in a stack which is shared and visible to both players. If the sum of the cards face up on the table is less than 21 then no legal move is possible so you must shuffle the cards and deal a new game. (Conway [Co2] calls such a game *={0|0}, where 0={|}; in this game the first player automatically wins.)

Players alternate moves.
A move consists of exchanging a card on the table with a lower card from the other pile.
The player whose move makes the sum of the cards on the table under 21 loses.

The winning strategy (given below) for this game is due to Conway and Ryba [CS2], [KR]. There is a Steiner system $S(5,6,12)$ of hexads in the set $\{0,1,...,11\}$ . This Steiner system is associated to the MINIMOG of in the “shuffle numbering” rather than the “modulo $11$ labeling”.

The following result is due to Ryba.

Proposition 6: For this Steiner system, the winning strategy is to choose a move which is a hexad from this system.

This result is proven in a wonderful paper J. Kahane and A. Ryba, [KR]. If you are unfortunate enough to be the first player starting with a hexad from $S(5,6,12)$ then, according to this strategy and properties of Steiner systems, there is no winning move! In a randomly dealt game there is a probability of 1/7 that the first player will be dealt such a hexad, hence a losing position. In other words, we have the following result.

Corollary 7: The probability that the first player has a win in mathematical blackjack (with a random initial deal) is 6/7.

An example game is given in this expository hexads_sage (pdf).

Bibliography

[Cu1] R. Curtis, “The Steiner system $S(5,6,12)$, the Mathieu group $M_{12}$, and the kitten,” in Computational group theory, ed. M. Atkinson, Academic Press, 1984.
[Cu2] —, “A new combinatorial approach to $M_{24}$,” Math Proc Camb Phil Soc 79(1976)25-42
[Co1] J. Conway, “Hexacode and tetracode – MINIMOG and MOG,” in Computational group theory, ed. M. Atkinson, Academic Press, 1984.
[Co2] —, On numbers and games (ONAG), Academic Press, 1976.
[CS1] J. Conway and N. Sloane, Sphere packings, Lattices and groups, 3rd ed., Springer-Verlag, 1999.
[CS2] —, “Lexicographic codes: error-correcting codes from game theory,” IEEE Trans. Infor. Theory32(1986)337-348.
[KR] J. Kahane and A. Ryba, “The hexad game,” Electronic Journal of Combinatorics, 8 (2001)

Memories of TS Michael, by Thomas Quint

Posted on 2016/12/08 by wdjoyner

TS Michael passed away on November 22, 2016, from cancer. I will miss him as a colleague and a kind, wise soul. Tom Quint has kindly allowed me to post these reminiscences that he wrote up.

Well, I guess I could start with the reason TS and I met in the first place. I was a postdoc at USNA in about 1991 and pretty impressed with myself. So when USNA offered to continue my postdoc for two more years (rather than give me a tenure track position), I turned it down. Smartest move I ever made, because TS got the position and so we got to know each other.

We started working w each other one day when we both attended a talk on “sphere of influence graphs”. I found the subject moderately interesting, but he came into my office all excited, and I couldn’t get rid of him — wouldn’t leave until we had developed a few research ideas.

Interestingly, his position at USNA turned into a tenure track, while mine didn’t. It wasn’t until 1996 that I got my position at U of Nevada.

Work sessions with him always followed the same pattern. As you may or may not know, T.S. a) refused to fly in airplanes, and b) didn’t drive. Living across the country from each other, the only way we could work together face-to-face was: once each summer I would fly out to the east coast to visit my parents, borrow one of their cars for a week, and drive down to Annapolis. First thing we’d do is go to Whole Foods, where he would load up my car with food and other supplies, enough to last at least a few months. My reward was that he always bought me the biggest package of nigiri sushi we could find — not cheap at Whole Foods!

It was fun, even though I had to suffer through eight million stories about the USNA Water Polo Team.

Oh yes, and he used to encourage me to sneak into one of the USNA gyms to work out. We figured that no one would notice if I wore my Nevada sweats (our color is also dark blue, and the pants also had a big “N” on them). It worked.

Truth be told, TS didn’t really have a family of his own, so I think he considered the mids as his family. He cared deeply about them (with bonus points if you were a math major or a water polo player :-).

One more TS anecdote, complete with photo. Specifically, TS was especially thrilled to find out that we had named our firstborn son Theodore Saul Quint. Naturally, TS took to calling him “Little TS”. At any rate, the photo below is of “Big TS” holding “Little TS”, some time in the Fall of 2000.

TS Michael in 2000.

A tribute to TS Michael

Posted on 2016/11/30 by wdjoyner

I’ve known TS for over 20 years as a principled colleague and a great teacher.

TS at the USNA in Dec 2015.

However, we really never spoke much except for the past five-to-ten years or so. For a period, I wrote a lot about error-correcting codes and we’d talk occasionally about our common interests (for example, I found his paper “The rigidity theorems of Hamada and Ohmori, revisited” fascinating). However, once I became interested in graph theory, we spoke as often as I could corner him. He taught me a lot and only know I realize how lucky I was to have him as a colleague.

I remember many times, late on a Friday, when we’d talk for an hour or two about chess, mathematics, “office politics” (he always knew more than me), and allergies. Here’s one of his favorite chess problems:

Mate in 549 moves. This problem was discovered by a team of chess engame experts at Lomonosov University, Moscow, August 2012.

Maybe this says more about me than him, but when it was just the two of us, we rarely talked about families or relationships. None-the-less, he always treated me like a good friend. One of my favorite memories was when my wife and I were shopping at the plaza where his condo building was located (it’s a big plaza). Elva and I were walking store-to-store when we spotted TS. He was walking to distract himself from his discomfort. At the time, doctors didn’t know what his problems were and he suspected allergies. I have a number of food sensitivities and he was a welcomed fountain of medical knowledge about these issues. (In fact, his hints have really helped me a lot, health-wise.) In any case, TS and Elva and I spoke for 30 minutes or so about health and family. I remember how gracious and thoughtful he was, skillfully steering the conversation into non-technical matters for Elva’s benefit. I ran into him another time while waiting for Elva, who was in a nearby doctor’s office (I told you this was a big shopping plaza). TS generously waited with me until Elva was ready to be picked up. What we chatted about is lost in the cobwebs of my memory but I remember vividly where we sat and the kind of day it was. TS had such a kind heart.

As I said, TS taught me a lot about graph theory. Whether in-between classes or when I was lucky enough to spot him late in the day, he’d kindly entertain my naive (usually false) conjectures and speculations about strongly regular graphs. I never heard him speak in anything but the kindest terms. He’d never say “that’s just plain wrong” or “idiotic” (even if it was) but instead teach me the correct way to think about it in a matter in which I could see myself how my speculations were wrong-headed. My upcoming book with Caroline Melles is indebted to his insight and suggestions.

Even after he left Maryland to spend his remaining days with his family in California, TS emailed encouragement and suggestions about an expository paper I was writing to help connect my matrix theory students with the methods of ranking sports teams. While he was very helpful and provided me with his excellent insights as usual, in truth, I used the work on the paper as an excuse to keep up with his health status. I’m relatively ignorant of medical issues and tried to stay optimistic until it’s totally unrealistic. As sad as it was, we was always frank and honest with me about his prognosis.

He’s gone now, but as a teacher, researcher, and as a kind soul, TS is unforgettable.

A list of TS’s publications:

T. S. Michael, Tournaments, book chapter in Handbook of Linear Algebra, 2nd ed, CRC Press, Boca Raton, 2013.
T. S. Michael, Cycles of length 5 in triangle-free graphs: a sporadic counterexample to a characterization of equality, Bulletin of the Institute of Combinatorics and Its Applications, 67 (2013) 6–8.
T. S. Michael and Val Pinciu, Guarding orthogonal prison yards: an upper bound,
Congressus Numerantium, 211 (2012) 57–64.
Ilhan Hacioglu and T. S. Michael, The p-ranks of residual and derived skew Hadamard designs,
Discrete Mathematics, 311 (2011) 2216-2219.
T. S. Michael, Guards, galleries, fortresses, and the octoplex, College Math Journal, 42 (2011) 191-200. (This paper won a Polya Award)
Elizabeth Doering, T. S. Michael, and Bryan Shader, Even and odd tournament matrices with minimum rank over finite fields, Electronic Journal of Linear Algebra, 22 (2011) 363-377.
Brenda Johnson, Mark E. Kidwell, and T. S. Michael, Intrinsically knotted graphs have at least 21 edges, Journal of Knot Theory and Its Ramifications, 19 (2010) 1423-1429.
T. S. Michael, How to Guard an Art Gallery and Other Discrete Mathematical Adventures. Johns Hopkins University Press, Baltimore, 2009.
T. S. Michael and Val Pinciu, Art gallery theorems and triangulations, DIMACS Educational Module Series, 2007, 18 pp (electronic 07-1)
T. S. Michael and Thomas Quint, Sphericity, cubicity, and edge clique covers of graphs, Discrete Applied Mathematics, 154 (2006) 1309-1313.
T. S. Michael and Val Pinciu, Guarding the guards in art galleries, Math Horizons, 14 (2006), 22-23, 25.
Richard J. Bower and T. S. Michael, Packing boxes with bricks, Mathematics Magazine, 79 (2006), 14-30.
T. S. Michael and Thomas Quint, Optimal strategies for node selection games: skew matrices and symmetric games, Linear Algebra and Its Applications 412 (2006) 77-92.
T. S. Michael, Ryser’s embedding problem for Hadamard matrices, Journal of Combinatorial Designs 14 (2006) 41-51.
Richard J. Bower and T. S. Michael, When can you tile a box with translates of two given rectangular bricks?, Electronic Journal of Combinatorics 11 (2004) Note 7, 9 pages.
T. S. Michael and Val Pinciu, Art gallery theorems for guarded guards, Computational Geometry 26 (2003) 247-258.
T. S. Michael, Impossible decompositions of complete graphs into three Petersen subgraphs, Bulletin of the Institute of Combinatorics and Its Applications 39 (2003) 64-66.
T. S. Michael and William N. Traves, Independence sequences of well-covered graphs: non-unimodality and the roller-coaster conjecture, Graphs and Combinatorics 19 (2003) 403-411.
T. S. Michael and Thomas Quint, Sphere of influence graphs and the L-Infinity metric, Discrete Applied Mathematics 127 (2003) 447-460.
T. S. Michael, Signed degree sequences and multigraphs, Journal of Graph Theory 41 (2002) 101-105.
T. S. Michael and Val Pinciu, Multiply guarded guards in orthogonal art galleries, Lecture Notes in Computer Science 2073, pp 753-762, in: Proceedings of the International Conference on Computer Science, San Francisco, Springer, 2001.
T. S. Michael, The rigidity theorems of Hamada and Ohmori, revisited, in Coding Theory and Cryptography: From the Geheimschreiber and Enigma to Quantum Theory. (Annapolis, MD, 1998), 175-179, Springer, Berlin, 2000.
T. S. Michael and Thomas Quint, Sphere of influence graphs in general metric spaces, Mathematical and Computer Modelling, 29 (1999) 45-53.
Suk-Geun Hwang, Arnold R. Kraeuter, and T. S. Michael, An upper bound for the permanent of a nonnegative matrix, Linear Algebra and Its Applications 281 (1998), 259-263.
* First Corrections: Linear Algebra and Its Applications 300 (1999), no. 1-3, 1-2
T. S. Michael and W. D. Wallis, Skew-Hadamard matrices and the Smith normal form, Designs, Codes, and Cryptography, 13 (1998) 173-176.
T. S. Michael, The p-ranks of skew Hadamard designs, Journal of Combinatorial Theory, Series A, 73 (1996) 170-171.
T. S. Michael, The ranks of tournament matrices, American Mathematical Monthly, 102 (1995) 637-639.
T. S. Michael, Lower bounds for graph domination by degrees, pp 789-800 in Graph Theory, Combinatorics, and Algorithms: Proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs, Y. Alavi and A. Schwenk (eds.), Wiley, New York, 1995.
T. S. Michael and Thomas Quint, Sphere of influence graphs: a survey, Congressus Numerantium, 105 (1994) 153-160.
T. S. Michael and Thomas Quint, Sphere of influence graphs: edge density and clique size, Mathematical and Computer Modelling, 20 (1994) 19-24.
T. S. Michael and Aaron Stucker, Mathematical pitfalls with equivalence classes, PRIMUS, 3 (1993) 331-335.
T. S. Michael, The structure matrix of the class of r-multigraphs with a prescribed degree sequence, Linear Algebra and Its Applications, 183 (1993) 155-177.
T. S. Michael, The decomposition of the complete graph into three isomorphic strongly regular graphs, Congressus Numerantium, 85 (1991) 177-183.
T. S. Michael, The structure matrix and a generalization of Ryser’s maximum term rank formula, Linear Algebra and Its Applications, 145 (1991) 21-31.
Richard A. Brualdi and T. S. Michael, The class of matrices of zeros, ones and twos with prescribed row and column sums, Linear Algebra and Its Applications, 114(115) (1989) 181-198.
Richard A. Brualdi and T. S. Michael, The class of 2-multigraphs with a prescribed degree sequence, Linear and Multilinear Algebra, 24 (1989) 81-102.
Richard A. Brualdi, John L. Goldwasser, and T. S. Michael, Maximum permanents of matrices of zeros and ones, Journal of Combinatorial Theory, Series A, 47 (1988) 207-245.

Memories of TS Michael, by Bryan Shader

Posted on 2016/11/28 by wdjoyner

TS Michael passed away on November 22, 2016, from cancer. I will miss him as a colleague and a kind, wise soul.

TS Michael in December 2015 at the USNA

Bryan Shader has kindly allowed me to post these reminiscences that he wrote up.

Memories of TS Michael, by Bryan Shader

Indirect influence
TS indirectly influenced my choice of U. Wisconsin-Madison for graduate school. My senior year as an undergraduate, Herb Ryser gave a talk at my school. After the talk I was able to meet Ryser and asked for advice on graduate schools. Herb indicated that one of his very good undergraduate students had chosen UW-Madison and really liked the program. I later found out that the person was TS.

About the name
Back in the dark ages, universities still did registration by hand. This meant that for a couple of days before each semester the masses of students would wind their way through a maze of stations in a large gymnasium. For TS’s first 4 years, he would invariably encounter a road block because someone had permuted the words in his name (Todd Scott Michael) on one of the forms. After concretely verifying the hatcheck probabilities and fearing that this would cause some difficulties in graduating, he legally changed his name to TS Michael.

Polyominoes & Permanents
I recall many stories about how TS’s undergraduate work on polyominoes affected
his life. In particular, he recalled how once he started working on tilings on
polyominoes, he could no longer shower, or swim without visualizing polynomino
tilings on the wall’s or floor’s tiling. We shared an interest and passion for permanents (the permanent is a function of a matrix much like the determinant and plays a critical role in combinatorics). When working together we frequently would find that we both couldn’t calculate the determinant of a 3 by 3 matrix correctly, because we were calculating the permanent rather than the determinant.

Presentations and pipe-dreams
TS and I often talked about how best to give a mathematical lecture, or
presentation at a conference. Perhaps this is not at all surprising, as our common advisor (Richard Brualdi) is an incredible expositor, as was TS’s undergraduate advisor (Herb Ryser, our mathematical grandfather). TS often mentioned how Herb Ryser scripted every moment of a lecture; he knew each word he would write on the board and exactly where it would be written. TS wasn’t quite so prescriptive–but before any presentation he gave he would go to the actual room of the presentation a couple of times and run through the talk. This would include answering questions from the “pretend” audience. After being inspired by TS’s talks, I adopted this preparation method.
TS and I also fantasized about our talks ending with the audience lifting us up on their shoulders and carrying us out of the room in triumph! That is never happened to either of us (that I know of), but to have it, as a dream has always been a good motivation.

Mathematical heritage
TS was very interested in his mathematical heritage, and his mathematics brothers and sisters. TS was the 12th of Brandi’s 37 PhD students; I was the 15th. In 2005, TS and I organized a conference (called the Brualidfest) in honor of Richard Brualdi. Below I attach some photos of the design for the T-shirt.

t-shirt design for Brualdi-Fest, 1

The first image shows a biclique partition of K_5; for each color the edges of the given color form a complete bipartite graph; and each each of the completed graph on 5 vertices is in exactly one of these complete bipartite graph. This is related to one of TS’s favorite theorem: the Graham-Pollak Theorem.

t-shirt design for Bruldi-Fest, 2

The second image (when the symbols are replaced by 1s) is the incidence matrix of the projective plane of order 2; one of TS’s favorite matrices.

Here’s a photo of the Brualdi and his students at the conference:

ts-michaels_memories3

From L to R they are: John Mason (?), Thomas Forreger, John Goldwasser, Dan Pritikin, Suk-geun Hwang, Han Cho, T.S. Michael, B. Shader, Keith Chavey, Jennifer Quinn, Mark Lawrence, Susan Hollingsworth, Nancy Neudauer, Adam Berliner, and Louis Deaett.

Here’s a picture for a 2012 conference:

ts-michaels_memories4

From bottom to top: T.S. Michael (1988), US Naval Academy, MD; Bryan Shader (1990), University of Wyoming, WY; Jennifer Quinn (1993), University of Washington, Tacoma, WA; Nancy Neudauer (1998), Pacific University, OR; Susan Hollingsworth (2006), Edgewood College, WI; Adam Berliner (2009), St. Olaf College, MN; Louis Deaett (2009), Quinnipiac University, CT; Michael Schroeder (2011), Marshall University, WV; Seth Meyer (2012), Kathleen Kiernan (2012).

Here’s a caricature of TS made by Kathy Wilson (spouse of mathematician
Richard Wilson) at the Brualdifest:

TS Michael, by Kathy Wilson

Long Mathematical Discussions
During graduate school, TS and I would regularly bump into each other as we
were coming and going from the office. Often this happened as we were crossing University Avenue, one of the busiest streets in Madison. The typical conversation started with a “Hi, how are you doing? Have you considered X?” We would then spend the next 60-90 minutes on the street corner (whether it was a sweltering 90 degrees+, or a cold, windy day) considering X. In more recent years, these conversations have moved to hotel lobbies at conferences that we attend together. These discussions have been some of the best moments of my life, and through them I have become a better mathematician.

Here’s a photo of T.S. Michael with Kevin van der Meulen at the Brualdi-fest.

OLYMPUS DIGITAL CAMERA

I’m guessing they are in the midst of one of those “Have you considered X?” moments that TS is famous for.

Mathematical insight
TS has taught me a lot about mathematics, including:

How trying to generalize a result can lead to better understanding of the original result.
How phrasing a question appropriately is often the key to a mathematical breakthrough
Results that are surprising (e.g. go against ones intuition), use an elegant proof (e.g. bring in matrices in an unexpected way), and are aesthetically pleasing are worth pursing (as Piet Hein said “Problems worthy of attack, prove their worth by fighting back.”)
The struggle to present the proof of a result in the simplest, most self-contained way is important because often it produces a better understanding. If you can’t say something in a clean way, then perhaps you really don’t understand it fully.

TS’ mathematics fathers are:
Richard Brualdi ← Herb Ryser ← Cyrus MacDuffee ← Leonard Dickson ← E.H. Moore ← H. A. Newton ← Michel Chasles ← Simeon Poisoon ← Joseph Lagrange ← Leonhard Euler ← Johann Bernoulli.

Linear systems of graphs in Sage

Posted on 2015/05/22 by wdjoyner

Let $\Gamma$ be a graph. A divisor on $\Gamma$ is an element of the free group generated by the vertices $V$ , ${\mathbb{Z}}[V]$ .

We say that divisors $D$ and $D^\prime$ are linearly equivalent and write $D \sim D^\prime$ if $D^\prime-D$ is a principal divisor, i.e., if $D^\prime = D + \text{div}(f)$ for some function $f : V \rightarrow {\mathbb{Z}}$ . Note that if $D$ and $D^\prime$ are linearly equivalent, they must have the same degree, since the degree of every principal divisor is 0. Divisors of degree 0 are linearly equivalent if and only if they determine the same element of the Jacobian. If $D$ is a divisor of degree 0, we denote by $[D]$ the element of the Jacobian determined by $D$ . A divisor $D$ is said to be effective if $D(v) \geq 0$ for all vertices $v$ . We write $D \geq 0$ to mean that $D$ is effective. The linear system associated to a divisor $D$ is the set

$|D| = \{ D^\prime \in \text{Div}(\Gamma ) : D^\prime \geq 0 \text{ and } D^\prime \sim D\},$

i.e., $|D|$ is the set of all effective divisors linearly equivalent to $D$ . Note that if $D_1 \sim D_2$ , then $|D_1| = |D_2|$ . We note also that if $\text{deg}(D)<0$ , then $|D|$ must be empty.

Sage can be used to compute the linear system of any divisor on a graph.

def linear_system(D, Gamma):
    """
    Returns linear system attached to the divisor D.

    EXAMPLES:
        sage: Gamma2 = graphs.CubeGraph(2)
        sage: Gamma1 = Gamma2.subgraph(vertices = ['00', '01'], edges = [('00', '01')])
        sage: f = [['00', '01', '10', '11'], ['00', '01', '00', '01']]
        sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f)
        True
        sage: PhiV = matrix_of_graph_morphism_vertices(Gamma1, Gamma2, f); PhiV
        [1 0 1 0]
        [0 1 0 1]
        sage: D = vector([1,0,0,1])
        sage: PhiV*D
        (1, 1)
        sage: linear_system(PhiV*D, Gamma1)
        [(2, 0), (1, 1), (0, 2)]
        sage: linear_system(D, Gamma2)
        [(0, 2, 0, 0), (0, 0, 2, 0), (1, 0, 0, 1)]
        sage: [PhiV*x for x in linear_system(D, Gamma2)]
        [(0, 2), (2, 0), (1, 1)]

    """
    Q = Gamma.laplacian_matrix()
    CS = Q.column_space()
    N = len(D.list())
    d = sum(D.list())
    #print d
    lin_sys = []
    if d < 0:
        return lin_sys
    if (d == 0) and (D in CS):
        lin_sys = [CS(0)]
        return lin_sys
    elif (d == 0):
        return lin_sys
    S = IntegerModRing(d+1)^N
    V = QQ^N
    for v in S:
        v = V(v)
        #print D-v,v,D
        if D-v in CS:
            lin_sys.append(v)
    return lin_sys

Yet Another Mathblog

Tag Archives: combinatorics