Joseph Bernard Kruskal, Jr.

Quick Info

29 January 1928
New York City, New York, USA
19 September 2010
Maplewood, New Jersey, USA

Joseph Kruskal was an American mathematician, statistician and computer scientist who worked in combinatorics and graph theory.


Joseph Kruskal's parents were Joseph Bernard Kruskal Sr. (1885-1950), the owner of Kruskal & Kruskal, a wholesale fur business, and Lillian Rose Vorhaus (1898-1992) who became a leading populariser of origami in America from the 1950s onward. Lillian was born in New York but her father had emigrated from Poland. Perhaps we should note that Lillian taught origami to Persi Diaconis when he was working as a magician; he later he became a famous mathematician. Joseph was one of his parents' five children, William Henry Kruskal (1919-2005), Molly L Kruskal (1921-), Rosaly Kruskal (1923-), Martin David Kruskal (1925-2006) and Joseph Kruskal, the subject of this biography. Both Joseph's brothers, William Kruskal and Martin Kruskal became professors of mathematics and have biographies in this archive. While Joseph was growing up, his older brother Martin David took every opportunity to teach him mathematics.

Kruskal studied mathematics at the University of Chicago. He was awarded a BS in 1948 and an MS in 1949 by Chicago. Joseph Bernard Kruskal Sr. died in 1950. Joseph Kruskal's mother Lillian married Harry C Oppenheimer in 1954. Kruskal married Rachel Solomon in 1953; they had two children, Joyce and Benjamin. He then went to Princeton University where he undertook research for a Ph.D. advised by Roger Lyndon and Albert W Tucker. He explained how it was Paul Erdős, and not his advisors, who gave him the problem that led to his doctorate:-
Paul Erdős was telling lots of people about a conjecture due to a Hungarian mathematician, Andrew Vázsonyi (1916-2003) (also known as Endre Weiszfeld), he was friendly with and who he said "had died", meaning that he left mathematics for a well-paying job with some company - I think it was an airplane manufacturer. I was one of many people who heard him describe this conjecture. Roughly a year later, I had put a lot of work into this problem, but was still not close to a solution. By chance I bumped into Erdős at the Princeton Junction station. We chatted. I don't know how the conversation turned to the Vázsonyi conjecture - probably I told him I had been working on it. He said, oh, you must read a recent paper by Richard Rado. I quickly went to the library and found his paper, which I read with fear and trembling. Had I been scooped? It turned out that he had made significant progress, but hadn't cracked the nut. His work combined with mine finally led to a solution.
In 1954, Kruskal was awarded a Ph.D. by Princeton for his thesis The Theory of Well-Partially-Ordered Sets. He published Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture (1960) based on his thesis. He gives the following acknowledgement in this paper:-
This paper presents an expanded version of part of my doctoral dissertation at Princeton University. I wish to express my gratitude for the encouragement and direction of R Lyndon and A W Tucker. I also wish to acknowledge my debt to P Erdős for acquainting me with the problem and to my brother Martin Kruskal for his collaboration in the early development of the theory.
We should explain that while Kruskal was working towards his Ph.D., he was also employed at the US Office of Naval Research. This meant that, from 1950 to 1953, he worked at George Washington University on the Logistical Research Project. After the award of his doctorate, Kruskal continued to work for the US Office of Naval Research, spending the years 1954-1956 working on Princeton's Analytical Research Project.

Before publishing the paper based on his Ph.D. thesis, he had already published a number of articles including: Monotonic subsequences (1953); On the shortest spanning subtree of a graph and the traveling salesman problem (1956); (with Alan J Hoffman) Integral boundary points of convex polyhedra (1956); and (with R J Aumann) The coefficients in an allocation problem (1958). The authors of this last mentioned paper state:-
The research described in this paper has extended over a period of years, during which the authors have been affiliated with various institutions. These include Princeton University, Bell Telephone Laboratories, Inc., The University of Wisconsin, the Hebrew University, and the National Bureau of Standards.
They explain what the allocation problem is in the Introduction:-
The allocation or assignment problem is one of the most important problems of management science. It may be stated very briefly: We are given a system with a number of vacant positions and an equal number of available parts. We know how well each part performs in each position; we wish to assign the parts to the positions so that the system performance is optimised. Applications range far and wide, from employment to aircraft assignment to naval overhaul programmes. The computational aspects of the problem have been solved, under the assumption that a numerical value is associated with each assignment and that the value of the system is given by the sum of the values of the individual assignments. The crux of the problem, therefore, becomes the finding of values to use for the individual assignments.
During the three years 1956-59, Kruskal lectured at the University of Wisconsin at Madison and at the University of Wisconsin at Ann Arbor. In 1959 he took up an appointment at Bell Laboratories, in Murray Hill, New Jersey, where he continued to work for the rest of his career. However, he was a visiting professor at Yale University in 1967-68. He formally retired in 1993 but continued to undertake research at the Bell Laboratories for several years.

In [5] Kruskal lists his scientific interests as: multidimensional scaling; minimum spanning trees; clustering; and statistical linguistics. His name is well-known for being attached to a number of important concepts. For example 'Kruskal's algorithm', a graph theory algorithm which finds a minimal spanning tree of a weighted graph, was described in his 1956 paper On the shortest spanning subtree of a graph and the traveling salesman problem. The 'Kruskal's tree theorem' is the name now given to Kruskal's proof of the Vazsonyi's Conjecture which he published in Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture (1960). The 'Kruskal-Katona theorem' appears in Kruskal's 1963 paper The number of simplices in a complex and in Gyula O H Katona's 1968 paper A theorem of finite sets. The 'Kruskal rank' or 'kk-rank' appears in Kruskal's 1977 paper Three-way arrays rank and uniqueness of trilinear decompositions, with applications to arithmetic complexity and statistics.

In 1978 Kruskal published the book Multidimensional Scaling which was co-authored by Myron Wish. Mark Hansel writes in the review [3]:-
This book successfully emphasizes the underlying assumptions, substantive interpretation, and applications of multidimensional scaling ...
There is another area to which Kruskal has made a major contribution, namely a field known as lexicostatistics or glottochronology which is a form of comparative linguistics. Working with Isidore Dyen and Paul Black, Kruskal published the monograph An Indoeuropean Classification, a Lexicostatistical Experiment in the Transactions of the American Philosophical Society in 1992. In 1997 Kruskal announced that the 'Comparative Indoeuropean Data Corpus' was available. It included a 200-item lexicostatistical lists for 95 Indo-European speech varieties, cognation judgments between the lists, lexicostatistical percentages, individual replacement rates for 200 meanings, and time separations based on these rates.

Kruskal's interest in languages extended to an interest in how to write good scientific articles. His ideas in this area are contained in a letter he wrote to the journal Science. In the 5 September 1969 issue of Science, John H Wilson Jr published the letter Better Written Journal Papers - Who Wants Them? Kruskal replied in [4]:-
In the field of technical exposition, good writing does not mean graceful prose. It does mean explanations which are as easy to follow as the intrinsic difficulty of the subject will permit. It is not easy to describe the nature of clear exposition. However, in my editorial capacity I have had ample opportunity to observe the most common breaches. It may be useful to describe a few.

1. No common failure is more disastrous than omitting an important part of the argument or some important piece of evidence.

2. Authors frequently mislead their readers by emphasizing matters of marginal importance, and touching only lightly on the central issues.

3. Papers are often badly arranged. Arguments get separated from the propositions they are designed to support, definitions come long after terms are used, and observations which belong in one section intrude irrelevantly in another.

I freely confess to a love of beautiful English prose. ... Even in scientific exposition one occasionally encounters beautiful writing, and I enjoy it there as much as in John Barth's writings. However, graceful prose contributes only slightly to clarity of exposition, as any reader of 'Finnegans Wake' will testify.
His nephew, Clyde P Kruskal, wrote a tribute to his uncle following his death. He recalled some personal memories:-
I recall as a child how happy I was when he came to visit, usually after giving a talk somewhere. I also remember that once, when our extended family had a get together on the Long Island Sound, he spent all day taking the children one-by-one out sailing. ... There was a period of time when I used to visit Bell Labs, where Joe worked. I would stay with him and my Aunt Rachel, who were wonderful hosts. I used to enjoy our wide ranging dinner conversations, and I learned so much about words, politics, statistics, my family, etc.
The authors of [1] and [2] pay this tribute to Kruskal:-
Joe was both a pure and an applied mathematician par excellence. In studying over our folders of Joe's correspondence and publications, we are particularly struck by how encouraging his advice was to junior colleagues like the two of us, and even benign to ideological adversaries in his own peer group. He was a self-effacing person who seemed unaware of his own truly monumental accomplishments. As both a kindly friend and top-internationally recognized major mathematician, his absence is a very sorrowful one.
Kruskal was a fellow of the American Statistical Association and was honoured by being elected president of both the Psychometric Society and the Classification Society of North America. In 1979 he was awarded the Mathematical Association of America's The Lester R Ford Award for his paper, written jointly with Lawrence A Shepp, Computerized tomography: the new medical x-ray technology. This paper was published in the American Mathematical Monthly in 1978.

He died in his home in Maplewood, New Jersey, of pancreatic cancer at the age of 82.

References (show)

  1. J D Carroll and P Arabie, In memoriam Joseph B Kruskal: 1928-2010, Journal of Classification 29 (2012), 4-6.
  2. J D Carroll and P Arabie, In memoriam Joseph B Kruskal: 1928-2010, Psychometrika 78 (2) (2-13), 237-239.
  3. M Hansel, Review: Multidimensional Scaling, by Joseph B Kruskal and Myron Wish, Contemporary Sociology 9 (1) (1980), 107-108.
  4. J B Kruskal, Nature's Chief Masterpiece Is Writing Well, Science, New Series 166 (3904) (1969), 454-455.
  5. Joseph B (Joe) Kruskal, Bell Laboratories (1997).
  6. E Williams, Joseph B Kruskal Papers, 1926-2003, Archives of American Mathematics, Dolph Briscoe Center for American History, The University of Texas at Austin (2012).

Additional Resources (show)

Written by J J O'Connor and E F Robertson
Last Update October 2013