Jon Folkman
Encyclopedia
Jon Hal Folkman was an American mathematician, a student of John Milnor
, and a researcher at the RAND Corporation.
in 1960. He received his Ph.D. in 1964 from Princeton University
, under the supervision of Milnor, with a thesis entitled Equivariant Maps of Spheres into the Classical Groups.
.
In geometric combinatorics
, Folkman is known for his pioneering and posthumously-published studies of oriented matroid
s; in particular, the Folkman–Lawrence representation theorem is "one of the cornerstones of the theory of oriented matroids". In lattice
theory, Folkman solved an open problem
on the foundations of combinatorics
by proving a conjecture
of Gian–Carlo Rota
; in proving Rota's conjecture, Folkman characterized the structure of the homology groups
of "geometric lattices"
in terms of the free
Abelian group
s of finite rank. In graph theory
, he was the first to study semi-symmetric graph
s, and he discovered the semi-symmetric graph with the fewest possible vertices, now known as the Folkman graph
. He proved the existence, for every positive h, of a finite Kh + 1-free graph which has a monocolored Kh in every 2-coloring of the edges, settling a problem previously posed by Paul Erdős
and András Hajnal
. He further proved that if G is a finite graph such that every set S of vertices contains an independent set of size (|S| − k)/2 then the chromatic number of G is at most k + 2.
In convex geometry
, Folkman worked with his RAND colleague Lloyd Shapley
to prove the Shapley–Folkman lemma and theorem
: Their results suggest that sums of sets
are approximately convex; in mathematical economics
their results are used to explain why economies with many agents have approximate equilibria
, despite individual nonconvexities.
In additive combinatorics, Folkman's theorem
states that for each assignment of finitely many colors to the positive integers, there exist arbitrarily large sets of integers all of whose nonempty sums have the same color; the name was chosen as a memorial to Folkman by his friends. In Ramsey theory
, the Rado–Folkman–Sanders theorem describes "partition regular" sets.
and Paul Erdős
. After his brain surgery, Folkman was despairing that he had lost his mathematical skills. As soon as Folkman received Graham and Erdős at the hospital, Erdős challenged Folkman with mathematical problems, helping to rebuild his confidence
.
Notwithstanding his ability to solve the problems posed by Erdős, Folkman purchased a gun and killed himself. Folkman's supervisor at RAND, Delbert Ray Fulkerson, blamed himself for failing to notice suicidal behaviors in Folkman. Years later Fulkerson also killed himself.
John Milnor
John Willard Milnor is an American mathematician known for his work in differential topology, K-theory and dynamical systems. He won the Fields Medal in 1962, the Wolf Prize in 1989, and the Abel Prize in 2011. Milnor is a distinguished professor at Stony Brook University...
, and a researcher at the RAND Corporation.
Schooling
Folkman was a Putnam FellowWilliam Lowell Putnam Mathematical Competition
The William Lowell Putnam Mathematical Competition, often abbreviated to the Putnam Competition, is an annual mathematics competition for undergraduate college students of the United States and Canada, awarding scholarships and cash prizes ranging from $250 to $2,500 for the top students and $5,000...
in 1960. He received his Ph.D. in 1964 from 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....
, under the supervision of Milnor, with a thesis entitled Equivariant Maps of Spheres into the Classical Groups.
Research
Jon Folkman contributed important theorems in many areas of combinatoricsCombinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
.
In geometric combinatorics
Geometric combinatorics
Geometric combinatorics is a branch of mathematics in general and combinatorics in particular. It includes a number of subareas such as polyhedral combinatorics , convex geometry , and discrete geometry, which in turn has many applications to computational geometry...
, Folkman is known for his pioneering and posthumously-published studies of oriented matroid
Oriented matroid
An oriented matroid is a mathematical structure that abstracts the properties of directed graphs and of arrangements of vectors in a vector space over an ordered field...
s; in particular, the Folkman–Lawrence representation theorem is "one of the cornerstones of the theory of oriented matroids". In lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
theory, Folkman solved an open problem
Open problem
In science and mathematics, an open problem or an open question is a known problem that can be accurately stated, and has not yet been solved . Some questions remain unanswered for centuries before solutions are found...
on the foundations of combinatorics
Enumerative combinatorics
Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations...
by proving a conjecture
Conjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
of Gian–Carlo Rota
Gian-Carlo Rota
Gian-Carlo Rota was an Italian-born American mathematician and philosopher.-Life:Rota was born in Vigevano, Italy...
; in proving Rota's conjecture, Folkman characterized the structure of the homology groups
Homology (mathematics)
In mathematics , homology is a certain general procedure to associate a sequence of abelian groups or modules with a given mathematical object such as a topological space or a group...
of "geometric lattices"
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
in terms of the free
Free group
In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...
Abelian group
Abelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
s of finite rank. In graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, he was the first to study semi-symmetric graph
Semi-symmetric graph
In the mathematical field of graph theory, a semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive....
s, and he discovered the semi-symmetric graph with the fewest possible vertices, now known as the Folkman graph
Folkman graph
In the mathematical field of graph theory, the Folkman graph, named after Jon Folkman, is a bipartite 4-regular graph with 20 vertices and 40 edges....
. He proved the existence, for every positive h, of a finite Kh + 1-free graph which has a monocolored Kh in every 2-coloring of the edges, settling a problem previously posed by 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...
and András Hajnal
András Hajnal
András Hajnal is an emeritus professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.-Biography:Hajnal was born on 13 May 1931, in Hungary....
. He further proved that if G is a finite graph such that every set S of vertices contains an independent set of size (|S| − k)/2 then the chromatic number of G is at most k + 2.
In convex geometry
Convex geometry
Convex geometry is the branch of geometry studying convex sets, mainly in Euclidean space.Convex sets occur naturally in many areas of mathematics: computational geometry, convex analysis, discrete geometry, functional analysis, geometry of numbers, integral geometry, linear programming,...
, Folkman worked with his RAND colleague Lloyd Shapley
Lloyd Shapley
Lloyd Stowell Shapley is a distinguished American mathematician and economist. He is a Professor Emeritus at University of California, Los Angeles, affiliated with departments of Mathematics and Economics...
to prove the Shapley–Folkman lemma and theorem
Shapley–Folkman lemma
In geometry and economics, the Shapley–Folkman lemma describes the Minkowski addition of sets in a vector space. Minkowski addition is defined as the addition of the sets' members: for example, adding the set consisting of the integers zero and one to itself yields the set consisting of...
: Their results suggest that sums of sets
Minkowski addition
In geometry, the Minkowski sum of two sets A and B in Euclidean space is the result of adding every element of A to every element of B, i.e...
are approximately convex; in mathematical economics
Mathematical economics
Mathematical economics is the application of mathematical methods to represent economic theories and analyze problems posed in economics. It allows formulation and derivation of key relationships in a theory with clarity, generality, rigor, and simplicity...
their results are used to explain why economies with many agents have approximate equilibria
Economic equilibrium
In economics, economic equilibrium is a state of the world where economic forces are balanced and in the absence of external influences the values of economic variables will not change. It is the point at which quantity demanded and quantity supplied are equal...
, despite individual nonconvexities.
In additive combinatorics, Folkman's theorem
Folkman's theorem
Folkman's theorem is a theorem in mathematics, and more particularly in arithmetic combinatorics and Ramsey theory. According to this theorem, whenever the natural numbers are partitioned into finitely many subsets, there exist arbitrarily large sets of numbers all of whose sums belong to the same...
states that for each assignment of finitely many colors to the positive integers, there exist arbitrarily large sets of integers all of whose nonempty sums have the same color; the name was chosen as a memorial to Folkman by his friends. In 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...
, the Rado–Folkman–Sanders theorem describes "partition regular" sets.
Brain cancer and despair
In the late 1960s, Folkman suffered from brain cancer; while hospitalized, Folkman was visited repeatedly by Ronald GrahamRonald Graham
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"...
and 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...
. After his brain surgery, Folkman was despairing that he had lost his mathematical skills. As soon as Folkman received Graham and Erdős at the hospital, Erdős challenged Folkman with mathematical problems, helping to rebuild his confidence
Self-confidence
The socio-psychological concept of self-confidence relates to self-assuredness in one's personal judgment, ability, power, etc., sometimes manifested excessively.Being confident in yourself is infectious if you present yourself well, others will want to follow in your foot steps towards...
.
Notwithstanding his ability to solve the problems posed by Erdős, Folkman purchased a gun and killed himself. Folkman's supervisor at RAND, Delbert Ray Fulkerson, blamed himself for failing to notice suicidal behaviors in Folkman. Years later Fulkerson also killed himself.