Fulkerson Prize

Last updated
Fulkerson Prize
Awarded forOutstanding papers in the area of discrete mathematics
Country United States
Presented by
Reward(s)$1,500
First awarded1979
Website http://www.ams.org/profession/prizes-awards/ams-prizes/fulkerson-prize   OOjs UI icon edit-ltr-progressive.svg

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

Contents

Winners

Source: Mathematical Optimization Society official website. [47]

Source: American Mathematical Society official website. [48]

See also

Related Research Articles

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph K5 or the complete bipartite graph K3,3 as minors.

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs. Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding.

George Neil Robertson is a mathematician working mainly in topological graph theory, currently a distinguished professor emeritus at the Ohio State University.

<span class="mw-page-title-main">Paul Seymour (mathematician)</span> British mathematician

Paul D. Seymour is a British mathematician known for his work in discrete mathematics, especially graph theory. He was responsible for important progress on regular matroids and totally unimodular matrices, the four colour theorem, linkless embeddings, graph minors and structure, the perfect graph conjecture, the Hadwiger conjecture, claw-free graphs, χ-boundedness, and the Erdős–Hajnal conjecture. Many of his recent papers are available from his website.

<span class="mw-page-title-main">László Lovász</span> Hungarian mathematician

László Lovász is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He was the president of the International Mathematical Union from 2007 to 2010 and the president of the Hungarian Academy of Sciences from 2014 to 2020.

Colin de Verdière's invariant is a graph parameter for any graph G, introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators.

The Journal of Combinatorial Theory, Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. Series A is concerned primarily with structures, designs, and applications of combinatorics. Series B is concerned primarily with graph and matroid theory. The two series are two of the leading journals in the field and are widely known as JCTA and JCTB.

<span class="mw-page-title-main">Branch-decomposition</span> Hierarchical clustering of graph edges

In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G.

<span class="mw-page-title-main">Clique-sum</span> Gluing graphs at complete subgraphs

In graph theory, a branch of mathematics, a clique sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs G and H each contain cliques of equal size, the clique-sum of G and H is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then deleting all the clique edges or possibly deleting some of the clique edges. A k-clique-sum is a clique-sum in which both cliques have exactly k vertices. One may also form clique-sums and k-clique-sums of more than two graphs, by repeated application of the clique-sum operation.

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

<span class="mw-page-title-main">Maria Chudnovsky</span> Mathematician and engineer

Maria Chudnovsky is an Israeli-American mathematician working on graph theory and combinatorial optimization. She is a 2012 MacArthur Fellow.

Combinatorica is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors-in-chief with Paul Erdős as honorary editor-in-chief. The current editors-in-chief are Imre Bárány and József Solymosi. The advisory board consists of Ronald Graham, Gyula O. H. Katona, Miklós Simonovits, Vera Sós, and Endre Szemerédi. It is published by the János Bolyai Mathematical Society and Springer Verlag.

Robin Thomas was a mathematician working in graph theory at the Georgia Institute of Technology.

<span class="mw-page-title-main">Apex graph</span> Graph which can be made planar by removing a single node

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

<span class="mw-page-title-main">Alexander Schrijver</span> Dutch mathematician and computer scientist

Alexander (Lex) Schrijver is a Dutch mathematician and computer scientist, a professor of discrete mathematics and optimization at the University of Amsterdam and a fellow at the Centrum Wiskunde & Informatica in Amsterdam. Since 1993 he has been co-editor in chief of the journal Combinatorica.

In mathematics, a dijoin is a subset of the edges of a directed graph, with the property that contracting every edge in the dijoin produces a strongly connected graph. Equivalently, a dijoin is a subset of the edges that, for every dicut, includes at least one edge crossing the dicut. Here, a dicut is a partition of the vertices into two subsets, so that each edge that has an endpoint in both subsets is directed from the first subset to the second.

In the theory of combinatorial optimization, submodular flow is a general class of optimization problems that includes as special cases the minimum-cost flow problem, matroid intersection, and the problem of computing a minimum-weight dijoin in a weighted directed graph. It was originally formulated by Jack Edmonds and Rick Giles, and can be solved in polynomial time.

References

  1. Karp, Richard M. (1975). "On the computational complexity of combinatorial problems". Networks. 5: 45–68. doi:10.1002/net.1975.5.1.45.
  2. Appel, Kenneth; Haken, Wolfgang (1977). "Every planar map is four colorable, Part I: Discharging". Illinois Journal of Mathematics . 21: 429–490.
  3. Seymour, Paul (1977). "The matroids with the max-flow min-cut property". Journal of Combinatorial Theory . 23 (2–3): 189–222. doi: 10.1016/0095-8956(77)90031-4 .
  4. Judin, D.B.; Nemirovski, Arkadi (1976). "Informational complexity and effective methods of solution for convex extremal problems". Ekonomika I Matematicheskie Metody. 12: 357–369.
  5. Khachiyan, Leonid (1979). "A polynomial algorithm in linear programming". Akademiia Nauk SSSR. Doklady. 244: 1093–1096.
  6. "Leonid Khachiyan, professor, leading computer scientist". Boston Globe . May 5, 2005..
  7. Grötschel, Martin; Lovász, László; Schrijver, Alexander (1981). "The ellipsoid method and its consequences in combinatorial optimization". Combinatorica . 1 (2): 169–197. doi:10.1007/bf02579273.
  8. Egorychev, G. P. (1981). "The solution of van der Waerden's problem for permanents". Akademiia Nauk SSSR. Doklady. 258: 1041–1044.
  9. Falikman, D. I. (1981). "A proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix". Matematicheskie Zametki. 29: 931–938.
  10. Beck, Jozsef (1981). "Roth's estimate of the discrepancy of integer sequences is nearly sharp". Combinatorica . 1 (4): 319–325. doi:10.1007/bf02579452.
  11. Lenstra, H. W. Jr. (1983). "Integer programming with a fixed number of variables". Mathematics of Operations Research. 8 (4): 538–548. CiteSeerX   10.1.1.431.5444 . doi:10.1287/moor.8.4.538.
  12. Luks, Eugene M. (1982). "Isomorphism of graphs of bounded valence can be tested in polynomial time". Journal of Computer and System Sciences. 25 (1): 42–65. doi: 10.1016/0022-0000(82)90009-5 .
  13. "U of O Computer Chief Gets Top Award". Eugene Register-Guard . August 10, 1985..
  14. Tardos, Éva (1985). "A strongly polynomial minimum cost circulation algorithm". Combinatorica . 5 (3): 247–256. doi:10.1007/bf02579369.
  15. Karmarkar, Narendra (1984). "A new polynomial-time algorithm for linear programming". Combinatorica . 4 (4): 373–395. doi:10.1007/bf02579150.
  16. Dyer, Martin E.; Frieze, Alan M.; Kannan, Ravindran (1991). "A random polynomial time algorithm for approximating the volume of convex bodies". Journal of the ACM . 38 (1): 1–17. CiteSeerX   10.1.1.145.4600 . doi:10.1145/102782.102783.
  17. Alfred Lehman, "The width-length inequality and degenerate projective planes," W. Cook and P. D. Seymour (eds.), Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 1, (American Mathematical Society, 1990) pp. 101-105.
  18. Nikolai E. Mnev, "The universality theorems on the classification problem of configuration varieties and convex polytope varieties," O. Ya. Viro (ed.), Topology and Geometry-Rohlin Seminar, Lecture Notes in Mathematics 1346 (Springer-Verlag, Berlin, 1988) pp. 527-544.
  19. Billera, Louis (1988). "Homology of smooth splines: Generic triangulations and a conjecture of Strang". Transactions of the American Mathematical Society . 310 (1): 325–340. doi: 10.2307/2001125 . JSTOR   2001125.
  20. Kalai, Gil (1992). "Upper bounds for the diameter and height of graphs of the convex polyhedra". Discrete and Computational Geometry . 8 (4): 363–372. doi: 10.1007/bf02293053 .
  21. Robertson, Neil; Seymour, Paul; Thomas, Robin (1993). "Hadwiger's conjecture for K_6-free graphs". Combinatorica . 13 (3): 279–361. doi:10.1007/bf01202354.
  22. Kim, Jeong Han (1995). "The Ramsey number R(3,t) has order of magnitude t2/log t". Random Structures & Algorithms. 7 (3): 173–207. doi:10.1002/rsa.3240070302. MR   1369063..
  23. Goemans, Michel X.; Williamson, David P. (1995). "Improved approximation algorithms for the maximum cut and satisfiability probelsm using semi-definite programming". Journal of the ACM . 42 (6): 1115–1145. doi: 10.1145/227683.227684 .
  24. Michele Conforti, Gérard Cornuéjols, and M. R. Rao, "Decomposition of balanced matrices", Journal of Combinatorial Theory , Series B, 77 (2): 292–406, 1999.
  25. "MR Rao New Dean Of ISB". Financial Express . July 2, 2004..
  26. J. F. Geelen, A. M. H. Gerards and A. Kapoor, "The Excluded Minors for GF(4)-Representable Matroids," Journal of Combinatorial Theory , Series B, 79 (2): 247–2999, 2000.
  27. 1 2 3 2003 Fulkerson Prize citation, retrieved 2012-08-18.
  28. Bertrand Guenin, "A characterization of weakly bipartite graphs," Journal of Combinatorial Theory , Series B, 83 (1): 112–168, 2001.
  29. Satoru Iwata, Lisa Fleischer, Satoru Fujishige, "A combinatorial strongly polynomial algorithm for minimizing submodular functions," Journal of the ACM , 48 (4): 761–777, 2001.
  30. Alexander Schrijver, "A combinatorial algorithm minimizing submodular functions in strongly polynomial time," Journal of Combinatorial Theory , Series B 80 (2): 346–355, 2000.
  31. Manindra Agrawal, Neeraj Kayal and Nitin Saxena, "PRIMES is in P," Annals of Mathematics , 160 (2): 781–793, 2004.
  32. Raghunathan, M. S. (June 11, 2009). "India as a player in Mathematics". The Hindu . Archived from the original on June 14, 2009..
  33. 1 2 3 2006 Fulkerson Prize citation, retrieved 2012-08-19.
  34. Mark Jerrum, Alistair Sinclair and Eric Vigoda, "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries," Journal of the ACM , 51 (4): 671–697, 2004.
  35. Neil Robertson and Paul Seymour, "Graph Minors. XX. Wagner's conjecture," Journal of Combinatorial Theory , Series B, 92 (2): 325–357, 2004.
  36. Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "The strong perfect graph theorem". Annals of Mathematics . 164: 51–229. arXiv: math/0212070 . doi:10.4007/annals.2006.164.51.
  37. 1 2 3 2009 Fulkerson Prize citation, retrieved 2012-08-19.
  38. Spielman, Daniel A.; Teng, Shang-Hua (2004). "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time". Journal of the ACM . 51: 385–463. arXiv: math/0212413 . doi:10.1145/990308.990310.
  39. Hales, Thomas C. (2005). "A proof of the Kepler conjecture". Annals of Mathematics . 162 (3): 1063–1183. doi: 10.4007/annals.2005.162.1065 .
  40. Ferguson, Samuel P. (2006). "Sphere Packings, V. Pentahedral Prisms". Discrete and Computational Geometry . 36: 167–204. doi: 10.1007/s00454-005-1214-y .
  41. Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009). "Expander flows, geometric embeddings and graph partitioning". Journal of the ACM . 56 (2): 1–37. CiteSeerX   10.1.1.310.2258 . doi:10.1145/1502793.1502794.
  42. Johansson, Anders; Kahn, Jeff; Vu, Van H. (2008). "Factors in random graphs". Random Structures and Algorithms. 33: 1–28. doi:10.1002/rsa.20224.
  43. Lovász, László; Szegedy, Balázs (2006). "Limits of dense graph sequences". Journal of Combinatorial Theory . 96 (6): 933–957. arXiv: math/0408173 . doi:10.1016/j.jctb.2006.05.002.
  44. Santos, Francisco (2011). "A counterexample to the Hirsch conjecture". Annals of Mathematics . 176 (1): 383–412. arXiv: 1006.2814 . doi:10.4007/annals.2012.176.1.7. MR   2925387.
  45. 2015 Fulkerson Prize citation, retrieved 2015-07-18.
  46. Rothvoß, Thomas (2017). "The matching polytope has exponential extension complexity". Journal of the ACM . 64 (6): A41:1–A41:19. arXiv: 1311.2369 . doi:10.1145/3127497. MR   3713797.
  47. "The Fulkerson Prize". MOS Prizes. Mathematical Optimization Society. Retrieved 2024-07-25.
  48. "2024 Delbert Ray Fulkerson Prize Awarded". News from the AMS. American Mathematical Society. July 23, 2024. Retrieved 2024-07-25.