Memories of TS Michael, by Bryan Shader

TS Michael passed away on November 22, 2016, from cancer. I will miss him as a colleague and a kind, wise soul.

ts-michaels_2015-12-21_small

TS Michael in December 2015 at the USNA


Bryan Shader has kindly allowed me to post these reminiscences that he wrote up.

Memories of TS Michael, by Bryan Shader

Indirect influence
TS indirectly influenced my choice of U. Wisconsin-Madison for graduate school. My senior year as an undergraduate, Herb Ryser gave a talk at my school. After the talk I was able to meet Ryser and asked for advice on graduate schools. Herb indicated that one of his very good undergraduate students had chosen UW-Madison and really liked the program. I later found out that the person was TS.

About the name
Back in the dark ages, universities still did registration by hand. This meant that for a couple of days before each semester the masses of students would wind their way through a maze of stations in a large gymnasium. For TS’s first 4 years, he would invariably encounter a road block because someone had permuted the words in his name (Todd Scott Michael) on one of the forms. After concretely verifying the hatcheck probabilities and fearing that this would cause some difficulties in graduating, he legally changed his name to TS Michael.

Polyominoes & Permanents
I recall many stories about how TS’s undergraduate work on polyominoes affected
his life. In particular, he recalled how once he started working on tilings on
polyominoes, he could no longer shower, or swim without visualizing polynomino
tilings on the wall’s or floor’s tiling. We shared an interest and passion for permanents (the permanent is a function of a matrix much like the determinant and plays a critical role in combinatorics). When working together we frequently would find that we both couldn’t calculate the determinant of a 3 by 3 matrix correctly, because we were calculating the permanent rather than the determinant.

Presentations and pipe-dreams
TS and I often talked about how best to give a mathematical lecture, or
presentation at a conference. Perhaps this is not at all surprising, as our common advisor (Richard Brualdi) is an incredible expositor, as was TS’s undergraduate advisor (Herb Ryser, our mathematical grandfather). TS often mentioned how Herb Ryser scripted every moment of a lecture; he knew each word he would write on the board and exactly where it would be written. TS wasn’t quite so prescriptive–but before any presentation he gave he would go to the actual room of the presentation a couple of times and run through the talk. This would include answering questions from the “pretend” audience. After being inspired by TS’s talks, I adopted this preparation method.
TS and I also fantasized about our talks ending with the audience lifting us up on their shoulders and carrying us out of the room in triumph! That is never happened to either of us (that I know of), but to have it, as a dream has always been a good motivation.

Mathematical heritage
TS was very interested in his mathematical heritage, and his mathematics brothers and sisters. TS was the 12th of Brandi’s 37 PhD students; I was the 15th. In 2005, TS and I organized a conference (called the Brualidfest) in honor of Richard Brualdi. Below I attach some photos of the design for the T-shirt.

ts-michaels_memories1

t-shirt design for Brualdi-Fest, 1

The first image shows a biclique partition of K_5; for each color the edges of the given color form a complete bipartite graph; and each each of the completed graph on 5 vertices is in exactly one of these complete bipartite graph. This is related to one of TS’s favorite theorem: the Graham-Pollak Theorem.

ts-michaels_memories2

t-shirt design for Bruldi-Fest, 2

The second image (when the symbols are replaced by 1s) is the incidence matrix of the projective plane of order 2; one of TS’s favorite matrices.

Here’s a photo of the Brualdi and his students at the conference:

ts-michaels_memories3

From L to R they are: John Mason (?), Thomas Forreger, John Goldwasser, Dan Pritikin, Suk-geun Hwang, Han Cho, T.S. Michael, B. Shader, Keith Chavey, Jennifer Quinn, Mark Lawrence, Susan Hollingsworth, Nancy Neudauer, Adam Berliner, and Louis Deaett.

Here’s a picture for a 2012 conference:

ts-michaels_memories4

From bottom to top: T.S. Michael (1988), US Naval Academy, MD; Bryan Shader (1990), University of Wyoming, WY; Jennifer Quinn (1993), University of Washington, Tacoma, WA; Nancy Neudauer (1998), Pacific University, OR; Susan Hollingsworth (2006), Edgewood College, WI; Adam Berliner (2009), St. Olaf College, MN; Louis Deaett (2009), Quinnipiac University, CT; Michael Schroeder (2011), Marshall University, WV; Seth Meyer (2012), Kathleen Kiernan (2012).

Here’s a caricature of TS made by Kathy Wilson (spouse of mathematician
Richard Wilson) at the Brualdifest:

OLYMPUS DIGITAL CAMERA

TS Michael, by Kathy Wilson

Long Mathematical Discussions
During graduate school, TS and I would regularly bump into each other as we
were coming and going from the office. Often this happened as we were crossing University Avenue, one of the busiest streets in Madison. The typical conversation started with a “Hi, how are you doing? Have you considered X?” We would then spend the next 60-90 minutes on the street corner (whether it was a sweltering 90 degrees+, or a cold, windy day) considering X. In more recent years, these conversations have moved to hotel lobbies at conferences that we attend together. These discussions have been some of the best moments of my life, and through them I have become a better mathematician.

Here’s a photo of T.S. Michael with Kevin van der Meulen at the Brualdi-fest.

OLYMPUS DIGITAL CAMERA

I’m guessing they are in the midst of one of those “Have you considered X?” moments that TS is famous for.

Mathematical insight
TS has taught me a lot about mathematics, including:

  •  How trying to generalize a result can lead to better understanding of the original result.
  •  How phrasing a question appropriately is often the key to a mathematical breakthrough
  • Results that are surprising (e.g. go against ones intuition), use an elegant proof (e.g. bring in matrices in an unexpected way), and are aesthetically pleasing are worth pursing (as Piet Hein said “Problems worthy of attack, prove their worth by fighting back.”)
  •  The struggle to present the proof of a result in the simplest, most self-contained way is important because often it produces a better understanding. If you can’t say something in a clean way, then perhaps you really don’t understand it fully.

TS’ mathematics fathers are:
Richard Brualdi ← Herb Ryser ← Cyrus MacDuffee ← Leonard Dickson ← E.H. Moore ← H. A. Newton ← Michel Chasles ← Simeon Poisoon ← Joseph Lagrange ← Leonhard Euler ← Johann Bernoulli.

Simple unsolved math problem, 5

It seems everyone’s heard of Pascal’s triangle. However, if you haven’t then it is an infinite triangle of integers with 1‘s down each side and the inside numbers determined by adding the two numbers above it:

wikipedia-pascals_triangle_5

First 6 rows of Pascal’s triangle

The first 6 rows are depicted above. It turns out, these entries are the binomial coefficients that appear when you expand (x+y)^n and group the terms into like powers x^{n-k}y^k:

wikipedia-pascals_triangle_2

First 6 rows of Pascal’s triangle, as binomial coefficients.

The history of Pascal’s triangle pre-dates Pascal, a French mathematician from the 1600s, and was known to scholars in ancient Persia, China, and India.

Starting in the mid-to-late 1970s, British mathematician David Singmaster was known for his research on the mathematics of the Rubik’s cube. However, in the early 1970’s, Singmaster made the following conjecture [1].

Conjecture: If N(a) denotes the number of times the number a > 1 appears in Pascal’s triangle then N(a) \leq 12 for all a>1.

In fact, there are no known numbers a>1 with N(a)>8 and the only number greater than one with N(a)=8 is a=3003.

References:

[1] Singmaster, D. “Research Problems: How often does an integer occur as a binomial coefficient?”, American Mathematical Monthly, 78(1971) 385–386.

The minimum upset ranking problem

Suppose n teams play each other, and let Team r_1 < Team r_2 < \dots < Team r_n denote some fixed ranking (where r_1,\dots,r_n is some permutation of 1,\dots,n). An upset occurs when a lower ranked team beats an upper ranked team. For each ranking, {\bf r}, let U({\bf r}) denote the total number of upsets. The minimum upset problem is to find an “efficient” construction of a ranking for which U({\bf r}) is as small as possible.

In general, let A_{ij} denote the number of times Team i beat team $j$ minus the number of times Team j beat Team i. We regard this matrix as the signed adjacency matrix of a digraph \Gamma. Our goal is to find a Hamiltonian (undirected) path through the vertices of \Gamma which goes the “wrong way” on as few edges as possible.

  1. Construct the list of spanning trees of \Gamma (regarded as an undirected graph).
  2. Construct the sublist of Hamiltonian paths (from the spanning trees of maximum degree 2).
  3. For each Hamiltonian path, compute the associated upset number: the total number of edges transversal in \Gamma going the “right way” minus the total number going the “wrong way.”
  4. Locate a Hamiltonian for which this upset number is as large as possible.

Use this sagemath/python code to compute such a Hamiltonian path.

def hamiltonian_paths(Gamma, signed_adjacency_matrix = []):
    """
    Returns a list of hamiltonian paths (spanning trees of 
    max degree <=2).

    EXAMPLES:
        sage: Gamma = graphs.GridGraph([3,3])
        sage: HP = hamiltonian_paths(Gamma)
        sage: len(HP)
        20
        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: Gamma = Graph(A, format='weighted_adjacency_matrix')
        sage: HP = hamiltonian_paths(Gamma, signed_adjacency_matrix = A)
        sage: L = [sum(x[2]) for x in HP]; max(L)
        5
        sage: L.index(5)
        21
        sage: HP[21]                                 
        [Graph on 6 vertices,
         [0, 5, 2, 1, 3, 4],
         [-1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1]]
        sage: L.count(5)
        1

    """
    ST = Gamma.spanning_trees()
    if signed_adjacency_matrix == []:
        HP = []
        for X in ST:
            L = X.degree_sequence()
            if max(L)<=2:
                #print L,ST.index(X), max(L)
                HP.append(X)
        return HP
    if signed_adjacency_matrix != []:
        A = signed_adjacency_matrix
        HP = []
        for X in ST:
            L = X.degree_sequence()
            if max(L)<=2:
                #VX = X.vertices()
                EX = X.edges()
		if EX[0][1] != EX[-1][1]:
                    ranking = X.shortest_path(EX[0][0],EX[-1][1])
		else:
		    ranking = X.shortest_path(EX[0][0],EX[-1][0])
		signature = [A[ranking[i]][ranking[j]] for i in range(len(ranking)-1) for j in range(i+1,len(ranking))]
                HP.append([X,ranking,signature])
        return HP

Wessell describes this method in a different way.

  1. Construct a matrix, M=(M_{ij}), with rows and columns indexed by the teams in some fixed order. The entry in the i-th row and the j-th column is defined bym_{ij}= \left\{ \begin{array}{rr} 0,& {\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.
  2. Reorder the rows (and corresponding columns) to in a basic win-loss order: the teams that won the most games go at the
    top of M, and those that lost the most at the bottom.
  3. Randomly swap rows and their associated columns, each time checking if the
    number of upsets has gone down or not from the previous time. If it has gone down, we keep
    the swap that just happened, if not we switch the two rows and columns back and try again.

An implementaiton of this in Sagemath/python code is:

def minimum_upset_random(M,N=10):
    """
    EXAMPLES:
        sage: M = matrix(QQ,[
        [0 , 0 , 1  , 0 , 0 , 0 ],
        [1,   0 ,  0,  1,  1,   0  ],
        [0 , 1 ,  0 ,  1 , 1  , 0  ],
        [1 , 0 , 0,  0 ,  0 , 0  ],
        [1 , 0 , 0 , 1 , 0 , 0  ],
        [1 ,  1  ,  1  , 1  , 1  , 0 ]
        ])
        sage: minimum_upset_random(M)
        (
        [0 0 1 1 0 1]                    
        [1 0 0 1 0 1]                    
        [0 1 0 0 0 0]                    
        [0 0 1 0 0 0]                    
        [1 1 1 1 0 1]                    
        [0 0 1 1 0 0], [1, 2, 0, 3, 5, 4]
        )

    """
    n = len(M.rows())
    Sn = SymmetricGroup(n)
    M1 = M
    wins = sum([sum([M1[j][i] for i in range(j,6)]) for j in range(6)])
    g0 = Sn(1)
    for k in range(N):
        g = Sn.random_element()
        P = g.matrix()
        M0 = P*M1*P^(-1)
        if sum([sum([M0[j][i] for i in range(j,6)]) for j in range(6)])>wins:
            M1 = M0
            g0 = g*g0
    return M1,g0(range(n))

Simple unsolved math problem, 3

A perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself. For example,  1 + 2 + 3 = 6 implies 6 is a perfect number.

Unsolved Problem: Are there any odd perfect numbers? 

The belief, by some, that there are none goes back over 500 years (wikipedia).

If you want to check out some recent research into this problem, see oddperfect.org.

b5527a1273f40d19e7fa821caa0208b9

(Another unsolved problem: Are there an infinite number of even perfect numbers?)

Simple unsolved math problem, 2

In 1911, Otto Toeplitz asked the following question.

Inscribed Square Problem: Does every plane simple closed curve contain all four vertices of some square?

This question, also known as the square peg problem or the Toeplitz’ conjecture, is still unsolved in general. (It is known in lots of special cases.)

inscribed_square

Inscribed square, by Claudio Rocchini

Thanks to Mark Meyerson (“Equilateral triangles and continuous curves”,Fundamenta Mathematicae, 1980) and others, the analog for triangles is true. For any triangle T and Jordan curve C, there is a triangle similar to T and inscribed in C. (In particular, the triangle can be equilateral.) The survey page by Mark J. Nielsen has more information on this problem.

Added 2016-11-23: See also this recent post by T. Tao.

Simple unsolved math problem, 1

In 1937 Lothar Collatz proposed the 3n+1 conjecture (known by a long list of aliases), is stated as follows.

First, we define the function f on the set of positive integers:

If the number n is even, divide it by two: f(n)=n/2.
If the number n is odd, triple it and add one: f(n)=3n+1.

In modular arithmetic notation, define the function f as follows:
f(n)=  {n/2},\  if \ n\equiv 0 \pmod 2, and f(n)=  {3n+1},\  if \ n\equiv 1 \pmod 2. Believe it or not, this is the restriction to the positive integers of the complex-valued map (2+7z-(2+5z)\cos(\pi z))/4.

The 3n+1 conjecture is: The sequence
n,\ f(n),\ f^2(n)=f(f(n)),\ f^3(n)=f(f^2(n)),\ \dots
will eventually reach the number 1, regardless of which positive integer n is chosen initially.

This is still unsolved, though a lot of people have worked on it. For a recent survey of results, see the paper by Chamberland.