Another mathematician visits the ballpark – OPS

Yes, I more-or-less stole the above title from the 2004 Ken Ross book entitled A Mathematician at the Ballpark. Like that book, anyone familiar with middle-school (or junior high school) math, should have no problem with most of what we do here. However, I will try to go into baseball in more detail than the book did.

Paraphrasing slightly, I read somewhere the following facetious remark:

From a survey of 1000 random baseball fans 

across the nation,  183% of them hate math. 

If you are one of these 183%, then this series could be for you. Hopefully, even if you aren’t a baseball expert, but you would like to learn some baseball statistics, (now often called “sabermetrics”), these posts will help. I’m no expert myself, so we’ll learn together.

In this series of blog posts, each post will introduce a particular metric in baseball statistics as well as some of the math and baseball behind it. We illustrate all these notions using the Baltimore Orioles’ 2022 season.

This week we look at one of the most popular statistics you see on televised games: OPS or “On-base Plus Slugging,” which is short for on-base percentage plus slugging percentage. Don’t worry, we’ll explain all these terms as we go. 

On-base percentage

First, On-Base Percentage or OBP is a more recent version of On-Base Average or OBA (the same as OBP but the SF term is omitted). We define 

OBP = (H + BB + HBP)/(AB + BB + HBP + SF), 

where 

  • H is the number of Hits (the times the batter reaches base because of a batted, fair ball without error by the defense), 
  • BB is the number of Base-on-Balls (or walks), where a batter receives four pitches that the umpire calls balls, and is in turn awarded first base,
  • HBP, or Hit By Pitch, counts the times this hitter is touched by a pitch and awarded first base as a result, and 
  • SF is the number of Sacrifice Flies and AB the number of At-Bats, which are more complicated to carefully define.

The official scorer keeps track of all these numbers, and more, as the baseball game is played. We still have to define the expressions AB and SF.

First, SF, or Sacrifice Flies, counts the number of fly balls hit to the outfield for which both of the following are true:

  • this fly is caught for an out, and a baserunner scores after the catch (so there must be at most one hit at the time),
  • the fly is dropped, and a runner scores, if in the scorer’s judgment the runner could have scored after the catch had the fly ball been caught.

A sacrifice fly is only credited if a runner scores on the play. (By the way, this is a “recent” statistic, as they weren’t tabulated before 1954. Between 1876, when the major league baseball national league was born, and 1954 baseball analysts used the OBA instead.)

Second, AB, or At-Bats, counts those plate appearances that are not one of the following:

  • A walk,
  • being hit by a pitch,
  • a bunt (or Sacrifice Hit, SH),
  • a sacrifice fly,
  • interference (the catcher hitting the bat with his glove, for example), or
  • an obstruction (by the first baseman blocking the base path, for example).

Incidentally, the self-explanatory number Plate Appearances, or PA, can differ from AB by as much as 10%, mostly due to the number of walks that a batter can draw.

The main terms in the OBP expression are H and AB. So we naturally expect OBP to be approximately equal to the Batting Average, defined by

BA = H/AB,

For example, if we take the top 18 Orioles players and plot the BA vs the OBP, we get the following graph:

The line shown above is simply the line of best fit to visually indicate the correlation.

Example: As an example, let’s look at the Orioles’ All-Star center fielder,  Curtis Mullins, who had 672 plate appearances and 608 at bats, for a difference of 672 − 608 = 64. He had 1 bunt, 5 sacrifice flies, he was hit by a pitch 9 times, and walked 47 times. These add up to 62, so (using the above definition of AB) the number of times he was awarded 1st base due to interference or obstruction was 64 − 62 = 2.

Mullins’ H = 157 hits break down into 105 singles, 32 doubles, 4 triples, and 16 home runs.

Second, let’s add to these his 126 strikeouts, for a total of 157+126+64 = 347.

The remaining 608 − 347 = 261 plate appearances were pitches hit by Mullins, but either caught on the fly but a fielder or the ball landed fair and Mullins was thrown out at a base.

These account for all of Mullins’ plate appearances. Mullins has a batting average of BA = 157/608 = 0.258 and an on-base percentage of OBP = 0.318.

Slugging percentage

The slugging percentage, SLG, (SLuGging) is the total bases achieved on hits divided by at-bats:

SLG = TB/AB.

Here, TB or Total Bases, is the weighted sum

TB = 1B + 2*2B + 3*3B + 4*HR,

where

  • 1B is the number of “singles” (hits where the batter makes it to 1st Base),
  • 2B is the number of doubles,
  • 3B is the number of triples, and
  • HR denotes the number of Home Runs.

On-base Plus Slugging

With all these definitions under own belt, finally we are ready to compute “on-base plus slugging”, that is the on-base percentage plus slugging percentage:

OPS = OBP + SLG.

Example: Again, let’s consider Curtis Mullins. He had 1B = 105 singles, 2B = 32 doubles, 3B = 4 triples, and HR = 16 home runs, so his TB = 105+64+12+64 = 245. Therefore, his SLG = 245/608 = 0.403, so his on-base plus slugging is OPS = OBP + SLG = 0.318 + 0.403 = 0.721.

This finishes our discussion of OPS. I hope this helps explain it better. For more, see the OPS page at the MLB site or the wikipedia page for OPS

A table of small quartic graphs

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 to D_3 – examples

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.

  1. \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.)
  2. \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.)
  3. \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.)
  4. 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:
    3regular12d-D3-110302011111
    3regular12d-D3-103020111111
    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.
  5. \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)
  6. 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:
    3regular12f-D3-111103020111
    3regular12f-D3-111110302011
    And here is another plot of the last colored graph:
    3regular12f2-D3-111110302011
    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.
  7. \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)
  8. 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:
    3regular12h-D3-302010302010
    3regular12h-D3-333333302010
    3regular12h-D3-030201030201
    3regular12h-D3-103020111111
    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.
  9. (list under construction)

NCF Boolean functions

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

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

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-123210000cyclic9-123321000cyclic9-123332100cyclic9-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.

  1. \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.)
  2. \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.)
  3. \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.)
  4. \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)
  5. \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)
  6. \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)
  7. \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)
  8. (list under construction)

Harmonic morphisms to P_3 – examples

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

The path graph P_3

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

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

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

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

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

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

Example 1:

P3-C3-V

Example 2:
D3-2110

Example 3:
cyclic4-2101

Michael Reid’s Happy New Year Puzzles, 2018

Belatedly posted by permission of Michael Reid. Enjoy!

Here are some New Year’s puzzles to help start out 2018.

1. Arrange the ten digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 in the
expression a^b + c^d + e^f + g^h + i^j to make 2018.

2. (a) Express 2018 = p^q + r^s where p, q, r, s are primes.
(b) Express 2018 = p^q - r^s where p, q, r, s are primes.

3. (a) Is it possible to put the first 9 primes, 2, 3, 5, 7, 11, 13,
17, 19 and 23 into a 3×3 matrix that has determinant 2018?
(b) Is it possible to put the first 16 primes, 2, 3, 5, … , 53,
into a 4×4 matrix that has determinant 2018?

4. (a) Express 2018 = A / B using the fewest number of distinct
digits.
For example, the expression 7020622 / 3479 uses only seven
different digits. But it is possible to do better than this.
(b) Express 2018 = (A_1 \cdot A_2 \cdot ... \cdot A_m) / (B_1 \cdot B_2 \cdot ... \cdot B_n) using the fewest number of distinct digits.

Michael Reid’s Happy New Year Puzzle, 2017

Belatedly posted by permission of Michael Reid. Enjoy!

Here are some interesting puzzles to start the New Year; hopefully they are not too easy!

1. Express 2017 as a quotient of palindromes.

2. (a) Are there two positive integers whose sum is 2017 and whose product
is a palindrome?
(b) Are there two positive integers whose difference is 2017 and whose
product is a palindrome?

3. Is there a positive integer n such that both 2017 + n and
2017 n are palindromes?

4. What is the smallest possible sum of the decimal digits of 2017 n ,
where n is …
(a) … a positive integer?
(b) … a prime number?
(c) … a palindrome?

5. Consider the following two operations on a positive integer:
(i) replace a string of consecutive digits by its square,
(ii) if a string of consecutive digits is a perfect cube,
replace the string by its cube root.

Neither the string being replaced, nor its replacement, may have
have “leading zeros”. For example, from 31416 , we may change it to
319616 , by squaring the 14 . From 71253 , we may change it to
753 by taking the cube root of 125 .

(a) Starting from the number 2017 , what is the smallest number we
can reach with a sequence of these operations?
(b) What is the smallest number from which we can start, and reach
the number 2017 with a sequence of these operations?

6. Find a list of positive rational numbers, q_1 , q_2 , … , q_n
whose product is 1 , and whose sum is 2017 . Make your list as
short as possible.
Extra Credit: Prove that you have the shortest possible list.

Michael Reid’s Happy New Year Problems, 2020

Posted by permission of Michael Reid. Enjoy!

New Year’s Greetings!

Here are some fun puzzles to start the year.

1. Substitute the numbers 1, 2, … , 9 for the letters
a, b, … , i in the expression a^b + c^d + (e + f + g - h)^i
to get 2020.

2. Use the digits 1, 2, … , 9 in order, and any of the usual
arithmetic operations and parentheses to get a number that is
as close as possible to, but not exactly equal to 2020.

3. Express 2019/2020 as a sum of distinct Egyptian fractions,
i.e. 1 / n_1 + 1 / n_2 + ... + 1 / n_k for integers 0 < n_1 < n_2 < ...  n_k < 202049
(but 202049 is not square).

5. Make a 4×4 matrix of single-digit integers (0-9) with digits
2, 0, 2, 0 on the main diagonal, and having determinant 2020.
Is it possible to do it with a symmetric matrix?

If you liked this one, check out other puzzles ont this blog tagged with “Michael Reid”.