Joseph Kruskal
Encyclopedia
Joseph Bernard Kruskal, Jr. (January 29, 1928 – September 19, 2010) was an American
mathematician
, statistician
, computer scientist
and psychometrician. He was a student at the University of Chicago
and at Princeton University
, where he completed his Ph.D.
in 1954, nominally under Albert W. Tucker
and Roger Lyndon
, but de facto under Paul Erdős
with whom he had two very short conversations. Kruskal has worked on well-quasi-ordering
s and multidimensional scaling
.
He was a Fellow of the American Statistical Association
, former president of the Psychometric Society, and former president of the Classification Society of North America. He also initiated and was first president of the Fair Housing Council of South Orange
and Maplewood
in 1963, and actively supported civil rights in several other organizations.
In statistics, Kruskal's most influential work is his seminal contribution to the formulation of multidimensional scaling
. In computer science, his best known work is Kruskal's algorithm
for computing the minimal spanning tree (MST) of a weighted graph. The algorithm first orders the edges by weight and then proceeds through the ordered list adding an edge to the partial MST provided that adding the new edge does not create a cycle. Minimal spanning trees have applications to the construction and pricing of communication networks. In combinatorics, he is known for Kruskal's tree theorem
(1960), which is also interesting from a mathematical logic
perspective since it can only be proved nonconstructively. Kruskal also applied his work in linguistics, in an experimental lexicostatistical
study of Indo-European
languages, together with the linguists Isidore Dyen
and Paul Black. Their database is still widely-used (available at the link below).
Kruskal was born in New York City
to a successful fur wholesaler, Joseph B. Kruskal, Sr. His mother, Lillian Rose Vorhaus Kruskal Oppenheimer, became a noted promoter of Origami
during the early era of television. He died in Princeton.
Joseph Kruskal should not be confused with his two brothers Martin David Kruskal
(1925–2006; co-inventor of soliton
s and of surreal number
s) and William Kruskal
(1919–2005; developed the Kruskal-Wallis one-way analysis of variance
).
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
, statistician
Statistician
A statistician is someone who works with theoretical or applied statistics. The profession exists in both the private and public sectors. The core of that work is to measure, interpret, and describe the world and human activity patterns within it...
, computer scientist
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
and psychometrician. He was a student at the University of Chicago
University of Chicago
The University of Chicago is a private research university in Chicago, Illinois, USA. It was founded by the American Baptist Education Society with a donation from oil magnate and philanthropist John D. Rockefeller and incorporated in 1890...
and at Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
, where he completed his Ph.D.
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
in 1954, nominally under Albert W. Tucker
Albert W. Tucker
Albert William Tucker was a Canadian-born American mathematician who made important contributions in topology, game theory, and non-linear programming....
and Roger Lyndon
Roger Lyndon
Roger Conant Lyndon was an American mathematician, for many years a professor at the University of Michigan. He is known for Lyndon words, the Curtis–Hedlund–Lyndon theorem, Craig–Lyndon interpolation and the Lyndon–Hochschild–Serre spectral sequence.-Biography:Lyndon was born on December 18, 1917...
, but de facto under Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
with whom he had two very short conversations. Kruskal has worked on well-quasi-ordering
Well-quasi-ordering
In mathematics, specifically order theory, a well-quasi-ordering or wqo is a well-founded quasi-ordering with an additional restriction on sequences - that there is no infinite sequence x_i with x_i \not \le x_j for all i...
s and multidimensional scaling
Multidimensional scaling
Multidimensional scaling is a set of related statistical techniques often used in information visualization for exploring similarities or dissimilarities in data. MDS is a special case of ordination. An MDS algorithm starts with a matrix of item–item similarities, then assigns a location to each...
.
He was a Fellow of the American Statistical Association
American Statistical Association
The American Statistical Association , is the main professional US organization for statisticians and related professions. It was founded in Boston, Massachusetts on November 27, 1839, and is the second oldest, continuously operating professional society in the United States...
, former president of the Psychometric Society, and former president of the Classification Society of North America. He also initiated and was first president of the Fair Housing Council of South Orange
South Orange, New Jersey
-Demographics:As of the census of 2000, there were 16,964 people, 5,522 households, and 3,766 families residing in the township. The population density was 5,945.3 people per square mile . There were 5,671 housing units at an average density of 1,987.5 per square mile...
and Maplewood
Maplewood, New Jersey
Maplewood is a township in Essex County, New Jersey, United States. As of the 2010 United States Census, the township population was 23,867.-History:...
in 1963, and actively supported civil rights in several other organizations.
In statistics, Kruskal's most influential work is his seminal contribution to the formulation of multidimensional scaling
Multidimensional scaling
Multidimensional scaling is a set of related statistical techniques often used in information visualization for exploring similarities or dissimilarities in data. MDS is a special case of ordination. An MDS algorithm starts with a matrix of item–item similarities, then assigns a location to each...
. In computer science, his best known work is Kruskal's algorithm
Kruskal's algorithm
Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized...
for computing the minimal spanning tree (MST) of a weighted graph. The algorithm first orders the edges by weight and then proceeds through the ordered list adding an edge to the partial MST provided that adding the new edge does not create a cycle. Minimal spanning trees have applications to the construction and pricing of communication networks. In combinatorics, he is known for Kruskal's tree theorem
Kruskal's tree theorem
In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered...
(1960), which is also interesting from a mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
perspective since it can only be proved nonconstructively. Kruskal also applied his work in linguistics, in an experimental lexicostatistical
Lexicostatistics
Lexicostatistics is an approach to comparative linguistics that involves quantitative comparison of lexical cognates. Lexicostatistics is related to the comparative method but does not reconstruct a proto-language...
study of Indo-European
Indo-European
Indo-European may refer to:* Indo-European languages** Aryan race, a 19th century and early 20th century term for those peoples who are the native speakers of Indo-European languages...
languages, together with the linguists Isidore Dyen
Isidore Dyen
Isidore Dyen was an American linguist, Professor Emeritus of Malayo-Polynesian and Comparative Linguistics at Yale University...
and Paul Black. Their database is still widely-used (available at the link below).
Kruskal was born in New York City
New York City
New York is the most populous city in the United States and the center of the New York Metropolitan Area, one of the most populous metropolitan areas in the world. New York exerts a significant impact upon global commerce, finance, media, art, fashion, research, technology, education, and...
to a successful fur wholesaler, Joseph B. Kruskal, Sr. His mother, Lillian Rose Vorhaus Kruskal Oppenheimer, became a noted promoter of Origami
Origami
is the traditional Japanese art of paper folding, which started in the 17th century AD at the latest and was popularized outside Japan in the mid-1900s. It has since then evolved into a modern art form...
during the early era of television. He died in Princeton.
Joseph Kruskal should not be confused with his two brothers Martin David Kruskal
Martin Kruskal
Martin David Kruskal was an American mathematician and physicist. He made fundamental contributions in many areas of mathematics and science, ranging from plasma physics to general relativity and from nonlinear analysis to asymptotic analysis...
(1925–2006; co-inventor of soliton
Soliton
In mathematics and physics, a soliton is a self-reinforcing solitary wave that maintains its shape while it travels at constant speed. Solitons are caused by a cancellation of nonlinear and dispersive effects in the medium...
s and of surreal number
Surreal number
In mathematics, the surreal number system is an arithmetic continuum containing the real numbers as well as infinite and infinitesimal numbers, respectively larger or smaller in absolute value than any positive real number...
s) and William Kruskal
William Kruskal
William Henry Kruskal was an American mathematician and statistician. He is best known for having formulated the Kruskal–Wallis one-way analysis of variance , a widely-used nonparametric statistical method.Kruskal was born in New York City to a successful fur wholesaler...
(1919–2005; developed the Kruskal-Wallis one-way analysis of variance
Kruskal-Wallis one-way analysis of variance
In statistics, the Kruskal–Wallis one-way analysis of variance by ranks is a non-parametric method for testing whether samples originate from the same distribution. The factual null hypothesis is that the populations from which the samples originate, have the same median...
).
Concepts named after Joseph Kruskal
- Kruskal's algorithmKruskal's algorithmKruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized...
(1956) - Kruskal's tree theoremKruskal's tree theoremIn mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered...
(1960) - Kruskal–Katona theoremKruskal–Katona theoremIn algebraic combinatorics, the Kruskal–Katona theorem gives a complete characterization of the f-vectors of abstract simplicial complexes. It includes as a special case the Erdős–Ko–Rado theorem and can be restated in terms of uniform hypergraphs. The theorem is named after Joseph Kruskal...
(1963)
External links
- The Dyen, Kruskal and Black lexicostatistical database : the 200-meaning Swadesh lists for 95 Indo-European languages.