A footnote to Robert H. Mountjoy

Posted on 2020/08/27 by wdjoyner

In an earlier post titled Mathematical romantic? I mentioned some papers I inherited of one of my mathematical hero’s Andre Weil with his signature. In fact, I was fortunate enough to go to dinner with him once in Princeton in the mid-to-late 1980s – a very gentle, charming person with a deep love of mathematics. I remember he said he missed his wife, Eveline, who passed away in 1986. (They were married in 1937.)

All this is simply to motivate the question, why did I get these papers? First, as mentioned in the post, I was given Larry Goldstein‘s old office and he either was kind enough to gift me his old preprints or left them to be thrown away by the next inhabitant of his office. BTW, if you haven’t heard of him, Larry was a student of Shimura, when became a Gibbs Fellow at Yale, then went to the University of Maryland at COllege Park in 1969. He wrote lots of papers (and books) on number theory, eventually becoming a full professor, but eventually settled into computers and data science work. He left the University of Maryland about the time I arrived in the early 1980s to create some computer companies that he ran.

This motivates the question: How did Larry get these papers of Weil? I think Larry inherited them from Mountjoy (who died before Larry arrived at UMCP, but more on him later). This motivates the question, who is Mountjoy and how did he get them?

I’ve done some digging around the internet and here’s what I discovered.

The earliest mention I could find is when he was listed as a recipient of an NSF Fellowship in “Annual Report of the National Science Foundation: 1950-1953” under Chicago, Illinois, Mathematics, 1953. So he was a grad student at the University of Chicago in 1953. Andre Weil was there at the time. (He left sometime in 1958.) Mountjoy could have gotten the notes of Andre Weil then. Just before Weil left Chicago, Walter Lewis Baily arrived (in 1957, to be exact). This is important because in May 1965 the Notices of the AMS reported that reported:

Mountjoy, Robert Harbison
Abelian varieties attached to representations of discontinuous groups (S. Mac Lane and W. L. Baily)

(His thesis was published posthumously in American Journal of Mathematics Vol. 89 (1967)149-224.) This thesis is in a field studied by Weil and Baily but not Saunders.

But we’re getting ahead of ourselves. The 1962 issue of Maryland Magazine had this:

Mathematics Grant
A team of University of Maryland mathematics researchers have received a grant of $53,000 from the National Science Foundation to continue some technical investigations they started two years ago.
The mathematical study they are directing is entitled “Problems in Geometric Function Theory.” The project is under the direction of Dr. James Hummel. Dr. Mischael Zedek. and Prof. Robert H. Mountjoy, all of the Mathematics Department. They are assisted by four graduate-student researchists. The $53,000 grant is a renewal of an original grant which was made two years ago.

We know he was working at UMCP in 1962.

Here’s the sad news.

The newspaper Democrat and Chronicle, from Rochester, New York, on Wednesday, May 25, 1965 (Page 40) published the news that Robert H. Mountjoy “Died suddenly at Purcellville, VA, May 23, 1965”. I couldn’t read the rest (it’s behind a paywall but I could see that much). The next day, they published more: “Robert H. Mountjoy, son-in-law of Mr and Mrs Allen P Mills of Brighton, was killed in a traffic crash in Virgina. Mountjoy, about 30, a mathematics instructors at the University of Maryland, leaves a widow Sarah Mills Mountjoy and a 5-month old son Alexander, and his parents Mr and Mrs Lucius Mountjoy of Chicago.”

It’s so sad. The saying goes “May his memory be a blessing.” I never met him, but from what I’ve learned of Mountjoy, his memory is indeed a blessing.

The Riemann-Hurwitz formula for regular graphs

Posted on 2020/08/21 by wdjoyner

A little over 10 years ago, M. Baker and S. Norine (I’ve also seen this name spelled Norin) wrote a terrific paper on harmonic morphisms between simple, connected graphs (see “Harmonic morphisms and hyperelliptic graphs” – you can find a downloadable pdf on the internet of you google for it). Roughly speaking, a harmonic function on a graph is a function in the kernel of the graph Laplacian. A harmonic morphism between graphs is, roughly speaking, a map from one graph to another that preserves harmonic functions.

They proved quite a few interesting results but one of the most interesting, I think, is their graph-theoretic analog of the Riemann-Hurwitz formula. We define the genus of a simple connected graph $\Gamma = (V,E)$ to be

${\rm genus}(\Gamma) = |E| - |V | + 1.$

It represents the minimum number of edges that must be removed from the graph to make it into a tree (so, a tree has genus 0).

Riemann-Hurwitz formula (Baker and Norine): Let $\phi:\Gamma_2\to \Gamma_1$ be a harmonic morphism from a graph $\Gamma_2 = (V_2,E_2)$ to a graph $\Gamma_1 = (V_1, E_1)$ . Then

${\rm genus}(\Gamma_2)-1 = {\rm deg}(\phi)({\rm genus}(\Gamma_1)-1)+\sum_{x\in V_2} [m_\phi(x)+\frac{1}{2}\nu_\phi(x)-1].$

I’m not going to define them here but $m_\phi(x)$ denotes the horizontal multiplicity and $\nu_\phi(x)$ denotes the vertical multiplicity.

I simply want to record a very easy corollary to this, assuming $\Gamma_2 = (V_2,E_2)$ is $k_2$ -regular and $\Gamma_1 = (V_1, E_1)$ is $k_1$ -regular.

Corollary: Let $\Gamma_2 \rightarrow \Gamma_1$ be a non-trivial harmonic morphism from a connected $k_2$ -regular graph
to a connected $k_1$ -regular graph.
Then

$\sum_{x\in V_2}\nu_\phi(x) = k_2|V_2| - k_1|V_1|\deg (\phi).$

The number-theoretic side of J. Barkley Rosser

Posted on 2020/08/13 by wdjoyner

By chance, I ran across a reference to a paper of J Barkey Rosser and it brought back fond memories of days long ago when I would browse the stacks in the math dept library at the University of Washington in Seattle. I remember finding papers describing number-theoretic computations of Rosser and Schoenfeld. I knew nothing about Rosser. Was he a number theorist?

J. Barkley Rosser, taken at Math meeting in Denver

Here’s all I could glean from different sources on the internet:
J. Barkley Rosser was born in Jacksonville, Florida in 1907. He earned both his Bachelor of Science (1929) and his Master of Science (1931) from the University of Florida. Both degrees were in physics. He obtained his Ph.D. in mathematics (in fact, mathematical logic) from Princeton University in 1934, under the supervision of Alonso Church. After getting his Ph.D., Rosser taught at Princeton, Harvard, and Cornell and spent the latter part of his career at the University of Wisconsin-Madison. As a logician, Rosser is known for his part in the Church-Rosser Theorem and the Kleene–Rosser Paradox in lambda calculus. Moreover, he served as president of the Association for Symbolic Logic. As an applied mathematician, he served as president of the Society of Industrial and Applied Mathematics (otherwise known as SIAM). While at the University of Wisconsin-Madison, he served as the director of the U.S. Army Mathematics Research Center. He continued to lecture well into his late 70s, and passed away at his home in Madison in 1989. He has a son, J. Barkley Rosser Jr, who’s an economist at James Madison University.

What about Schoenfeld?

Lowell_Schoenfeld

Lowell Schoenfeld spent his early years in New York City, graduating Cum Laude from the College of the City of New York in 1940. He went on to MIT to earn a Master’s. He received his Ph.D. in 1944 from the University of Pennsylvania under the direction of Hans Rademacher. (During his years in graduate school, he seems to have worked for the Philadelphia Navy Yard as well, writing reports on aircraft navigational computers.) After positions at Temple University and Harvard, he moved to the University of Illinois, where he met his future wife. He met Josephine M. Mitchell when she was a tenured Associate Professor and he was an untenured Assistant Professor. After they married, the University would no longer allow Mitchell to teach, so the couple both resigned their positions and eventually settled at Pennsylvania State University. They spent about 10 years there but in 1968 the couple moved to the University of Buffalo, where they remained until their retirements in the 1980s.

As far as I can tell, these are the papers they wrote together, all in analytic number theory:

[1] Rosser, J. Barkley; Schoenfeld, Lowell. “Approximate formulas for some functions of prime numbers”. Illinois J. Math. 6 (1962), no. 1, 64–94.
[2] Rosser, J. Barkley; Schoenfeld, Lowell; J.M. Yohe. “Rigorous Computation and the Zeros of the Riemann Zeta-Function,” 1969
[3] Rosser, J. Barkley; Schoenfeld, Lowell. “Sharper Bounds for the Chebyshev Functions $\theta (x)$ and $\psi (x)$ ” Mathematics of Computation Vol. 29, No. 129 (Jan., 1975), pp. 243-269
[4] Rosser, J. Barkley; Schoenfeld, Lowell. “Approximation of the Riemann Zeta-Function” 1971.

I haven’t seen a copy of the papers [2] and [4] in years but I’m guessing these are what I looked at as a teenager in Seattle, years ago, wandering through the stacks at the UW.

Rosser also wrote papers on topics in recreational mathematics, such as magic squares. Two such papers were co-written with R.J. Walker from Cornell University, who’s more well-known for his textbook Algebraic Curves:

Rosser, Barkley; Walker, R. J. “The algebraic theory of diabolic magic squares,” Duke Math. J. 5 (1939), no. 4, 705–728
Rosser, Barkley; Walker, R. J. “On the transformation group for diabolic magic squares of order four,” Bull. Amer. Math. Soc. 44 (1938), no. 6, 416–420.

Diabolic magic squares, also called pan-diagonal magic squares, are $n\times n$ squares of integers $1, 2, ..., n^2$ whose rows all add to a constant C, whose columns all add to C, whose diagonals both add to C, and whose “broken diagonals” all add to C. An example was given by the German artist Albrecht Durer in the 1514 engraving called Melencolia I: (where C=34):

melencolia_i_1943.3.3522_diabolic-magic-square

I wish I knew more about this number-theoretic side of Rosser. He’s a very interesting mathematician.

A table of small quartic graphs

Posted on 2020/07/02 by wdjoyner

This page is modeled after the handy wikipedia page Table of simple cubic graphs of “small” connected 3-regular graphs, where by small I mean at most 11 vertices.

These graphs are obtained using the SageMath command graphs(n, [4]*n), where n = 5,6,7,… .

5 vertices: Let $V=\{0,1,2,3,4\}$ denote the vertex set. There is (up to isomorphism) exactly one 4-regular connected graphs on 5 vertices. By Ore’s Theorem, this graph is Hamiltonian. By Euler’s Theorem, it is Eulerian.
4reg5a: The only such 4-regular graph is the complete graph $\Gamma = K_5$ .
graph4reg5
We have

diameter = 1
girth = 3
If G denotes the automorphism group then G has cardinality 120 and is generated by (3,4), (2,3), (1,2), (0,1). (In this case, clearly, $G = S_5$ .)
edge set: $\{(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)\}$

6 vertices: Let $V=\{0,1,\dots, 5\}$ denote the vertex set. There is (up to isomorphism) exactly one 4-regular connected graphs on 6 vertices. By Ore’s Theorem, this graph is Hamiltonian. By Euler’s Theorem, it is Eulerian.
4reg6a: The first (and only) such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 2), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (2, 3), (2, 5), (3, 4), (3, 5), (4, 5)\}$ .
graph4reg6
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 48 and is generated by (2,4), (1,2)(4,5), (0,1)(3,5).

7 vertices: Let $V=\{0,1,\dots, 6\}$ denote the vertex set. There are (up to isomorphism) exactly 2 4-regular connected graphs on 7 vertices. By Ore’s Theorem, these graphs are Hamiltonian. By Euler’s Theorem, they are Eulerian.
4reg7a: The 1st such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 3), (0, 5), (0, 6), (1, 2), (1, 3), (1, 5), (2, 3), (2, 4), (2, 6), (3, 4), (4, 5), (4, 6), (5, 6)\}$ . This is an Eulerian, Hamiltonian (by Ore’s Theorem), vertex transitive (but not edge transitive) graph.
graph4reg7a
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 14 and is generated by (1,5)(2,4)(3,6), (0,1,3,2,4,6,5).

4reg7b: The 2nd such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 3), (0, 4), (0, 6), (1, 2), (1, 5), (1, 6), (2, 3), (2, 4), (2, 6), (3, 4), (3, 5), (4, 5), (5, 6)\}$ . This is an Eulerian, Hamiltonian graph (by Ore’s Theorem) which is neither vertex transitive nor edge transitive.
graph4reg7b
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 48 and is generated by (3,4), (2,5), (1,3)(4,6), (0,2)

8 vertices: Let $V=\{0,1,\dots, 7\}$ denote the vertex set. There are (up to isomorphism) exactly six 4-regular connected graphs on 8 vertices. By Ore’s Theorem, these graphs are Hamiltonian. By Euler’s Theorem, they are Eulerian.
4reg8a: The 1st such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 5), (0, 6), (0, 7), (1, 3), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 7), (3, 4), (3, 6), (4, 5), (4, 6), (5, 7)\}$ . This is vertex transitive but not edge transitive.
graph4reg8a
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 16 and is generated by $(1,7)(2,3)(5,6)$ and $(0,1)(2,4)(3,5)(6,7)$ .

4reg8b: The 2nd such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 5), (0, 6), (0, 7), (1, 3), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 7), (3, 4), (3, 6), (4, 5), (4, 6), (5, 7)\}$ . This is a vertex transitive (but not edge transitive) graph.
graph4reg8b
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 48 and is generated by $(2,3)(5,7)$ , $(1,3)(4,5)$ , $(0,1,3)(4,5,6)$ , $(0,4)(1,6)(2,5)(3,7)$ .

4reg8c: The 3rd such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 2), (0, 5), (0, 6), (1, 3), (1, 4), (1, 7), (2, 3), (2, 4), (2, 7), (3, 5), (3, 6), (4, 5), (4, 6), (5, 7), (6, 7)\}$ . This is a strongly regular (with “trivial” parameters (8, 4, 0, 4)), vertex transitive, edge transitive graph.
graph4reg8c
We have

diameter = 2
girth = 4
If G denotes the automorphism group then G has cardinality $1152=2^7\cdot 3^2$ and is generated by (5,6), (4,7), (3,4), (2,5), (1,2), (0,1)(2,3)(4,5)(6,7).

4reg8d: The 4th such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 2), (0, 4), (0, 6), (1, 3), (1, 5), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 6), (5, 7), (6, 7)\}$ . This graph is not vertex transitive, nor edge transitive.
graph4reg8d
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 16 and is generated by (3,5), (1,4), (0,2)(1,3)(4,5)(6,7), (0,6)(2,7).

4reg8e: The 5th such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 2), (0, 6), (0, 7), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 7), (3, 5), (3, 7), (4, 5), (4, 6), (5, 6), (6, 7)\}$ . This graph is not vertex transitive, nor edge transitive.
graph4reg8e
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 4 and is generated by (0,1)(2,4)(3,6)(5,7), (0,2)(1,4)(3,6).

4reg8f: The 6th (and last) such 4-regular graph is the bipartite graph $\Gamma=K_{4,4}$ having edge set: $\{(0, 1), (0, 2), (0, 6), (0, 7), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 5), (3, 7), (4, 5), (4, 6), (5, 6), (5, 7), (6, 7)\}$ . This graph is not vertex transitive, nor edge transitive.
graph4reg8f
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 12 and is generated by (3,4)(6,7), (1,2), (0,3)(5,6).

9 vertices: Let $V=\{0,1,\dots, 8\}$ denote the vertex set. There are (up to isomorphism) exactly 16 4-regular connected graphs on 9 vertices. Perhaps the most interesting of these is the strongly regular graph with parameters (9, 4, 1, 2) (also distance regular, as well as vertex- and edge-transitive). It has an automorphism group of cardinality 72, and is referred to as d4reg9-14 below.

Without going into details, it is possible to theoretically prove that there are no harmonic morphisms from any of these graphs to either the cycle graph $C_4$ or the complete graph $K_4$ . However, both d4reg9-3 and d4reg9-14 not only have harmonic morphisms to $C_3$ , they each may be regarded as a multicover of $C_3$ .

d4reg9-1
Gamma edges: E1 = [(0, 1), (0, 2), (0, 7), (0, 8), (1, 2), (1, 3), (1, 7), (2, 3), (2, 8), (3, 4), (3, 5), (4, 5), (4, 6), (4, 8), (5, 6), (5, 7), (6, 7), (6, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  12 
aut gp gens:  [(1,2)(4,5)(7,8), (0,1)(3,8)(5,6), (0,4)(1,5)(2,6)(3,7)]

d4reg9_1

d4reg9-2 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 3), (1, 7), (2, 3), (2, 5), (2, 8), (3, 4), (4, 5), (4, 6), (4, 8), (5, 6), (5, 7), (6, 7), (6, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  2 
aut gp gens:  [(0,5)(1,6)(2,8)(3,4)]

d4reg9_2

d4reg9-3 
Gamma edges: E1 = [(0, 1), (0, 2), (0, 7), (0, 8), (1, 2), (1, 3), (1, 4), (2, 3), (2, 8), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6), (5, 7), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  18 
aut gp gens:  [(1,7)(2,8)(3,6)(4,5), (0,1,4,6,8,2,3,5,7)]

d4reg9_3

d4reg9-4 
Gamma edges: E1 = [(0, 1), (0, 5), (0, 7), (0, 8), (1, 2), (1, 4), (1, 7), (2, 3), (2, 4), (2, 5), (3, 4), (3, 6), (3, 8), (4, 5), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  4 
aut gp gens:  [(2,4), (0,6)(1,3)(7,8)]

d4reg9_4

d4reg9-5 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 5), (0, 8), (1, 2), (1, 4), (1, 7), (2, 3), (2, 5), (2, 7), (3, 4), (3, 8), (4, 5), (4, 6), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  12 
aut gp gens:  [(1,5)(2,4)(6,7), (0,1)(2,3)(4,5)(7,8)]

d4reg9_5

d4reg9-6 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 5), (1, 6), (2, 3), (2, 5), (2, 6), (3, 4), (3, 8), (4, 5), (4, 7), (4, 8), (5, 6), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  8 
aut gp gens:  [(2,6)(3,7), (0,3)(1,2)(4,7)(5,6)]

d4reg9_6

d4reg9-7 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 4), (0, 8), (1, 2), (1, 3), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (4, 5), (4, 8), (5, 6), (5, 7), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  2 
aut gp gens:  [(0,3)(1,4)(2,8)(5,6)]

d4reg9_7

d4reg9-8 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 3), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (4, 5), (4, 6), (4, 8), (5, 6), (5, 8), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  2 
aut gp gens:  [(0,8)(1,5)(2,6)(3,4)]

d4reg9_8

d4reg9-9 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 6), (0, 8), (1, 2), (1, 3), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (4, 5), (4, 7), (4, 8), (5, 6), (5, 8), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  4 
aut gp gens:  [(5,7), (0,3)(2,6)(4,8)]

d4reg9_9

d4reg9-10 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 5), (0, 8), (1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 8), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  16 
aut gp gens:  [(2,6)(3,8), (1,5), (0,1)(2,3)(4,5)(6,8)]

d4reg9_10

d4reg9-11 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 5), (4, 5), (4, 8), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  8 
aut gp gens:  [(2,4)(7,8), (0,2)(3,7)(4,6)(5,8)]

d4reg9_11

d4reg9-12 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 6), (0, 8), (1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 8), (5, 6), (5, 8), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  18 
aut gp gens:  [(1,6)(2,5)(3,8)(4,7), (0,1,6)(2,7,3)(4,5,8), (0,2)(1,3)(5,8(6,7)]

d4reg9_12

d4reg9-13 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 4), (0, 8), (1, 2), (1, 5), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 8), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  8 
aut gp gens:  [(2,6)(3,8), (0,1)(2,3)(4,5)(6,8), (0,4)(1,5)]

d4reg9_13

d4reg9-14 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 4), (0, 8), (1, 2), (1, 5), (1, 8), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 6), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  72 
aut gp gens:  [(2,5)(3,4)(6,7), (1,3)(4,8)(5,7), (0,1)(2,3)(4,5)]

d4reg9_14

d4reg9-15 
Gamma edges: E1 = [(0, 1), (0, 4), (0, 6), (0, 8), (1, 2), (1, 3), (1, 5), (2, 3), (2, 4), (2, 7), (3, 4), (3, 7), (4, 5), (5, 6), (5, 8), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  32 
aut gp gens:  [(6,8), (2,3), (1,4), (0,1)(2,6)(3,8)(4,5)]

d4reg9_15

d4reg9-16 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 7), (3, 8), (4, 5), (4, 6), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  16 
aut gp gens:  [(7,8), (4,5), (0,1)(2,3)(4,7)(5,8), (0,2)(1,3)(4,7)(5,8)]

d4reg9_16

10 vertices: Let $V=\{0,1,\dots, 9\}$ denote the vertex set. There are (up to isomorphism) exactly 59 4-regular connected graphs on 10 vertices. One of these actually has an automorphism group of cardinality 1. According to SageMath: Only three of these are vertex transitive, two (of those 3) are symmetric (i.e., arc transitive), and only one (of those 2) is distance regular.

Example 1: The quartic, symmetric graph on 10 vertices that is not distance regular is depicted below. It has diameter 2, girth 4, chromatic number 3, and has an automorphism group of order 320 generated by $\{(7,8), (4,6), (1,2), (1,7)(2,8)(3,4)(5,6), (0,1,3,4,7)(2,5,6,8,9)\}$ .

d4reg10-46a

Example 2: The quartic, distance regular, symmetric graph on 10 vertices is depicted below. It has diameter 3, girth 4, chromatic number 2, and has an automorphism group of order 240 generated by $\{(2,5)(4,7), (2,8)(3,4), (1,5)(7,9), (0,1,3,2,7,6,9,8,4,5)\}$ .

d4reg10-51a

11 vertices: There are (up to isomorphism) exactly 265 4-regular connected graphs on 11 vertices. Only two of these are vertex transitive. None are distance regular or edge transitive.

Example 1: One of the vertex transitive graphs is depicted below. It has diameter 2, girth 4, chromatic number 3, and has an automorphism group of order 22 generated by $\{(1,10)(2,9)(3,4)(5,6)(7,8), (0,1,5,4,2,7,8,9,3,6,10)\}$ .

Example 2:The second vertex transitive graph is depicted below. It has diameter 3, girth 3, chromatic number 4, and has an automorphism group of order 22 generated by $\{(1,5)(2,7)(3,6)(4,8)(9,10), (0,1,3,2,4,10,9,8,7,6,5)\}$ .

Harmonic morphisms from cubic graphs of order 8 to a graph of order 4

Posted on 2020/06/08 by wdjoyner

There are five simple cubic graphs of order 8 (listed here) and there are 6 connected graphs of order 4 (listed here). But before we get started, I have a conjecture.

Let $\Gamma_1$ be a simple graph on n1 vertices, $\Gamma_2$ a simple graph on n2 vertices, and assume there is a harmonic morphism $\phi:\Gamma_1 \to \Gamma_2$ . Call an n1-tuple of “colors” $\{0,1,2,..., n2-1\}$ a harmonic color list (HCL) if it’s attached to a harmonic morphism in the usual way (the ith coordinate is j if $\phi$ sends vertex i of $\Gamma_1$ to vertex j of $\Gamma_2$ ). Let S be the set of all such HCLs. The automorphism group $G_1$ of $\Gamma_1$ acts on S (by permuting coordinates associated to the vertices of $\Gamma_1$ , as does the automorphism group $G_2$ of $\Gamma_2$ (by permuting the “colors” associated to the vertices of $\Gamma_2$ ). These actions commute. Clearly S decomposes as a disjoint union of distinct $G_1\times G_2$ orbits. The conjecture is that there is only one such orbit.

Note: Caroline Melles has disproven this conjecture. Still, the question of the number of orbits is an interesting one, IMHO.

Onto the topic of the post! The 6 connected graphs of order 4 are called P4 (the path graph), D3 (the star graph, also $K_{3,1}$ ), C4 (the cycle graph), K4 (the complete graph), Paw (C3 with a “tail”), and Diamond (K4 but missing an edge). All these terms are used on graphclasses.org. The results below were obtained using SageMath.

We start with the graph $\Gamma_1$ listed 1st on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [2, 2, -2, -2], 2). This graph $\Gamma_1$ has diameter 3, girth 3, and its automorphism group G is generated by (5,6), (1,2), (0,3)(4,7), (0,4)(1,5)(2,6)(3,7), $|G|=16$ . This graph is not vertex transitive. Its characteristic polynomial is $x^8 - 12x^6 - 8x^5 + 38x^4 + 48x^3 - 12x^2 - 40x - 15$ . Its edge connectivity and vertex connectivity are both 2. This graph has no non-trivial harmonic morphisms to D3 or P4 or C4 or Paw. However, there are 48 non-trivial harmonic morphisms to $\Gamma_2=K4$ . For example,
(the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3} and produces 24 total plots), and (again, the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3} and produces 24 total plots). There are 8 non-trivial harmonic morphisms to $\Gamma_2={\rm Diamond}$ . For example, and Here the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3}, while the automorphism group of the graph $\Gamma_1$ acts by permuting some of the coordinates, for example, it can swap the 5th and 6th coordinates.Next, we take for $\Gamma_1$ the graph listed 2nd on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [4, -2, 4, 2], 2). This graph $\Gamma_1$ has diameter 3, girth 3, and its automorphism group G is generated by (1,7)(2,6)(3,5), (0,4)(1,3)(5,7), $|G|=4$ (obviously too small to act transitively on the vertices). Its characteristic polynomial is $x^8 - 12x^6 - 4x^5 + 38x^4 + 16x^3 - 36x^2 - 12x + 9$ , its edge connectivity and vertex connectivity are both 3. This graph has no non-trivial harmonic morphisms to D3 or P4 or C4 or Paw or K4. However, it has 4 non-trivial harmonic morphisms to Diamond. They are:
Let $\Gamma_1$ denote the graph listed 3rd on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [2, 4, -2, 3, 3, 4, -3, -3], 1). This graph $\Gamma_1$ has diameter 2, girth 3, and its automorphism group G is generated by (4,6), (1,2)(3,5), (0,1)(5,7), $|G|=12$ . It does not act transitively on the vertices. Its characteristic polynomial is $x^8 - 12x^6 - 2x^5 + 36x^4 - 31x^2 + 12x$ and its edge connectivity and vertex connectivity are both 3.
This graph has no non-trivial harmonic morphisms to P4 or C4 or Paw or K4 or Diamond. However, it has 6 non-trivial harmonic morphisms to D3, for example,

The automorphism group of D3 (the symmetric group of degree 3) acts by permuting the colors {0,1,2,3} and so yields a total of 6=3! such harmonic color plots.Let $\Gamma_1$ denote the graph listed 4th on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [4, -3, 3, 4], 2). This example is especially interesting. Otherwise known as the “cube graph” $Q_3$ , this graph $\Gamma_1$ has diameter 3, girth 4, and its automorphism group G is generated by ((2,4)(5,7), (1,7)(4,6), (0,1,4,5)(2,3,6,7), $|G|=48$ . It is vertex transitive. Its characteristic polynomial is $x^8 - 12x^6 + 30x^4 - 28x^2 + 9$ and its edge connectivity and vertex connectivity are both 3.
This graph has no non-trivial harmonic morphisms to D3 or P4 or Paw. However, it has 24 non-trivial harmonic morphisms to C4, 24 non-trivial harmonic morphisms to K4, and 24 non-trivial harmonic morphisms to Diamond. An example of a non-trivial harmonic morphism to K4:

A few examples of a non-trivial harmonic morphism to Diamond:
and
A few examples of a non-trivial harmonic morphism to C4:

The automorphism group of C4 acts by permuting the colors {0,1,2,3} cyclically, while the automorphism group G acts by permuting coordinates. These yield more harmonic color plots.

Duursma zeta function of a graph

Posted on 2020/05/28 by wdjoyner

I’m going to start off with two big caveats:

This is not Duursma‘s definition, it’s mine.
I’m not convinced (yet?) that it’s a useful idea to examine such a zeta function.

So that’s your warning – you may be wasting your time reading this!

The Duursma zeta function of a linear block (error-correcting) code is due to Iwan Duursma and is a fascinating object of study. (More precisely, it’s defined for “formal” linear block codes, ie, defined via a weight enumerator polynomial with a suitable MacWilliams-like functional equation.) Sometimes it satisfies an analog of the Riemann hypothesis and sometimes it doesn’t. And sometimes that analog is still an open question.

Duursma zeta function of a code

Before we define the Duursma zeta function of a graph, we introduce the Duursma zeta function of a code.

Let $C$ be an $[n,k,d]_q$ code, ie a linear code over $GF(q)$ of length $n$ , dimension $k$ , and minimum distance $d$ . In general, if $C$ is an $[n,k,d]_q$ -code then we use $[n,k^\perp,d^\perp]_q$ for the parameters of the dual code, $C^\perp$ . It is a consequence of Singleton’s bound that $n+2-d-d^\perp\geq$ , with equality when $C$ is an MDS code. Motivated by analogies with local class field theory, in [Du] Iwan Duursma introduced the (Duursma) zeta function $\zeta=\zeta_C$ :

$\zeta_C(T)=\frac{P(T)}{(1-T)(1-qT)},$
where $P(T)=P_C(T)$ is a polynomial of degree $n+2-d-d^\perp$ , called the zeta polynomial of $C$ . We next sketch the definition of the zeta polynomial.

If $C^\perp$ denotes the dual code of $C$ , with parameters $[n,n-k,d^\perp]$ then the MacWilliams identity relates the weight enumerator $A_{C^\perp}$ of $C^\perp$ to the weight enumerator $A_{C}$ of $C$ :

$A_{C^\perp}(x,y) = |C|^{-1}A_C(x+(q-1)y,x-y).$
A polynomial $P(T)=P_C(T)$ for which

$\frac{(xT+(1-T)y)^n}{(1-T)(1-qT)}P(T)=\dots +\frac{A_C(x,y)-x^n}{q-1}T^{n-d}+\dots \ .$
is a (Duursma) zeta polynomial of $C$ .

Theorem (Duursma): If $C$ be an $[n,k,d]_q$ code with $d\geq 2$ and $d^\perp\geq 2$ then the Duursma zeta polynomial $P=P_C$ exists and is unique.

See the papers of Duursma for interesting properties and conjectures.

Duursma zeta function of a graph

Let $\Gamma=(V,E)$ be a graph having $|V(\Gamma)|$ vertices and $|E(\Gamma)|$ edges. We define the zeta function of $\Gamma$ via the Duursma zeta function of the binary linear code defined by the cycle space of $\Gamma$ .

Theorem (see [DKR], [HB], [JV]): The binary code $B=B_\Gamma$ generated by the rows of the incidence matrix of $\Gamma$ is the cocycle space of $\Gamma$ over $GF(2)$ , and the dual code $B^\perp$ is the cycle space $Z=Z_\Gamma$ of $\Gamma$ :

$B_\Gamma^\perp = Z_\Gamma.$
Moreover,
(a) the length of $B_\Gamma$ is $|E|$ , dimension of $B_\Gamma$ is $|V|-1$ , and the minimum distance of $B_\Gamma$ is the edge-connectivity of $\Gamma$ ,
(b) length of $Z_\Gamma$ is $|E|$ , dimension of $Z_\Gamma$ is $|E|-|V|+1$ , and the minimum distance of $Z_\Gamma$ is the girth of $\Gamma$ .

Call $Z_\Gamma$ the cycle code and $B_\Gamma$ the cocycle code.

Finally, we can introduce the (Duursma) zeta function $\Gamma$ :

$\zeta_\Gamma(T)=\zeta_{Z_\Gamma} =\frac{P(T)}{(1-T)(1-qT)},$
where $P=P_\Gamma=P_{Z_\Gamma}$ is the Duursma polynomial of $\Gamma$ .

Example: Using SageMath, when $\Gamma = W_5$ , the wheel graph on 5 vertices, we have

$P_\Gamma(T) = \frac{2}{7}T^4 + \frac{2}{7}T^3 + \frac{3}{14}T^2 + \frac{1}{7}T + \frac{1}{14}.$
All its zeros are of absolute value $1/\sqrt{2}$ .

References

[Du] I. Duursma, Combinatorics of the two-variable zeta function, in Finite fields and applications, 109–136, Lecture Notes in Comput. Sci., 2948, Springer, Berlin, 2004.

[DKR] P. Dankelmann, J. Key, B. Rodrigues, Codes from incidence matrices of graphs, Designs, Codes and Cryptography 68 (2013) 373-393.

[HB] S. Hakimi and J. Bredeson, Graph theoretic error-correcting codes, IEEE Trans. Info. Theory 14(1968)584-591.

[JV] D. Jungnickel and S. Vanstone, Graphical codes revisited, IEEE Trans. Info. Theory 43(1997)136-146.

Harmonic morphisms to D_3 – examples

Posted on 2020/05/01 by wdjoyner

This post expands on a previous post and gives more examples of harmonic morphisms to the tree $\Gamma_2=D_3$ . This graph is also called a star graph $Star_3$ on 3+1=4 vertices, or the bipartite graph $K_{1,3}$ .
D3-0123

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=D_3$ sends the red vertices in $\Gamma_1$ to the red vertex of $\Gamma_2=D_3$ (we let 3 be the numerical notation for the color red), the blue vertices in $\Gamma_1$ to the blue vertex of $\Gamma_2=D_3$ (we let 2 be the numerical notation for the color blue), the green vertices in $\Gamma_1$ to the green vertex of $\Gamma_2=D_3$ (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=D_3$ (we let 0 be the numerical notation for the color white).

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=D_3$ ), this remark has the following consequence: since in $D_3$ the green vertex is not adjacent to the blue or red vertex, none of the harmonic colored graphs below can have a green vertex adjacent to a blue or red vertex. In fact, any colored vertex can only be connected to a white vertex or a vertex of like color.

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

Example 1: There are only the 4 trivial harmonic morphisms $Star_4 \to D_3$ , plus the “obvious” ones obtained from that below and those induced by permutations of the vertices:
Star4-D3-00321 .

My guess is that the harmonic morphisms $Star_5\to D_3$ can be described in a similar manner. Likewise for the higher $Star_n$ graphs. Given a star graph $\Gamma$ with a harmonic morphism to $D_3$ , a leaf (connected to the center vertex 0) can be added to $\Gamma$ and preserve “harmonicity” if its degree 1 vertex is colored 0. You can try to “collapse” such leafs, without ruining the harmonicity property.

Example 2: For graphs like $\Gamma_1=$
C3LeafLeafLeaf-D3-000321
there are only the 4 trivial harmonic morphisms $\Gamma_1 \to D_3$ , plus the “obvious” ones obtained from that above and those induced by permutations of the vertices with a non-zero color.

Example 2.5: Likewise, for graphs like $\Gamma_1=$
3C3-D3-0332211
there are only the 4 trivial harmonic morphisms $\Gamma_1 \to D_3$ , plus the “obvious” ones obtained from that above and those induced by permutations of the vertices with a non-zero color.

Example 3: This is really a non-example. There are no harmonic morphisms from the (3-dimensional) cube graph (whose vertices are those of the unit cube) to $D_3$ .
More generally, take two copies of a cyclic graph on n vertices, $C_n$ , one hovering over the other. Now, connect each vertex of the top copy to the corresponding vertex of the bottom copy. This is a cubic graph that can be visualized as a “thick” regular polygon. (The cube graph is the case $n=4$ .) I conjecture that there is no harmonic morphism from such a graph to $D_3$ .

Example 4: There are 30 non-trivial harmonic morphisms $\Gamma_1 \to D_3$ for the Peterson graph (the last of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page). Here is an example:
petersen-D3-0330120021
Another interesting fact is that this graph has an automorphism group (isomorphic to the symmetric group on 5 letters) which acts transitively on the vertices.

Example 5: There are 12 non-trivial harmonic morphisms $\Gamma_1=K_{3,3} \to D_3$ for the complete bipartite (“utility”) graph $K_{3,3}$ . They are all obtained from either
K_3_3-D3-321000
or
K_3_3-D3-000231
by permutations of the vertices with a non-zero color (3!+3!=12).

Example 6: There are 6 non-trivial harmonic morphisms $\Gamma_1 \to D_3$ for the cubic graph $\Gamma_1=(V,E)$ , where $V=\{0,1,\dots, 9\}$ and $E = \{(0, 3), (0, 4), (0, 6), (1, 2), (1, 5), (1, 9), (2, 3), (2, 7), (3, 6), (4, 5), (4, 9), (5, 8), (6, 7), (7, 8), (8, 9)\}$ . This graph has diameter 3, girth 3, and edge-connectivity 3. It’s automorphism group is size 4, generated by (5,9) and (1,8)(2,7)(3,6). The harmonic morphisms are all obtained from
random3regular10e-D3-1011031102
by permutations of the vertices with a non-zero color (3!=6). This graph might be hard to visualize but it is isomorphic to the simple cubic graph having LCF notation [−4, 3, 3, 5, −3, −3, 4, 2, 5, −2]:
random3regular10e2
which has a nice picture. This is the ninth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page.

Example 7: (a) The first of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10f
This graph has diameter 5, automorphism group generated by (7,8), (6,9), (3,4), (2,5), (0,1)(2,6)(3,7)(4,8)(5,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(b) The second of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10g
This graph has diameter 4, girth 3, automorphism group generated by (7,8), (0,5)(1,2)(6,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(c) The third of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10h
This graph has diameter 3, girth 3, automorphism group generated by (4,5), (0,1)(8,9), (0,8)(1,9)(2,7)(3,6). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 8: The fourth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10i
This graph has diameter 3, girth 3, automorphism group generated by (4,6), (3,5), (1,8)(2,7)(3,4)(5,6), (0,9). There are 12 non-trivial harmonic morphisms $\Gamma_1\to D_3$ . For example,
3regular10i-D3-2220301022
and the remaining (3!=6 total) colorings obtained by permutating the non-zero colors. Another example is
3regular10i-D3-1103020111
and the remaining (3!=6 total) colorings obtained by permutating the non-zero colors.

Example 9: (a) The fifth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10j
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2,2,-2,-2,5],2) There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(b) The sixth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10k
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2,3,-2,5,-3],2) There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 10: The seventh of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10l-D3-3330222010
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2,3,-2,5,-3],2). Its automorphism group is order 12, generated by (1,2)(3,7)(4,6), (0,1)(5,6)(7,9), (0,4)(1,6)(2,5)(3,9). There are 6 non-trivial harmonic morphisms $\Gamma_1\to D_3$ , each obtained from the one above by permuting the non-zero colors.

Example 11: The eighth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10m
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, 3, 5, -4, -3, 5, 2, 5, -2, 4],1). Its automorphism group is order 2, generated by (0,3)(1,4)(2,5)(6,7). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 12: (a) The tenth (recall the 9th was mentioned above) of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10o
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[3, -3, 5, -3, 2, 4, -2, 5, 3, -4],1). Its automorphism group is order 6, generated by (2,8)(3,9)(4,5), (0,2)(5,6)(7,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(b) The 11th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10p
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[-4, 4, 2, 5, -2],2). Its automorphism group is order 4, generated by (0,1)(2,9)(3,8)(4,7)(5,6), (0,5)(1,6)(2,7)(3,8)(4,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(c) The 12th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10q
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -2, 2, 4, -2, 5, 2, -4, -2, 2],1). Its automorphism group is order 6, generated by (1,9)(2,8)(3,7)(4,6), (0,4,6)(1,3,8)(2,7,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(d) The 13th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10r
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2, 5, -2, 5, 5],2). Its automorphism group is order 8, generated by (4,8)(5,7), (0,2)(3,9), (0,5)(1,6)(2,7)(3,8)(4,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 13: The 14th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10s-D3-2033020110
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. Another harmonic morphism $\Gamma_1\to D_3$ is depicted as:
3regular10s-D3-0302222201
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. And another harmonic morphism $\Gamma_1\to D_3$ is depicted as:
3regular10s-D3-1110302011
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -3, -3, 3, 3],2). Its automorphism group is 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 a total of 18=3!+3!+3! non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 14: The 15th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10t-D3-2033020110
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -4, 4, -4, 4],2). Its automorphism group is order 8, generated by (2,7)(3,8), (1,9)(2,3)(4,6)(7,8), (0,5)(1,4)(2,3)(6,9)(7,8). There are a total of 6=3! non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 15: (a) The 16th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10u
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -4, 4, 5, 5],2). Its automorphism group is order 4, generated by (0,3)(1,2)(4,9)(5,8)(6,7), (0,5)(1,6)(2,7)(3,8)(4,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(b) The 17th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10v
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, 5, -3, 5, 3],2). Its automorphism group is order 20, generated by (2,6)(3,7)(4,8)(5,9), (0,1)(2,5)(3,4)(6,9)(7,8), (0,2)(1,9)(3,5)(6,8). This group acts transitively on the vertices. There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(c) The 18th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10w
This is an example of a “thick polygon” graph, already mentioned in Example 3 above. Its SageMath command is Gamma1 = graphs.LCFGraph(10,[-4, 4, -3, 5, 3],2). Its automorphism group is order 20, generated by (2,5)(3,4)(6,9)(7,8), (0,1)(2,6)(3,7)(4,8)(5,9), (0,2)(1,9)(3,6)(4,7)(5,8). This group acts transitively on the vertices. There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(d) The 19th in the list of 19 is the Petersen graph, already in Example 4 above.

We now consider some examples of the cubic graphs having 12 vertices. According to the House of Graphs there are 109 of these, but we use the list on this wikipedia page.

Example 16: 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 D_3$ 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.)
This example has 12 non-trivial harmonic morphisms.
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.) We show two such morphisms:

The other non-trivial harmonic morphisms are obtained by permuting the non-zero colors. There are 3!=6 for each graph above, so the total number of harmonic morphisms (including the trivial ones) is 6+6+4=16.
$\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)
This example has 12 non-trivial harmonic morphisms. $\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)\}$ . (This only differs by one edge from the one above.)
SageMath command:
Gamma1 = graphs.LCFGraph(12, [3, -2, -4, -3, 3, 3, 3, -3, -3, -3, 4, 2], 1)
We show two such morphisms:

And here is another plot of the last colored graph:

The other non-trivial harmonic morphisms are obtained by permuting the non-zero colors. There are 3!=6 for each graph above, so the total number of harmonic morphisms (including the trivial ones) is 6+6+4=16.
$\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)
This example has 48 non-trivial harmonic morphisms. $\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)
This example is also interesting as it has a large number of automorphisms – its automorphism group is size 64, generated by (8,10), (7,9), (2,4), (1,3), (0,5)(1,2)(3,4)(6,11)(7,8)(9,10), (0,6)(1,7)(2,8)(3,9)(4,10)(5,11). Here are examples of some of the harmonic morphisms using vertex-colored graphs:

I think all the other non-trivial harmonic morphisms are obtained by (a) permuting the non-zero colors, or (b) applying a element of the automorphism group of the graph.
(list under construction)

NCF Boolean functions

Posted on 2020/04/20 by wdjoyner

I recently learned about a new class of seemingly complicated, but in fact very simple functions which are called by several names, but perhaps most commonly as NCF Boolean functions (NCF is an abbreviation for “nested canalyzing function,” a term used by mathematical biologists). These functions were independently introduced by theoretical computer scientists in the 1960s using the term unate cascade functions. As described in [JRL2007] and [LAMAL2013], these functions have applications in a variety of scientific fields. This post describes these functions.

A Boolean function of n variables is simply a function $f:GF(2)^n\to GF(2)$ . Denote the $GF(2)$ -vector space of such functions by $B(n)$ . We write an element of this space as $f(x_1,x_2,\dots,x_n)$ , where the variables $x_i$ will be called coordinate variables. Let
$Res_{x_i=a}:B(n)\to B(n-1)$
denote the restriction map sending $f(x_1,x_2,\dots,x_n)$ to $f(x_1,x_2,\dots,x_{i-1},a,x_{i+1},\dots, x_n)$ . In this post, the cosets
$H_{i,a,n}=\{x=(x_1,x_2,\dots,x_n) \in GF(2)^n\ |\ x_i=a\}$
will be called coordinate hyperplanes ( $a \in GF(2), 1\leq i\leq n$ ). A function in $B(n)$ which is constant along some coordinate hyperplane is called canalyzing. An NCF function is a function $f\in B(n)$ which (a) is constant along some coordinate hyperplane $H_{i_1,a_1,n}$ , (b) whose restriction $f_1 = Res_{x_{i_1}=a_1}(f)\in B(n-1)$ is constant along some coordinate hyperplane $H_{i_2,a_2,n-1}\subset GF(2)^{n-1}$ , (c) whose restriction $f_2 = Res_{x_{i_2}=a_2}(f_1)\in B(n-2)$ is constant along some coordinate hyperplane $H_{i_2,a_2,n-2}\subset GF(2)^{n-2}$ , (d) and so on. This “nested” inductive definition might seem complicated, but to a computer it’s pretty simple and, to boot, it requires little memory to store.

If $1\leq i\leq n$ and $x=(x_1,x_2,\dots,x_n) \in GF(2)^n$ then let $x^i\in GF(2)^n$ denote the vector whose i-th coordinate is flipped (bitwise). The sensitivity of $f\in B(n)$ at $x$ is
$s(f,x) = |\{i\ |\ 1\leq i\leq n, f(x)\not= f(x^i)\}|$ . Roughly speaking, it’s the number of single-bit changes in $x$ that change the value of $f(x)$ . The (maximum) sensitivity is the quantity
$s(f)=max_x s(f,x).$ The block sensitivity is defined similarly, but you allow blocks of indices of coordinates to by flipped bitwise, as opposed to only one. It’s possible to

compute the sensitivity of any NCF function,
show the block sensitivity is equal to the sensitivity,
compute the cardinality of the set of all monotone NCF functions.

For details, see for example Li and Adeyeye [LA2012].

REFERENCES
[JRL2007] A.S. Jarrah, B. Raposa, R. Laubenbachera, “Nested Canalyzing, Unate Cascade, and Polynomial Functions,” Physica D. 2007 Sep 15; 233(2): 167–174.

[LA2012] Y. Li, J.O. Adeyeye, “Sensitivity and block sensitivity of nested canalyzing function,” ArXiV 2012 preprint. (A version of this paper was published later in Theoretical Comp. Sci.)

[LAMAL2013] Y. Li, J.O. Adeyeye, D. Murrugarra, B. Aguilar, R. Laubenbacher, “Boolean nested canalizing functions: a comprehensive analysis,” ArXiV, 2013 preprint.

Expected maximums and fun with Faulhaber’s formula

Posted on 2020/03/28 by wdjoyner

A recent Futility Closet post inspired this one. There, Greg Ross mentioned a 2020 paper by P Sullivan titled “Is the Last Banana Game Fair?” in Mathematics Teacher. (BTW, it’s behind a paywall and I haven’t seen that paper).

Suppose Alice and Bob don’t want to share a banana. They each have a fair 6-sided die to throw. To decide who gets the banana, each of them rolls their die. If the largest number rolled is a 1, 2, 3, or 4, then Alice wins the banana. If the largest number rolled is a 5 or 6, then Bob wins. This is the last banana game. In this post, I’m not going to discuss the last banana game specifically, but instead look at a related question.

Let’s define things more generally. Let $I_n=\{1,2,...,n\}$ , let $X,Y$ be two independent, uniform random variables taken from $I_n$ , and let $Z=max(X,Y)$ . The last banana game concerns the case $n=6$ . Here, I’m interested in investigating the question: What is $E(Z)$ ?

Computing this isn’t hard. By definition of independent and max, we have
$P(Z\leq z)=P(X\leq z)P(Y\leq z)$ .
Since $P(X\leq z)=P(Y\leq z)={\frac{z}{n}}$ , we have
$P(Z\leq z)={\frac{z^2}{n^2}}$ .
The expected value of $Z$ is defined as $\sum kP(Z=k)$ , but there’s a handy-dandy formula we can use instead:
$E(Z)=\sum_{k=0}^{n-1} P(Z>k)=\sum_{k=0}^{n-1}[1-P(Z\leq k)]$ .
Now we use the previous computation to get
$E(Z)=n-{\frac{1}{n^2}}\sum_{k=1}^{n-1}k^2=n-{\frac{1}{n^2}}{\frac{(n-1)n}{6}}={\frac{2}{3}}n+{\frac{1}{2}}-{\frac{1}{6n}}.$
This solves the problem as stated. But this method generalizes in a straightforward way to selecting m independent r.v.s in $I_n$ , so let’s keep going.

First, let’s pause for some background and history. Notice how, in the last step above, we needed to know the formula for the sum of the squares of the first n consecutive positive integers? When we generalize this to selecting m integers, we need to know the formula for the sum of the m-th powers of the first n consecutive positive integers. This leads to the following topic.

Faulhaber polynomials are, for this post (apparently the terminology is not standardized) the sequence of polynomials $F_m(n)$ of degree m+1 in the variable n that gives the value of the sum of the m-th powers of the first n consecutive positive integers:

$\sum_{k=1}^{n} k^m=F_m(n)$ .

(It is not immediately obvious that they exist for all integers $m\geq 1$ but they do and Faulhaber’s results establish this existence.) These polynomials were discovered by (German) mathematician Johann Faulhaber in the early 1600s, over 400 years ago. He computed them for “small” values of m and also discovered a sort of recursive formula relating $F_{2\ell +1}(n)$ to $F_{2\ell}(n)$ . It was about 100 years later, in the early 1700s, that (Swiss) mathematician Jacob Bernoulli, who referenced Faulhaber, gave an explicit formula for these polynomials in terms of the now-famous Bernoulli numbers. Incidentally, Bernoulli numbers were discovered independently around the same time by (Japanese) mathematician Seki Takakazu. Concerning the Faulhaber polys, we have
$F_1(n)={\frac{n(n+1)}{2}}$ ,
$F_2(n)={\frac{n(n+1)(2n+1)}{6}}$ ,
and in general,
$F_m(n)={\frac{n^{m+1}}{m+1}}+{\frac{n^m}{2}}+$ lower order terms.

With this background aside, we return to the main topic of this post. Let $I_n=\{1,2,...,n\}$ , let $X_1,X_2,...,x_m$ be m independent, uniform random variables taken from $I_n$ , and let $Z=max(X_1,X_2,...,X_m)$ . Again we ask: What is $E(Z)$ ? The above computation in the $m=2$ case generalizes to:

$E(Z)=n-{\frac{1}{n^m}}\sum_{k=1}^{n-1}k^m=n-{\frac{1}{n^m}}F_m(n-1).$

For m fixed and n “sufficiently large”, we have

$E(Z)={\frac{m}{m+1}}n+O(1).$

I find this to be an intuitively satisfying result. The max of a bunch of independently chosen integers taken from $I_n$ should get closer and closer to n as (the fixed) m gets larger and larger.

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

Author Archives: wdjoyner