Jon Folkman

Jon Hal Folkman
Born	(1938-12-08)December 8, 1938 Ogden, Utah, US[1]
Died	January 23, 1969(1969-01-23) (aged 30) Los Angeles, California, US[2]
Alma mater	Princeton University
Known for	Folkman graph Shapley–Folkman lemma & theorem Folkman–Lawrence representation Folkman's theorem (memorial) Homology of lattices and matroids
Awards	Putnam Fellow (1960)
Scientific career
Fields	Combinatorics
Institutions	RAND Corporation
Doctoral advisor	John Milnor

Jon Hal Folkman (December 8, 1938 – January 23, 1969)[3] was an American mathematician, a student of John Milnor, and a researcher at the RAND Corporation.

Schooling

Folkman was a Putnam Fellow in 1960.[4] 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.[5]

Research

Jon Folkman found the semi-symmetric graph with the fewest possible vertices, the Folkman graph.

Jon Folkman contributed important theorems in many areas of combinatorics.

In geometric combinatorics, Folkman is known for his pioneering and posthumously-published studies of oriented matroids; in particular, the Folkman–Lawrence topological representation theorem[6] is "one of the cornerstones of the theory of oriented matroids".[7][8] 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 groups of finite rank.[9] In graph theory, he was the first to study semi-symmetric graphs, and he discovered the semi-symmetric graph with the fewest possible vertices, now known as the Folkman graph.[10] He proved the existence, for every positive h, of a finite K_h + 1-free graph which has a monocolored K_h in every 2-coloring of the edges, settling a problem previously posed by Paul Erdős and András Hajnal.[11] 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.[12]

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.[13]

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.[14] In Ramsey theory, the Rado–Folkman–Sanders theorem describes "partition regular" sets.

The Folkman Number F(p, q; r)

For r > max{p, q}, let F(p, q; r) denote the minimum number of vertices in a graph G that has the following properties:

1. G contains no complete subgraph on r vertices,
2. in any green-red coloring of the edges of G there is either a green K_p or a red K_q subgraph.

Some results are

• F(3, 3; 5) < 18 (Martin Erickson)[15]
• F(2, 3; 4) < 1000 (Vojtěch Rödl, Andrzej Dudek)[16]

Brain cancer and despair

Paul Erdős visited Jon Folkman after Folkman awoke from surgery for brain cancer. To restore Folkman's confidence, Erdős immediately challenged him to solve mathematical problems.[17]

In the late 1960s, Folkman suffered from brain cancer; while hospitalized, Folkman was visited repeatedly by Ronald Graham 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.

Folkman later purchased a gun and killed himself. Folkman's supervisor at RAND, Delbert Ray Fulkerson, blamed himself for failing to notice suicidal behaviors in Folkman. Several years later Fulkerson also killed himself.[17]

References

1. Jon Hal Folkman at FamilySearch
2. "Obituaries". The Ogden Standard-Examiner. January 24, 1969. p. 20 – via Newspapers.com.
3. Birth and death dates from Graham, R. L.; Rothschild, B. L. (1971), "Ramsey's theorem for n-parameter sets", Transactions of the American Mathematical Society, 159: 257–292, doi:10.1090/S0002-9947-1971-0284352-8, JSTOR 1996010, and from Spencer, Joel (1971), "Optimal ranking of tournaments", Networks, 1 (2): 135–138, doi:10.1002/net.3230010204, both of which were dedicated to the memory of Folkman.
4. Putnam competition results Archived 2000-02-29 at the Wayback Machine, Mathematical Association of America, retrieved 2010-10-17.
5. John Hal Folkman at the Mathematics Genealogy Project.
6. Folkman, J.; Lawrence, J. (1978), "Oriented matroids", Journal of Combinatorial Theory, Series B, 25 (2): 199–236, doi:10.1016/0095-8956(78)90039-4.
7. Page 17: Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). Oriented Matroids. Cambridge University Press. ISBN 978-0-521-77750-6.
8. The Folkman-Lawrence representation theorem is called the "Lawrence representation theorem" by Günter M. Ziegler in remark 7.23 on page 211: Ziegler, Günter M. (1995). Lectures on Polytopes. Graduate texts in mathematics. Vol. 152. New York: Springer-Verlag. ISBN 0-387-94365-X. (paper).
9. • Kung, Joseph P. S., ed. (1986). "III Enumeration in geometric lattices, 2. Homology". A Source book in matroid theory. Boston, MA: Birkhäuser Boston, Inc. pp. 201–202. ISBN 0-8176-3173-9. MR 0890330.
     • Folkman, Jon (1966). "The homology groups of a lattice". Journal of Mathematics and Mechanics. Vol. 15. pp. 631–636. MR 0188116.
     • Folkman, Jon; Kung, Joseph P. S., eds. (1986). "The homology groups of a lattice". A Source book in matroid theory. Boston, MA: Birkhäuser Boston, Inc. pp. 243–248. ISBN 0-8176-3173-9. MR 0188116.
     • Rota, Gian-Carlo (1964). "On the foundations of combinatorial theory, I: Theory of Möbius functions". Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete. 2 (4): 340–368. doi:10.1007/BF00531932. MR 0174487. S2CID 121334025.
     • Rota, Gian-Carlo (1986). "On the foundations of combinatorial theory, I: Theory of Möbius functions". In Kung, Joseph P. S. (ed.). A Source book in matroid theory. Vol. 2. Birkhäuser Boston, Inc. pp. 213–242. doi:10.1007/978-1-4684-9199-9_3. ISBN 0-8176-3173-9. MR 0174487. S2CID 121334025.
10. Folkman, J. (1967), "Regular line-symmetric graphs", Journal of Combinatorial Theory, 3 (3): 215–232, doi:10.1016/S0021-9800(67)80069-3.
11. Folkman, J. (1970), "Graphs with monochromatic complete subgraphs in every edge coloring", SIAM Journal on Applied Mathematics, 18: 19–24, doi:10.1137/0118004, MR 0268080.
12. J. Folkman: An upper bound on the chromatic number of a graph, in: Combinatorial theory and its application, II (Proc. Colloq., Balatonfüred, 1969), North-Holland, Amsterdam, 1970, 437–457.
13. Starr, Ross M. (1969), "Quasi-equilibria in markets with non-convex preferences (Appendix 2: The Shapley–Folkman theorem, pp. 35–37)", Econometrica, 37 (1): 25–38, CiteSeerX 10.1.1.297.8498, doi:10.2307/1909201, JSTOR 1909201.
14. Page 81 in Graham, R.; Rothschild, B.; Spencer, J. H. (1990), Ramsey Theory (2nd ed.), New York: John Wiley and Sons, ISBN 0-471-50046-1.
15. Erickson, Martin (1993). "An upper bound for the Folkman number F(3, 3; 5)". Journal of Graph Theory. 17 (6). Wiley: 679–681. doi:10.1002/jgt.3190170604. ISSN 0364-9024.
16. Dudek, Andrzej; Rödl, Vojtěch (2008). "On the Folkman Number f(2, 3, 4)". Experimental Mathematics. 17 (1). Informa UK Limited: 63–67. doi:10.1080/10586458.2008.10129023. ISSN 1058-6458.
17. Hoffman, Paul (1998), The man who loved only numbers: the story of Paul Erdős and the search for mathematical truth, Hyperion, pp. 109–110, ISBN 978-0-7868-6362-4.