Hal Kierstead is a Professor at the School of Mathematical and Statistical Sciences in Arizona State University.  He visited our Department in September to work with Jan van den Heuvel and Daniel Quiroz.  He also spoke at our Seminar on Combinatorics, Games and Optimisation about the history and applications of generalised colouring numbers, a notion which arose from an idea of Chen and Schelp for using well-chosen vertex orderings to find good bounds on colourings of graphs.  This is work which Hal has been working on with fellow authors Alexandr V. (Sasha) Kostochka, William T. (Tom) Trotter, Xuding Zhu and many others.  Whilst he was with us, Jan took the opportunity to discover more about Hal’s reserach, career route and interests.

How would you describe your research interests to a non-mathematician?
I usually say that I work in discrete mathematics, and that this is a subject that supports computer science in a way that is somewhat similar to how calculus supports physics. This usually suffices, but sometimes it leads to a discussion of continuous motion as opposed to the series of snap shots that make up a movie. With the more curious, I may talk about counting, probability, and modeling with graph theory.

Consider me a more curious person; what examples of modelling in graph theory do you look at in your research?
First I would preface the discussion with two examples:

• Mathematicians have been studying prime numbers for centuries, going back to the ancient Greeks. With the assistance of record keeping their understanding became both much more sophisticated and much more widely disseminated over time. This work was a huge intellectual accomplishment with no conceivable functional application until the development of computers and the need for encryption. Today the theory of prime numbers is the backbone of encryption, and as such, is fundamentally important to society.
• Another example is the probabilistic method introduced by Paul Erdős to attack existence problems for various discrete structures. These problems were purely intellectual questions; there was no intention to apply results in any practical way. The technique was so effective that it quickly spread among mathematicians as it was used to answer more and more questions. It was not the individual answers that where of major importance, but the development and spread of the technique and related ideas. Soon it spread to theoretical computer science, and then to the practical algorithms used in today’s software.

With this background I will return to your question, and demonstrate this process operating on a much smaller scale. In graduate school I was working in logic on questions about what functions on infinite partial orderings can be calculated by an algorithm. The algorithm did not have to be fast, or polynomial, or even exponential; it only had to eventually give the correct answer. Later, while working in my first job I reformulated the underlying question in terms of online algorithms for finite partial orderings, and with Tom Trotter gave an exact answer for the special case of interval orders. Computer scientists use interval orders to model the problem of using as few storage locations as possible to store variables while running a program. Their techniques give optimal answers if all variables take the same space, but it is an NP-complete problem when the variables have different sizes. By using my work on First-Fit and online algorithms I was able to give the first two polynomial-time linear approximation algorithms for this problem.

If you hadn’t seen these applications of your research, would you be disappointed by that or would you have changed your area of research?
I investigated interval orders because I was aware there could be applications, so if I had not found them I would have been disappointed, but it would not have effected the main line of my research.

If a fledgling mathematics student (at any level, Undergraduate to PhD) asks you for advice on whether they should do more applied or more theoretical courses or research, how would you guide them?
There are several considerations:

1. I think a strong undergraduate student who wants to go to graduate school in applied math should concentrate on proof driven theory courses. There is plenty of time to learn applications later. That said, it is worthwhile to investigate what areas of applied mathematics fit the student’s interests.
2. Weak to average undergraduates gain little from proof driven theory courses, but seem to do well when they enter the job market.
3. My brother and I both got PhDs in logic in 1979. It was a time when academic jobs were very tight. I took the academic route whilst my brother took the industry route. We both had very satisfying careers. I had more freedom to do what I wanted, and what I found interesting (and important); he made twice as much money. My brother said that the most important thing for him was to learn as many first year graduate courses as possible. I often tell this story to students.

I think mathematics students have many choices for careers, and my role should be to inform, not advise.

What other interests do you have? How do you “switch off” from mathematics (assuming you do, now and then)?
I like to exercise, especially hiking and biking. I follow soccer (football) closely, especially the EPL, and watch games while peddling my stationary bike. I do not play anymore, but I can feel like I played by the end of the match! I like to relax before dinner with a beer, sitting on my back deck looking at the hills, and reading politics or light novels.

That’s a fantastic view in the photograph you sent us.  What city is in the background?
Mostly Phoenix, Tempe is to the right.