Arithmetic of characters of generalized symmetric groups, revisited

Posted on 2026/11/04 by wdjoyner

Around 25-30 years ago, I was fascinated by the group structure of the Rubik’s cube group (whose size is roughly 4.3×10^19). It turns out (see my book on the Rubik’s cube for details) to be simply described using generalized symmetric groups. As a result, I wanted to know more about their representations and this lead to the question, what is the smallest field over which you can faithfully represent the generalized symmetric group (as matrices)? This lead to some lecture notes in 1998 and then a more refined preprint in 2002. After revisions, this was published in Archiv der Mathematik, vol 81 (2003)113–120.

What did AI think of this paper? While it found no serious errors (the main results and proofs were correct), Opus-Claude found an incorrect statement and that I’d mis-stated a result due to J.P. Serre. So I asked AI to write a more readable corrected version, adding a Glossary, Further directions paragraph, Literature review, and a Summary section. The corrected revision is here (11 page pdf). Hope you enjoy reading it as much as I did writing it!

Odd king tours on even chessboards, revisited

Posted on 2026/10/31 by wdjoyner

Almost 30 years ago this year, a former student Michael Fourte and I wrote a combinatorics paper (original paper, 1997) with the title above, eventually published in the now defunct Journal of Recreational Mathematics 31(2003)173–177.That paper was a pleasure to write, but was it correct?

With AI tackling open math problems left and right, I asked AI to review our paper and correct it, if any errors were found. In fact, I expected no errors but it turns out the main theorem was not as carefully stated as it should be, and some conjectural statements were not formulated in the best way (though our proofs were correct). A corrected version, made with the help of AI, can be found here: 2026 corrected version. An AI-written report on the paper with some possible directions for further research is here: 2026 AI-written report/review.

A dice game of the Arapaho Indians as a coin-tossing game

Posted on 2026/04/04 by wdjoyner

In Stewart Culin’s Games of the North American Indians, one of the games he describes is an Arapaho women’s basket dice game. The original game uses five two-sided dice-like pieces tossed in a basket. A simple mathematical way to understand it is to model it instead as a coin-tossing game with 2 nickels and 3 dimes.

This is not meant to say that the Arapaho players literally used coins. They did not. Rather, the coin model is a convenient combinatorial translation of the game. Two of the original pieces are of one type, and three are of another type. That makes the game mathematically equivalent to flipping two coins of one denomination and three of another denomination, then scoring according to the pattern of heads and tails.

A historical game made modern

Culin describes the game as using a small yucca-fiber bowl and five “dice” made of bone or plum stones. Two of the five must match each other in shape and marking, while the other three form another matching set.

The coin model

Suppose we replace the five original pieces by:

2 nickels
3 dimes

Let heads mean “marked side up” and tails mean “blank side up.” Then one throw of the Arapaho basket becomes one simultaneous flip of the 2 nickels and the 3 dimes.

Define:

N = the number of nickels showing heads, so N can be 0, 1, or 2
D = the number of dimes showing heads, so D can be 0, 1, 2, or 3

So each flip produces a pair (N, D). The important point is that the score depends on the distribution of heads between the nickels and dimes, not merely on the total number of heads. That is why this is not just a five-coin game with all coins interchangeable.

Scoring rule

A convenient mathematical version of the scoring is:

8 points if both nickels and all three dimes are heads: (2,3)
3 points if:
- both nickels are heads and the dimes are not all heads: (2,0), (2,1), or (2,2), or
- both nickels are tails and all three dimes are heads: (0,3)
1 point if:
- all five are tails: (0,0), or
- exactly one nickel is heads and all three dimes are heads: (1,3)
0 points in all other cases

If a flip scores, the player continues flipping. If a flip scores 0, the turn ends and the basket passes. As Culin says, a successful throw earns another throw, a failed throw passes, and a game is commonly played to 100 points.

The full outcome table

Nickels (N)	Dimes (D)	Probability	Score
0	0	1/32	1
0	1	3/32	0
0	2	3/32	0
0	3	1/32	3
1	0	2/32	0
1	1	6/32	0
1	2	6/32	0
1	3	2/32	1
2	0	1/32	3
2	1	3/32	3
2	2	3/32	3
2	3	1/32	8

Probability distribution of the score

Assuming the coin model uses fair independent coins, the probabilities are:

P(score = 8) = 1/32
P(score = 3) = 8/32 = 1/4
P(score = 1) = 3/32
P(score = 0) = 20/32 = 5/8

So the probability that a single flip scores anything at all is:

P(score > 0) = 12/32 = 3/8.

That means a player succeeds on 37.5% of flips and fails on 62.5% of flips.

Expected score

The expected score on a single flip is:

E(score) = 8(1/32) + 3(8/32) + 1(3/32) = 35/32 ≈ 1.094.

Because a player keeps flipping after a successful result, the expected score in one uninterrupted turn is larger. If we let T be the expected total score of one turn, then:

T = E(score) / (1 – P(score > 0)) = (35/32) / (1 – 3/8) = 7/4 = 1.75.

So in this idealized coin-tossing model, the average value of a single turn is 1.75 points.

References

Stewart Culin, Games of the North American Indians (1907), Bureau of American Ethnology. Internet Archive edition: https://archive.org/details/gamesofnorthamer00culirich
Text version of Culin’s work, including the discussion of dice games and the Arapaho women’s basket dice game: https://archive.org/stream/in.ernet.dli.2015.31459/2015.31459.Games-Of-The-North-American-Indians_djvu.txt
This blog post draft was prepared with assistance from ChatGPT by OpenAI: https://openai.com/chatgpt

The shell algorithm and a new book

Posted on 2026/01/06 by wdjoyner

A Peek Behind the Curtain

One feature of my forthcoming book with Caroline Melles, Exploring Graphs via Harmonic Morphisms, is its computational emphasis. Many of the examples and insights emerged not from pure contemplation, but from extensive experimentation using SageMath. This post gives a glimpse into the algorithmic machinery that made this exploration possible.

The fundamental problem I faced in generating examples was this: given two graphs Γ₁ and Γ₂, find all harmonic morphisms φ: Γ₂ → Γ₁. This approach is direct—a brute force algorithm that constructs all possible “color lists” (vertex labelings that encode potential morphisms) and tests each one for the harmonic property. Straightforward? Yes. Fast? Definitely not.

However, when the target graph Γ₁ is a path graph, one can do better. The “shell algorithm” exploits the geometry of distance in the source graph. Starting from a chosen vertex v₀, one builds outward through successive neighborhoods—vertices at distance 1, then 2, and so on—assigning colors constrained by distance from the starting point. At each stage, one checks necessary conditions before proceeding, pruning impossible branches early. The automorphism groups of both graphs then generate equivalent colorings, and after removing duplicates, one has a complete enumeration of the harmonic morphisms.

That’s what was done for various choices of small graphs, printing computational data to a file whose name used notation or terminology for the graphs $\Gamma_1$ and $\Gamma_2$ . Months of computer searches resulted in a number of conjectures that were used to shape the material in the book.

The Elevator Problem

Posted on 2025/11/02 by wdjoyner

You are on the bottom floor (floor 0, lets call it) of an apartment building with no basement. There are n elevators, which we index 1,2,…,n. Assume the elevators are on floors f1, f2, … , where fk > 0 is the floor elevator k is currently on, 1 <= k <= n. Assume you only like one of the elevators, elevator e.

The way the elevator logic works is this: When you press the elevator button, one closest to you ( = one on floor number min(fk, k>0)) is told to go to 0. If there is a tie then, of those on the same lowest floor, the elevator with the smallest index is told to go to 0.
Move: If you press the button and some other elevator than elevator e arrives, you can tell it to go to any floor you wish.
Taboo: You can press the elevator button if and only if no elevator is moving down.
Goal: You want to use elevator e (for some fixed e=1, 2, …, n).

Problem: Is there a finite sequence of moves that allows you to ride in elevator e?

My plan is to post the answer sometime later, but have fun with it!

In the works: a book “Exploring Graphs via Harmonic Morphisms”

Posted on 2025/10/07 by wdjoyner

Caroline Melles and I have been working for some years on a 2-volume book in graph theory which investigates harmonic morphisms. These are, roughly speaking, mappings from one graph to another that preserve locally harmonic functions on these graphs. Therefore, this topic fits into the general framework of harmonic analysis on graphs.

This post only concerns the first volume. The intent here is to mention some of the types of results we obtain. Of course, by no means is it intended to be a complete description.

The second volume will be summarized in a separate post.

Graphs in our book are unweighted and, unless stated otherwise, have no loops or multiple edges. The basic idea is this: in chapter 2 we classify harmonic morphisms using a criteria expressed as a matrix identity. For various graph-theoretical constructions (such as edge deletion or join or a graph product or …) that can be performed on a given graph Gamma, we pick a graph morphism associated to the construction (such as sending a vertex in the constructed graph to the given graph). That morphism is associated to a matrix (which we called the vertex map matrix in chapter 3 of our earlier book, Adventures in Graph Theory). When this matrix satisfies the above-mentioned matrix criteria then the associated morphism is harmonic.

Chapter 1 is on Graph Morphisms.

This chapter is devoted to background on graph morphisms and some of the methods we use to study them.

Roughly speaking, a morphism is a mapping between graphs that preserves incidence structure. After defining horizontal and vertical edges, vertical multiplicities, local horizontal multiplicities, it recalls well-known graph families like cycle graphs, path graphs, and complete graphs.
There are a few very useful degree identities. First, there is a fundamental formula relating vertex degrees to multiplicities under morphisms. There is also a formula for the degree
of the morphism in terms of vertical multiplicities and local horizontal multiplicities.
A topic threading through the book is that of matrix-theoretic methods. This first chapter introduces vertex map matrices and edge map matrices that encode morphisms. After establishing key matrix identities and products, reviews adjacency matrices and their spectra, with detailed analysis of cycle graph eigenvalues using Chebyshev polynomials and complex roots of unity.
It recalls signed and unsigned incidence matrices, with and without edge orientations, and establishes the fundamental Graph Homomorphism Identity relating incidence matrices to morphism matrices,
introduces Laplacian matrices as differences of degree and adjacency matrices, connecting to the incidence matrix framework.
Introduced graph blowup morphisms via a blowup construction where vertices are replaced by independent sets, creating natural homomorphisms with specific structural properties.
Some functorial properties of graph morphisms are established, such as how morphisms behave under graph constructions like subdivisions, smoothing, deletions, and substitutions.
The chapter ends with exercises and a chapter summary.

Chapter 2 on Harmonic Morphisms

This chapter is devoted to the basics of harmonic morphisms.

Introduces the core definition: a graph morphism is harmonic if local horizontal multiplicities are constant across edges incident to each vertex’s image.
Cycle space and cocycle space – Develops the algebraic framework using homology and cohomology of graphs. Covers Urakawa’s theorem on pullbacks of harmonic 1-forms and Baker-Norin results on divisors and Jacobians.
Matrix-theoretic methods – Establishes the fundamental matrix characterization: a morphism is harmonic iff there exists a diagonal multiplicity matrix satisfying specific adjacency matrix identities. Proves equivalence with an analogous Laplacian matrix identity and an analogous incidence matrix criteria.
The Riemann-Hurwitz formula – Presents the graph-theoretic analogue relating genera of graphs via harmonic morphisms, with matrix proof and applications to regular graphs.
Some functorial consequences – Demonstrates how harmonic morphisms interact with graph constructions like subdivision, edge substitution, leaf addition, and deletion. Shows these
operations preserve harmonicity under appropriate conditions.
The chapter ends with exercises and a chapter summary.

All harmonic morphisms from this graph to C4 are covers.

Fundamental Problem: Given a graph Gamma1, for which graphs Gamma2 is there a non-trivial harmonic morphism phi from Gamma2 to Gamma1?

Follow-up question: Can the number of such phi be counted?

Chapter 3 on Counting Problems

This chapter looks at various families, such as the path graphs. What is especially remarkable is that, as we will see, the problem of counting harmonic morphisms often boils down to solving certain recurrance relations, some of which arose (in a completely different context of course) in
the work of medieval mathematicians, both in Europe and in India.

Regarding harmonic morphisms between path graphs, we show how to construct and count the harmonic morphisms from longer path graphs to shorter ones.
Regarding harmonic morphisms between cycle graphs, we show how to construct and count the harmonic morphisms from larger cycle graphs (when they exist) to smaller ones. It turns out all such harmonic morphisms are necessarily covers.
Regarding harmonic morphisms between complete graphs, we show how to construct and count the harmonic morphisms from larger complete graphs (when they exist) to smaller ones.
Harmonic morphisms to P2 (arising from the Baker-Norin Theorem) can be counted.
Harmonic morphisms to P3 (the path graph with only 3 vertices) can be counted in special cases.
There are lots of open questions, such as which trees have a harmonic morphism to P3.
The chapter ends with exercises and a chapter summary.

Chapter 4 on Harmonic Quotient Morphisms

This chapter studies quotient graphs arising from group actions and from vertex partitions.

Quotient graphs from group actions. Harmonic actions and transitive actions are studied separately.
Quotient graphs from paritions. Orbit partitions and equitable partitions are studied.
As a nice application of harmonic morphisms with particularly nice structural properties, we consider multicovers and blowup graphs.
The last section provides explicit formulas for the eigenvalue spectra of harmonic blowups of bipartite graphs, connecting the eigenvalues of the source and target graphs through the blowup parameters. The main result is the Godsil-McKay Theorem.
The chapter ends with exercises and a chapter summary.

Chapter 5 on Graph Morphisms and Graph Products

Roughly speaking, a graph product of Gamma1 with Gamma2 is a graph Gamma3 = (V3, E3), where V3 = V1 x V2 is the Cartesian product and there is a rule for the edges E3 based on some conditions on the vertices. The graph products considered in this book are the disjunctive, Cartesian, tensor, lexicographic, and the strong products.

The most basic questions one wants answered are these:
is the projection pr1 : Gamma1 x Gamma2 to Gamma1 harmonic, and
is the projection pr2 : Gamma1 x Gamma2 to Gamma2 harmonic?
If they do turn out to be harmonic morphisms, we also want to know the vertical and horizontal multiplicities as well. If they do not turn out to be harmonic morphisms, we also want (if possible) to establish conditions on the graphs under which the projections are harmonic.

However, we want to not only consider products of graphs but also products of morphisms.
In this case, the most basic question one wants answered is this:
Given harmonic morphisms phi : Gamma2 to Gamma1 and phi’ : Gamma2′ to Gamma1′, is the
product phi x phi’ harmonic?

For example, we show that projection morphisms from tensor products are always harmonic with explicit horizontal multiplicity formulas.
Moreover, we prove that the tensor product of harmonic morphisms (without vertical edges) yields a harmonic morphism with horizontal multiplicity matrix given by the Kronecker product of the original multiplicity matrices.
If Gamma x Gamma’ is a lexicographical product then the projection onto the first factor, pr1, is a harmonic morphism. However, the projection onto the second factor is not in general.
We establish a connection between the balanced blowup graph and a lexicographical product. One corollary of this connection is that the blowdown graph agrees with the first projection of the product, so is a harmonic morphism.

Chapter 6 on More Products and Constructions

This chapter studies graph morphisms associated to Cartesian/strong/disjunctive products of graphs as well as joins and NEPS graphs.
For example, we show that projection morphisms from Cartesian products or from strong products are always harmonic with explicit horizontal multiplicity formulas.
Roughly speaking, one of the results states:
Given two m-quasi-multicovers phi from Gamma2 to Gamma1 and phi’ from Gamma2′ to Gamma1′, the Cartesian product phi x phi’ is also an m-quasi-multicover (hence harmonic).
Another result, roughly speaking, states:
Given two harmonic morphisms phi from Gamma2 to Gamma1 and phi’ from Gamma2′ to Gamma1′, the
strong product phi x phi’ is also harmonic.
Can one classify the graphs for which the disjunctive product projections pr1 or pr2 are graph morphisms?
For example, we show that if phi from Gamma2 to Gamma1 and phi’ from Gamma2′ to Gamma1′ are graph morphisms, then the associated product map from Gamma2 x Gamma2′ to Gamma1 x Gamma1′ (where x is the disjunctive product) is, in general, not a graph morphism.
Given two harmonic morphisms phi from Gamma2 to Gamma1 and phi’ from Gamma2′ to Gamma1′, the join morphism phi wedge phi’ is harmonic if and only if a certain technical condition is true.
A theorem due to Urakawa states that projection morphisms from a NEPS graph to one
of its factors are always harmonic. Moreover, we give explicit horizontal multiplicity formulas.
The chapter ends with exercises and a chapter summary.

Computations are supported throughout using SageMath and Mathematica. The plan is the publish the volume with Birkhauser. We thank the editors there, especially John Benedetto, for their encouragement and guidance.

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)

Yet Another Mathblog

Tag Archives: combinatorics