# History of Decision Mathematics

## History of Decision Mathematics

Each year in May we run a history of mathematics conference at Birkbeck, organised by the British Society for the History of Mathematics (BSHM), and supported by the Department of Economics, Mathematics and Statistics at Birkbeck. In 2021, we moved the conference online due to the pandemic.

The 2021 event looked at the history of Decision Mathematics, with talks on a range of subjects including decision problems on graphs, and linear programming.

The 2021 event looked at the history of Decision Mathematics. Talks were given on a range of subjects including decision problems on graphs, and linear programming.

## Abstracts

**Tinne Hoff Kjeldsen (University of Copenhagen)** The emergence of nonlinear programming: Duality and WWII

The significance of internal and external driving forces in the history of mathematics In this talk we will discuss the emergence of nonlinear programming as a research field in mathematics in the 1950s. We will especially focus on various kind of driving forces both from inside and outside of mathematics, and discuss the significance of their influence on its development. The term ‘nonlinear programming’ entered into mathematics when the two Princeton mathematicians Albert W. Tucker and Harold W. Kuhn at a conference in 1950 proved what became known as the Kuhn-Tucker theorem. Later it turned out that a similar result had been proved earlier, even twice: in 1939 and 1948, but nothing came of it. Kuhn and Tucker’s work on nonlinear programming grew out their work on duality in linear programming, which in itself originated from investigations of a mathematical model of a logistic problem in the US Air Force from the Second World War. This short outline prompts several questions: Why could the result of the Kuhn-Tucker theorem all of a sudden launch a new research field in mathematics in 1950? How did ideas of duality emerge in linear programming, and what role did they play for the development of nonlinear programming? How did the Air Force logistic problem cross the boundary to academic research in mathematics? What role did the military play and what influence did it have for the emergence of mathematical programming as a research area in mathematics in academia?

The talk will be governed by these questions, and the answers will show that both internal and external factors influenced the mathematicians’ work in crucial ways, illustrating the interplay between developments of mathematics and the historical conditions of its development.

**Norman Biggs (London School of Economics)** Linear Programming from Fibonacci to Farkas

Linear Programming is a 20th century invention, but its roots can be traced back to the tenth century, when the Islamic mathematician Abu Kamil wrote about ‘The Problem of the Birds’ This was one of several problems on ‘mixtures’ that appeared in Fibonacci’s 1202 manual of commercial arithmetic, the Liber Abbaci — in a chapter on ‘The Alloying of Monies’. His work was repeated in the early printed books of arithmetic, many of which contained chapters on Alligation, as the subject became known. Around 1600 the introduction of modern notation clarified the link with the study of linear inequalities and Diophantine problems. The next step was Fourier’s work on Statics, which led him to suggest a procedure for handling linear inequalities based on a combination of logic and algebra. He also introduced the idea of describing the set of feasible solutions geometrically. In 1898, inspired by Fourier’s work, Gyula Farkas proved what we now regard as the fundamental theorem about systems of linear inequalities. This topic eventually found many applications as a tool for solving complex problems of organization and planning, and it became known as Linear Programming. The theorem of Farkas also plays a significant role in some areas of Theoretical Economics, including Game Theory, as John von Neumann pointed out.

**Tony Mann (University of Greenwich)** Curious puzzles in decision mathematics

This talk will discuss some mathematical puzzles which relate to topics in decision mathematics. What do they tell us about the subject, and about the world we live in?

**Steve Noble (Birkbeck, University of London)** The Chromatic Polynomial

A significant part of early research in graph theory was motivated by attempts to solve the four colour problem – deciding whether or not it is always possible to colour the countries of a map with at most four colours so that countries sharing a border receive different colours. When rephrased using graph theoretic terminology, this led to the problems of colouring the vertices or edges of a graph so that adjacent vertices or edges receive different colours: both of these have applications in optimization. George Birkhoff introduced the chromatic polynomial in 1912 in an attempt to find an analytic proof of the four-colour theorem. When evaluated at a positive integer k, the chromatic polynomial gives the number of proper colourings of the vertices of a graph when k colours are available. Unfortunately, Birkhoff was unsuccessful, but by introducing the chromatic polynomial he opened the way to a huge body of research investigating the behaviour and meaning of its coefficients and roots. Some of the questions asked have surprising answers and others have been recently answered after remaining open for many years.

**Bjarne Toft (Emeritus, University of Southern Denmark)** The 2-factor problem in graph theory

The decision problem - to determine if a given graph has a 2-factor or not - is fundamental in graph theory. It has played an important role in the history of graph theory, starting with the 1889-1891 collaboration between James Joseph Sylvester in Oxford and Julius Petersen in Copenhagen, and continuing with results of Dénes König in Hungary, William T. Tutte in England, Hans Boris Alexander Belck in Germany, and Jack Edmonds in America. There are even some more recent results, completing a part of the Sylvester-Petersen investigation. And there are unsolved problems to think about.