Ronald Graham
Encyclopedia
Ronald Lewis Graham is a mathematician
credited by the American Mathematical Society
as being "one of the principal architects of the rapid development worldwide of discrete mathematics
in recent years". He has done important work in scheduling theory, computational geometry
, Ramsey theory
, and quasi-randomness.
He is currently the Chief Scientist at the California Institute for Telecommunications and Information Technology (also known as Cal-(IT)2) and the Irwin and Joan Jacobs Professor in Computer Science and Engineering at the University of California, San Diego
(UCSD).
. In 1962, he received his Ph.D.
in mathematics
from the University of California, Berkeley
.
His 1977 paper considered a problem in Ramsey theory, and gave a "large number" as an upper bound for its solution. This number has since become well known as the largest number ever used in a mathematical proof (is listed as such in the Guinness Book of Records), and is now known as Graham's number
.
Graham popularized the concept of the Erdős number
, named after the highly prolific Hungarian mathematician Paul Erdős
(1913–1996). A scientist's Erdős number is the minimum number of coauthored publications away from a publication with Erdős. Graham's Erdős number is 1. He co-authored almost 30 papers with Erdős, and was also a good friend. Erdős often stayed with Graham, and allowed him to look after his mathematical papers and even his income. Graham and Erdős visited the young mathematician Jon Folkman
when he was hospitalized with brain cancer.
Between 1993 and 1994 Graham served as the president of the American Mathematical Society. Graham was also featured in Ripley's Believe It or Not for being not only "one of the world's foremost mathematicians", but also "a highly skilled trampolinist and juggler", and past president of the International Jugglers' Association
.
In 2003, Graham won the American Mathematical Society's annual Steele Prize
for Lifetime Achievement. The prize was awarded on January 16 that year, at the Joint Mathematics Meetings in Baltimore, Maryland. In 1999 he was inducted as a Fellow of the Association for Computing Machinery
. Graham, prolific mathematician and industrious human being, has won many other prizes over the years; he was one of the laureates of the prestigious Pólya Prize
the first year it was ever awarded, and among the first to win the Euler Medal
. The Mathematical Association of America
has also awarded him both the Lester R. Ford
prize which was "...established in 1964 to recognize authors of articles of expository excellence published in The American Mathematical Monthly...", and the Carl Allendoerfer
prize which was established in 1976 for the same reasons, however for a different magazine, the Mathematics Magazine.
He has published about 320 papers and five books, including Concrete Mathematics
with Donald Knuth
.
He is married to Fan Chung Graham (known professionally as Fan Chung
), who is the Akamai Professor in Internet Mathematics at the University of California, San Diego. He has four children—three daughters, Ché, Laura, Christy and a son, Marc—from an earlier marriage.
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....
credited by the American Mathematical Society
American Mathematical Society
The American Mathematical Society is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, which it does with various publications and conferences as well as annual monetary awards and prizes to mathematicians.The society is one of the...
as being "one of the principal architects of the rapid development worldwide of discrete mathematics
Discrete mathematics
Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...
in recent years". He has done important work in scheduling theory, computational geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
, Ramsey theory
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...
, and quasi-randomness.
He is currently the Chief Scientist at the California Institute for Telecommunications and Information Technology (also known as Cal-(IT)2) and the Irwin and Joan Jacobs Professor in Computer Science and Engineering at the University of California, San Diego
University of California, San Diego
The University of California, San Diego, commonly known as UCSD or UC San Diego, is a public research university located in the La Jolla neighborhood of San Diego, California, United States...
(UCSD).
Biography
Graham was born in Taft, CaliforniaTaft, California
Taft is a city in the foothills at the extreme southwestern edge of the San Joaquin Valley, in Kern County, California. Taft is located west-southwest of Bakersfield, at an elevation of 955 feet . The population was 9,327 at the 2010 census...
. In 1962, he received 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 mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
from the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
.
His 1977 paper considered a problem in Ramsey theory, and gave a "large number" as an upper bound for its solution. This number has since become well known as the largest number ever used in a mathematical proof (is listed as such in the Guinness Book of Records), and is now known as Graham's number
Graham's number
Graham's number, named after Ronald Graham, is a large number that is an upper bound on the solution to a certain problem in Ramsey theory.The number gained a degree of popular attention when Martin Gardner described it in the "Mathematical Games" section of Scientific American in November 1977,...
.
Graham popularized the concept of the Erdős number
Erdos number
The Erdős number describes the "collaborative distance" between a person and mathematician Paul Erdős, as measured by authorship of mathematical papers.The same principle has been proposed for other eminent persons in other fields.- Overview :...
, named after the highly prolific Hungarian mathematician 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...
(1913–1996). A scientist's Erdős number is the minimum number of coauthored publications away from a publication with Erdős. Graham's Erdős number is 1. He co-authored almost 30 papers with Erdős, and was also a good friend. Erdős often stayed with Graham, and allowed him to look after his mathematical papers and even his income. Graham and Erdős visited the young mathematician Jon Folkman
Jon Folkman
Jon Hal Folkman was an American mathematician, a student of John Milnor, and a researcher at the RAND Corporation.-Schooling:Folkman was a Putnam Fellow in 1960. He received his Ph.D...
when he was hospitalized with brain cancer.
International Jugglers' Association
The International Jugglers' Association or IJA is the oldest and largest organization of jugglers. It is open to members worldwide.-Benefits of Membership:* Special from major prop vendors worldwide.* Member prices in the IJA’s ....
.
Leroy P. Steele Prizes
The Leroy P. Steele Prizes are awarded every year by the American Mathematical Society, for distinguished research work and writing in the field of mathematics. Since 1993 there has been a formal division into three categories....
for Lifetime Achievement. The prize was awarded on January 16 that year, at the Joint Mathematics Meetings in Baltimore, Maryland. In 1999 he was inducted as a Fellow of the Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
. Graham, prolific mathematician and industrious human being, has won many other prizes over the years; he was one of the laureates of the prestigious Pólya Prize
Pólya Prize (SIAM)
The Pólya Prize is a prize in mathematics, awarded by the Society for Industrial and Applied Mathematics. First given in 1969, the prize is named after Hungarian mathematician George Pólya...
the first year it was ever awarded, and among the first to win the Euler Medal
Euler Medal
The Euler Medal, named after the 18th century mathematician Leonhard Euler, is an honor awarded annually by the Institute of Combinatorics and its Applications to a member with a distinguished lifetime contribution to combinatorial research who are still active in research.-Laureates:* 2008: Gabor...
. The Mathematical Association of America
Mathematical Association of America
The Mathematical Association of America is a professional society that focuses on mathematics accessible at the undergraduate level. Members include university, college, and high school teachers; graduate and undergraduate students; pure and applied mathematicians; computer scientists;...
has also awarded him both the Lester R. Ford
L. R. Ford
Lester Randolph Ford, Sr. was an American mathematician, editor of the American Mathematical Monthly from 1942 to 1946, and President of the Mathematical Association of America from 1947 to 1948....
prize which was "...established in 1964 to recognize authors of articles of expository excellence published in The American Mathematical Monthly...", and the Carl Allendoerfer
Carl B. Allendoerfer
Carl Barnett Allendoerfer was a prominent American mathematician in the mid-twentieth century, known for his work in topology and mathematics education.-Background:...
prize which was established in 1976 for the same reasons, however for a different magazine, the Mathematics Magazine.
He has published about 320 papers and five books, including Concrete Mathematics
Concrete Mathematics
Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik, is a mathematical textbook that is widely used in computer-science departments. It provides mathematical knowledge and skills for computer science, especially for the analysis of algorithms...
with Donald Knuth
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
.
He is married to Fan Chung Graham (known professionally as Fan Chung
Fan Chung
Fan Rong K Chung Graham , known professionally as Fan Chung, is a mathematician who works mainly in the areas of spectral graph theory, extremal graph theory and random graphs, in particular...
), who is the Akamai Professor in Internet Mathematics at the University of California, San Diego. He has four children—three daughters, Ché, Laura, Christy and a son, Marc—from an earlier marriage.
See also
- Coffman–Graham algorithmCoffman–Graham algorithmIn job shop scheduling and graph drawing, the Coffman–Graham algorithm is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, for arranging the elements of a partially ordered set into a sequence of levels...
- Erdős–Graham problem
- Graham's numberGraham's numberGraham's number, named after Ronald Graham, is a large number that is an upper bound on the solution to a certain problem in Ramsey theory.The number gained a degree of popular attention when Martin Gardner described it in the "Mathematical Games" section of Scientific American in November 1977,...
- Graham scanGraham scanThe Graham scan is a method of computing the convex hull of a finite set of points in the plane with time complexity O. It is named after Ronald Graham, who published the original algorithm in 1972...
External links
- Graham's UCSD Faculty Research Profile
- Papers of Ron Graham - a comprehensive archive of the papers written by Ron Graham
- About Ron Graham - a page summarizing some aspects of Graham's life and mathematics - part of Fan Chung's website
- "Math expert coolly juggles scientific puzzles and six or seven balls" - a SignOnSanDiego.com article on Graham, by Bruce V. Bigelow, dated March 18, 2003
- AMS news release telling of Graham's winning of the 2003 Steele Prize