Another mathematician visits the ballpark – OPS

Posted on 2023/03/06 by wdjoyner

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.

Harmonic quotients of regular graphs – examples

Posted on 2023/01/06 by wdjoyner

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

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

Rankine’s “The Mathematician in Love”

Posted on 2022/05/26 by wdjoyner

The 1874 poem “The Mathematician in Love” by Scottish mechanical engineer William Rankine (in the book From Songs and Fables) has been published in many places (e.g., poetry.com, New Scientist and the scanned version is available at the internet archive. However, the mathematical equations Rankine presented at the end of his poem are only available in the scanned versions. As WordPress can render LaTeX, the poem quoted below includes those last few lines.

The Mathematician in Love
William J. M. Rankine

A mathematician fell madly in love
With a lady, young, handsome, and charming:
By angles and ratios harmonic he strove
Her curves and proportions all faultless to prove,
As he scrawled hieroglyphics alarming.

II.

He measured with care, from the ends of a base.
The arcs which her features subtended:
Then he framed transcendental equations, to trace
The flowing outlines of her figure and face.
And thought the result very splendid.

III.

He studied (since music has charms for the fair)
The theory of fiddles and whistles, —
Then composed, by acoustic equations, an air,
Which, when ’twas performed, made the lady’s long hair
Stand on end, like a porcupine’s bristles.

IV.

The lady loved dancing: – he therefore applied.
To the polka and waltz, an equation;
But when to rotate on his axis he tried.
His centre of gravity swayed to one side.
And he fell, by the earth’s gravitation.

No doubts of the fate of his suit made him pause.
For he proved, to his own satisfaction.
That the fair one returned his affection; – “because,
As every one knows, by mechanical laws,
Re-action is equal to action.”

VI.

“Let x denote beauty, – y manners well-bred, –
x, Fortune, – (this last is essential), –
Let L stand for love” – our philosopher said, –
“Then z is a function of x, y and 0,
Of the kind which is known as potential.”

VII.

“Now integrate L with respect to dt,
(t Standing for time and persuasion);
Then, between proper limits, ’tis easy to see,
The definite integral Marriage must be: —
(A very concise demonstration).”

VIII.

Said he – “If the wandering course of the moon
By Algebra can be predicted,
The female affections must yield to it soon” –
But the lady ran off with a dashing dragoon,
And left him amazed and afflicted.

End notes:
Equation referred to in Stanza VI.–
$L=\phi(x,y,z)= \int\int\int \frac{f(x,y,z)}{\sqrt{(x-\xi)^2+(y-\nu)^2+(z-\zeta)^2}} \, d\xi d\nu d\zeta$
Equation referred to in Stanza VII.–
$\int_{-\infty}^\infty L\, dt = M$

Let’s do the Landau shuffle

Posted on 2021/10/23 by wdjoyner

Here’s a shuffle I’ve not seen before:

Take an ordinary deck of 52 cards and place them, face up, in the following pattern:
Going from the top of the deck to the bottom, placing cards down left-to-right, put 13 cards in the top row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
11 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
then 9 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
then 7 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
then 5 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\$
then 3 cards in the next row:
$\Box\ \Box\ \Box\$
and finally, the remaining 4 cards in the last row:
$\Box\ \Box\ \Box\ \Box\$
Now, take the left-most card in each row and move it to the right of the others (effectively, this is a cyclic shift of that row of cards to the left).
Finally, reassemble the deck by reversing the order of the placement.

In memory of the great German mathematician Edmund Landau (1877-1938, see also this bio), I call this the Landau shuffle. As with any card shuffle, this shuffle permutes the original ordering of the cards. To restore the deck to it’s original ordering you must perform this shuffle exactly 180180 times. (By the way, this is called the order of the shuffle.) Yes, one hundred eighty thousand, one hundred and eighty times. Moreover, no other shuffle than this Landau shuffle will require more repetitions to restore the deck. So, in some sense, the Landau shuffle is the shuffle that most effectively rearranges the cards.

Left to right: Oswald Veblen, Edmund Landau, Harald Bohr. Location, photographer, date unknown.

Now suppose we have a deck of $n$ (distictly labeled) cards, where $n>2$ is an integer. The collection of all possible shuffles, or permutations, of this deck is denoted $S_n$ and called the symmetric group. The above discussion leads naturally to the following question(s).

Question: What is the largest possible order of a shuffle of this deck (and how do you construct it)?

This requires a tiny bit of group theory. You only need to know that any permutation of $n$ symbols (such as the card deck above) can be decomposed into a composition or product) of disjoint cycles. To compute the order of an element $g \in S_n$ , write that element $g$ in disjoint cycle notation. Denote the lengths of the disjoint cycles occurring in $g$ as $k_1, k_2, \dots , k_m$ , where $k_i>0$ are integers forming a partition of $n$ : $n = k_1 + k_2 +\dots + k_m$ . Then the order of $g$ is known to be given by $order(g) = LCM(k_1, k_2, ...., k_m)$ , where LCM denotes the least common multiple.

The Landau function $g(n)$ is the function that returns the maximum possible order of an element $g \in S_n$ . Landau introduced this function in a 1903 paper where he also proved the asymptotic relation $\lim_{n\to \infty} \frac{\ln(g(n))}{\sqrt{n\ln(n)}}=1$ .

Example: If $n=52$ then note $52 = 13+11+9+7+5+3+4$ and that $LCM(13,11,9,77,5,3,4)=180180$ .

Oddly, my favorite mathematical software program SageMath does not have an implementation of the Landau function, so we end with some SageMath code.

def landau_function(n):
    L = Partitions(n).list()
    lcms = [lcm(P) for P in L]
    return max(lcms)

Here is an example (the time is included to show this took about 2 seconds on my rather old mac laptop):

sage: time landau_function(52) CPU times: user 1.91 s, sys: 56.1 ms, total: 1.97 s Wall time: 1.97 s 180180

Coding Theory and Cryptography

Posted on 2021/10/11 by wdjoyner

This was once posted on my USNA webpage. Since I’ve retired, I’m going to repost it here.

Coding Theory and Cryptography:
From Enigma and Geheimschreiber to Quantum Theory
(David Joyner, ed.) Springer-Verlag, 2000.
ISBN 3-540-66336-3

Summary: These are the proceedings of the “Cryptoday” Conference on Coding Theory, Cryptography, and Number Theory held at the U. S. Naval Academy during October 25-26, 1998. This book concerns elementary and advanced aspects of coding theory and cryptography. The coding theory contributions deal mostly with algebraic coding theory. Some of these papers are expository, whereas others are the result of original research. The emphasis is on geometric Goppa codes, but there is also a paper on codes arising from combinatorial constructions. There are both, historical and mathematical papers on cryptography.
Several of the contributions on cryptography describe the work done by the British and their allies during World War II to crack the German and Japanese ciphers. Some mathematical aspects of the Enigma rotor machine and more recent research on quantum cryptography are described. Moreover, there are two papers concerned with the RSA cryptosystem and related number-theoretic issues.

Chapters

Reminiscences and Reflections of a Codebreaker, by Peter Hilton pdf
FISH and I, by W. T. Tutte pdf
Sturgeon, The FISH BP Never Really Caught, by Frode Weierud, pdf
ENIGMA and PURPLE: How the Allies Broke German and Japanese Codes During the War, by David A. Hatch pdf
The Geheimschreiber Secret, by Lars Ulfving, Frode Weierud pdf
The RSA Public Key Cryptosystem, by William P. Wardlaw pdf
Number Theory and Cryptography (using Maple), by John Cosgrave pdf
A Talk on Quantum Cryptography or How Alice Outwits Eve, by Samuel J. Lomonaco, Jr. pdf
The Rigidity Theorems of Hamada and Ohmori, Revisited, by T. S. Michael pdf
Counting Prime Divisors on Elliptic Curves and Multiplication in Finite Fields, by M. Amin Shokrollahi pdf,
On Cyclic MDS-Codes, by M. Amin Shokrollahi pdf
Computing Roots of Polynomials over Function Fields of Curves, by Shuhong Gao, M. Amin Shokrollahi pdf
Remarks on codes from modular curves: MAPLE applications, by David Joyner and Salahoddin Shokranian, pdf

For more cryptologic history, see the National Cryptologic Museum.

This is now out of print and will not be reprinted (as far as I know). The above pdf files are posted by written permission. I thank Springer-Verlag for this.

The truncated tetrahedron covers the tetrahedron

Posted on 2021/04/29 by wdjoyner

At first, you might think this is obvious – just “clip” off each corner of the tetrahedron $\Gamma_1$ to create the truncated tetrahedron $\Gamma_2$ (by essentially creating a triangle from each of these clipped corners – see below for the associated graph). Then just map each such triangle to the corresponding vertex of the tetrahedron. No, it’s not obvious because the map just described is not a covering. This post describes one way to think about how to construct any covering.

First, color the vertices of the tetrahedron in some way.

The coloring below corresponds to a harmonic morphism $\phi : \Gamma_2\to \Gamma_1$ :

All others are obtained from this by permuting the colors. They are all covers of $\Gamma_1 = K_4$ – with no vertical multiplicities and all horizontal multiplicities equal to 1. These 24 harmonic morphisms of $\Gamma_2\to\Gamma_1$ are all coverings and there are no other harmonic morphisms.

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).$

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)\}$ .

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.

Yet Another Mathblog

Category Archives: math