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:


Example 2:

Example 3:

Differential equations and SageMath

The files below were on my teaching page when I was a college teacher. Since I retired, they disappeared. Samuel Lelièvre found an archived copy on the web, so I’m posting them here.

The files are licensed under the Attribution-ShareAlike Creative Commons license.

  1. Partial fractions handout, pdf
  2. Introduction to matrix determinants handout, pdf
  3. Impulse-response handout, pdf
  4. Introduction to ODEs, pdf
  5. Initial value problems, pdf
  6. Existence and uniqueness, pdf
  7. Euler’s method for numerically approximating solutions to DEs, pdf.
    Includes both 1st order DE case (with Euler and improved Euler) and higher order DE and systems of DEs cases, without improved Euler.
  8. Direction fields and isoclines, pdf
  9. 1st order ODEs, separable and linear cases, pdf
  10. A falling body problem in Newtonian mechanics, pdf
  11. A mixing problem, pdf
  12. Linear ODEs, I, pdf
  13. Linear ODEs, II, pdf
  14. Undetermined coefficients for non-homogeneous 2nd order constant coefficient ODEs, pdf
  15. Variation of parameters for non-homogeneous 2nd order constant coefficient ODEs, pdf.
  16. Annihilator method for non-homogeneous 2nd order constant coefficient ODEs, pdf.
    I found students preferred (the more-or-less equivalent) undetermined coefficient method, so didn’t put much effort into these notes.
  17. Springs, I, pdf
  18. Springs, II, pdf
  19. Springs, III, pdf
  20. LRC circuits, pdf
  21. Power series methods, I, pdf
  22. Power series methods, II, pdf
  23. Introduction to Laplace transform methods, I, pdf
  24. Introduction to Laplace transform methods, II, pdf
  25. Lanchester’s equations modeling the battle between two armies, pdf
  26. Row reduction/Gauss elimination method for systems of linear equations, pdf.
  27. Eigenvalue method for homogeneous constant coefficient 2×2 systems of 1st order ODEs, pdf.
  28. Variation of parameters for first order non-homogeneous linear constant coefficient systems of ODEs, pdf.
  29. Electrical networks using Laplace transforms, pdf
  30. Separation of variables and the Transport PDE, pdf
  31. Fourier series, pdf.
  32. one-dimensional heat equation using Fourier series, pdf.
  33. one-dimensional wave equation using Fourier series, pdf.
  34. one-dimensional Schroedinger’s wave equation for a “free particle in a box” using Fourier series, pdf.
  35. All these lectures collected as one pdf (216 pages).
    While licensed Attribution-ShareAlike CC, in the US this book is in the public domain, as it was written while I was a US federal government employee as part of my official duties. A warning – it has lots of typos. The latest version, written with Marshall Hampton, is a JHUP book, much more polished, available on amazon and the JHUP website. Google “Introduction to Differential Equations Using Sage”.

Course review: pdf

Love, War, and Zombies, pdf
This set of slides is of a lecture I would give if there was enough time towards the end of the semester

Integral Calculus and SageMath

Long ago, using LaTeX I assembled a book on Calculus II (integral calculus), based on notes of mine, Dale Hoffman (which was written in word), and William Stein. I ran out of energy to finish it and the source files mostly disappeared from my HD. Recently, Samuel Lelièvre found a copy of the pdf of this book on the internet (you can download it here). It’s licensed under a Creative Commons Attribution 3.0 United States License. You are free to print, use, mix or modify these materials as long as you credit the original authors.

Table of Contents

0 Preface

1 The Integral
1.1 Area
1.2 Some applications of area
1.2.1 Total accumulation as “area”
1.2.2 Problems
1.3 Sigma notation and Riemann sums
1.3.1 Sums of areas of rectangles
1.3.2 Area under a curve: Riemann sums
1.3.3 Two special Riemann sums: lower and upper sums
1.3.4 Problems
1.3.5 The trapezoidal rule
1.3.6 Simpson’s rule and Sage
1.3.7 Trapezoidal vs. Simpson: Which Method Is Best?
1.4 The definite integral
1.4.1 The Fundamental Theorem of Calculus
1.4.2 Problems
1.4.3 Properties of the definite integral
1.4.4 Problems
1.5 Areas, integrals, and antiderivatives
1.5.1 Integrals, Antiderivatives, and Applications
1.5.2 Indefinite Integrals and net change
1.5.3 Physical Intuition
1.5.4 Problems
1.6 Substitution and Symmetry
1.6.1 The Substitution Rule
1.6.2 Substitution and definite integrals
1.6.3 Symmetry
1.6.4 Problems

2 Applications
2.1 Applications of the integral to area
2.1.1 Using integration to determine areas
2.2 Computing Volumes of Surfaces of Revolution
2.2.1 Disc method
2.2.2 Shell method
2.2.3 Problems
2.3 Average Values
2.3.1 Problems
2.4 Moments and centers of mass
2.4.1 Point Masses
2.4.2 Center of mass of a region in the plane
2.4.3 x-bar For A Region
2.4.4 y-bar For a Region
2.4.5 Theorems of Pappus
2.5 Arc lengths
2.5.1 2-D Arc length
2.5.2 3-D Arc length

3 Polar coordinates and trigonometric integrals
3.1 Polar Coordinates
3.2 Areas in Polar Coordinates
3.3 Complex Numbers
3.3.1 Polar Form
3.4 Complex Exponentials and Trigonometric Identities
3.4.1 Trigonometry and Complex Exponentials
3.5 Integrals of Trigonometric Functions
3.5.1 Some Remarks on Using Complex-Valued Functions

4 Integration techniques
4.1 Trigonometric Substitutions
4.2 Integration by Parts
4.2.1 More General Uses of Integration By Parts
4.3 Factoring Polynomials
4.4 Partial Fractions
4.5 Integration of Rational Functions Using Partial Fractions
4.6 Improper Integrals
4.6.1 Convergence, Divergence, and Comparison

5 Sequences and Series
5.1 Sequences
5.2 Series
5.3 The Integral and Comparison Tests
5.3.1 Estimating the Sum of a Series
5.4 Tests for Convergence
5.4.1 The Comparison Test
5.4.2 Absolute and Conditional Convergence
5.4.3 The Ratio Test
5.4.4 The Root Test
5.5 Power Series
5.5.1 Shift the Origin
5.5.2 Convergence of Power Series
5.6 Taylor Series
5.7 Applications of Taylor Series
5.7.1 Estimation of Taylor Series

6 Some Differential Equations
6.1 Separable Equations
6.2 Logistic Equation

7 Appendix: Integral tables

Ring theory, via coding theory and cryptography

In these notes on ring theory, I tried to cover enough material to get a feeling for basic ring theory, via cyclic codes and ring-based cryptosystems such as NTRU. Here’s a list of the topics.

1 Introduction to rings
1.1 Definition of a ring
1.2 Integral domains and fields
1.3 Ring homomorphisms and ideals
1.4 Quotient rings
1.5 UFDs
1.6 Polynomial rings
1.6.1 Application: Shamir’s Secret Sharing Scheme
1.6.2 Application: NTRU
1.6.3 Application: Modified NTRU
1.6.4 Application to LFSRs

2 Structure of finite fields
2.1 Cyclic multiplicative group
2.2 Extension fields
2.3 Back to the LFSR

3 Error-correcting codes
3.1 The communication model
3.2 Basic definitions
3.3 Binary Hamming codes
3.4 Coset leaders and the covering radius
3.5 Reed-Solomon codes as polynomial codes
3.6 Cyclic codes as polynomial codes
3.6.1 Reed-Solomon codes as cyclic codes
3.6.2 Quadratic residue codes
3.6.3 BCH bound for cyclic codes
3.6.4 Decoding cyclic codes
3.6.5 Cyclic codes and LFSRs

4 Lattices
4.1 Basic definitions
4.2 The shortest vector problem
4.2.1 Application to a congruential PKC
4.3 LLL and a reduced lattice basis
4.4 Hermite normal form
4.5 NTRU as a lattice cryptosystem

Calculus on graphs

In these notes, I tried to cover enough material to get a feeling for “calculus on graphs”, with applications to sports rankings and the Friendship Theorem. Here’s a list of the topics.

1 . Introduction
2. Examples
3. Basic definitions
3.1 Diameter, radius, and all that
3.2 Treks, trails, paths
3.3 Maps between graphs
3.4 Colorings
3.5 Transitivity
4. Adjacency matrix
4.1 Definition
4.2 Basic results
4.3 The spectrum
4.4 Application to the Friendship Theorem
4.5 Eigenvector centrality and the Keener ranking
4.6 Strongly regular graphs
4.7  Orientation on a graph
5. Incidence matrix
5.1 The unsigned incidence matrix
5.2 The oriented case
5.3 Cycle space and cut space
6. Laplacian matrix
6.1 The Laplacian spectrum
7  Hodge decomposition for graphs
7.1 Abstract simplicial complexes
7.2 The Bjorner complex and the Riemann hypothesis
7.3 Homology groups
8. Comparison graphs
8.1 Comparison matrices
8.2 HodgeRank
8.3 HodgeRank example

Gray codes

This is based on work done about 20 years ago with a former student Jim McShea.

Gray codes were introduced by Bell Labs physicist Frank Gray in the 1950s. As introduced, a Gray code is an ordering of the n-tuples in GF(2)^n = \{0,1\}^n such that two successive terms differ in only one position. A Gray code can be regarded as a Hamiltonian path in the cube graph. For example:

[[0, 0, 0], [1, 0, 0], [1, 1, 0], [0, 1, 0], [0, 1, 1], [1, 1, 1], [1, 0, 1], [0, 0, 1]]

These can be generalized to n-tuples of integers (mod m) in the obvious way.

Gray codes have several applications:

  • solving puzzles such as the Tower of Hanoi and the Brain [G],
  • analog-digital-converters (goniometers) [S],
  • Hamiltonian circuits in hypercubes [Gil] and Cayley graphs of Coxeter groups [CSW],
  • capanology (the study of bell-ringing) [W],
  • continuous space-filling curves [Gi],
  • classification of Venn diagrams [R],
  • design of communication codes,
  • and more (see Wikipedia).

The Brain puzzle

Here's a SageMath/Python function for computing Gray codes.
def graycode(length,modulus):
    Returns the n-tuple reverse Gray code mod m.

        sage: graycode(2,4)
        [[0, 0],
         [1, 0],
         [2, 0],
         [3, 0],
         [3, 1],
         [2, 1],
         [1, 1],
         [0, 1],
         [0, 2],
         [1, 2],
         [2, 2],
         [3, 2],
         [3, 3],
         [2, 3],
         [1, 3],
         [0, 3]]

    n,m = length,modulus
    F = range(m)
    if n == 1:
        return [[i] for i in F]
    L = graycode(n-1, m)
    M = []
    for j in F:
        M = M+[ll+[j] for ll in L]
    k = len(M)
    Mr = [0]*m
    for i in range(m-1):
        i1 = i*int(k/m)
        i2 = (i+1)*int(k/m)
        Mr[i] = M[i1:i2]
    Mr[m-1] = M[(m-1)*int(k/m):]
    for i in range(m):
        if is_odd(i):
    M0 = []
    for i in range(m):
        M0 = M0+Mr[i]
    return M0


[CSW] J. Conway, N. Sloane, and A. Wilks, “Gray codes and reflection groups”, Graphs and combinatorics 5(1989)315-325

[E] M. C. Er, “On generating the N-ary reflected Gray codes”, IEEE transactions on computers, 33(1984)739-741

[G] M. Gardner, “The binary Gray code”, in Knotted donuts and other mathematical entertainments, F. H. Freeman and Co., NY, 1986

[Gi] W. Gilbert, “A cube-filling Hilbert curve”, Math Intell 6 (1984)78

[Gil] E. Gilbert, “Gray codes and paths on the n-cube”, Bell System Technical Journal 37 (1958)815-826

[R] F. Ruskey, “A Survey of Venn Diagrams“, Elec. J. of Comb.(1997), and updated versions.

[S] Web page of T. Sillke

[W] A. White, “Ringing the cosets”, Amer. Math. Monthly 94(1987)721-746

Sports ranking methods, 4

This is the fourth of a series of expository posts on matrix-theoretic sports ranking methods. This post discusses the Elo rating.

This system was originally developed by Arpad Elo (Elo (1903-1992) was a physics professor at Marquette University in Milwaukee and a chess master, eight-time winner of the Wisconsin State Chess Championships.) Originally, it was developed for rating chess players in the 1950s and 1960s. Now it is used for table tennis, basketball, and other sports.

We use the following version of his rating system.

As above, assume all the $n$ teams play each other (ties allowed)
and let r_i denote the rating of Team i, i=1,2,\dots,n.

Let A=(A_{ij}) denote an $n\times n$ matrix of score results:

A_{ij}= \left\{ \begin{array}{rr} -1,& {\rm if\ team\ } i {\rm \ lost\ to\ team\ } j,\\ +1,& {\rm if\ team\ } i {\rm\ beat\ team\ } j,\\ 0, & {\rm if}\ i=j. \end{array} \right.

Let S_{ij}=(A_{ij}+1)/2.

As in the previous post, the matrix A associated to the example of the Patriot league is the adjacency matrix of a diagraph.

  1. Initialize all the ratings to be 100: {\bf r}=(r_1,\dots,r_n) = (100,\dots,100).
  2. After Team i plays Team j, update their rating using the formula

    r_i = r_i+K(S_{ij}-mu_{ij}),

    where K=10 and

    \mu_{ij} = (1+e^{-(r_i-r_j)/400})^{-1}.

In the example of the Patriot league, the ratings vector is

{\bf r}=(85.124, 104.79, 104.88, 85.032, 94.876, 124.53).

This gives the ranking

Lafayette < Army < Lehigh < Bucknell < Holy Cross < Navy.

This gives a prediction failure rate of 13.3\%.

Some SageMath code for this:

def elo_rating(A):
    A is a signed adjacency matrix for a directed graph.

    Returns elo ratings of the vertices of Gamma = Graph(A) 
        sage: A = matrix(QQ,[
        [0 , -1 , 1  , -1 , -1 , -1 ],
        [1,   0 ,  -1,  1,  1,   -1  ],
        [-1 , 1 ,  0 ,  1 , 1  , -1  ],
        [1 , -1 , -1,  0 ,  -1 , -1  ],
        [1 , - 1 , - 1 , 1 , 0 , - 1  ],
        [1 ,  1  ,  1  , 1  , 1  , 0 ]
        sage: elo_rating(A)
        (85.124, 104.79, 104.88, 85.032, 94.876, 124.53)

    n = len(A.rows())
    RR = RealField(prec=20)
    V = RR^n
    K = 10
    r0 = 100 # initial rating
    r = n*[r0]
    for i in range(n):
        for j in range(n):
            if ij and A[i][j]==1:
                S = 1
            elif ij and A[i][j]==-1:
                S = 0
                S = 1/2
            mu = 1/(1+e^(-(r[i]-r[j])/400))
            r[i] = r[i]+K*(S-mu)
    return V(r)