Michel Marie Deza (27 April 1939-23 November 2016) was a Soviet and French mathematician, specializing in combinatorics, discrete geometry and graph theory. He is a retired director of research at the French National Centre for Scientific Research (CNRS), the vice president of the European Academy of Sciences, a research professor at the Japan Advanced Institute of Science and Technology, and one of the three founding editors-in-chief of the European Journal of Combinatorics.
Deza graduated from Moscow University in 1961, after which he worked at the Soviet Academy of Sciences until emigrating to France in 1972. In France, he worked at CNRS from 1973 until his 2005 retirement. He has written eight books and about 280 academic papers with 75 different co-authors, including four papers with Paul Erdős, giving him an Erdős number of 1.
The papers from a conference on combinatorics, geometry and computer science, held in Luminy, France in May 2007, have been collected as a special issue of the European Journal of Combinatorics in honor of Deza's 70th birthday.
Deza, M. (1974), "Solution d'un problème de Erdös-Lovász", Journal of Combinatorial Theory, Series B, 16 (2): 166–167, MR 0337635, doi:10.1016/0095-8956(74)90059-8 . This paper solved a conjecture of Paul Erdős and László Lovász (in [1], p. 406) that a sufficiently large family of k-subsets of any n-element universe, in which the intersection of every pair of k-subsets has exactly t elements, has a common t-element set shared by all the members of the family. Manoussakis writes that Deza is sorry not to have kept and framed the US$100 check from Erdős for the prize for solving the problem, and that this result inspired Deza to pursue a lifestyle of mathematics and travel similar to that of Erdős.
Deza, M.; Frankl, P.; Singhi, N. M. (1983), "On functions of strength t", Combinatorica, 3 (3–4): 331–339, MR 0729786, doi:10.1007/BF02579189 . This paper considers functions ƒ from subsets of some n-element universe to integers, with the property that, when A is a small set, the sum of the function values of the supersets of A is zero. The strength of the function is the maximum value t such that all sets A of t or fewer elements have this property. If a family of sets F has the property that it contains all the sets that have nonzero values for some function ƒ of strength at most t, F is t-dependent; the t-dependent families form the dependent sets of a matroid, which Deza and his co-authors investigate.
Deza, M.; Laurent, M. (1992), "Facets for the cut cone I", Mathematical Programming, 56 (1–3): 121–160, MR 1183645, doi:10.1007/BF01580897 . This paper in polyhedral combinatorics describes some of the facets of a polytope that encodes cuts in a complete graph. As the maximum cut problem is NP-complete, but could be solved by linear programming given a complete description of this polytope's facets, such a complete description is unlikely.
Deza, A.; Deza, M.; Fukuda, K. (1996), "On skeletons, diameters and volumes of metric polyhedra", Combinatorics and Computer Science (PDF), Lecture Notes in Computer Science, 1120, Springer-Verlag, pp. 112–128, MR 1448925, doi:10.1007/3-540-61576-8_78 . This paper with Antoine Deza, who holds a Canada Research Chair in Combinatorial Optimization at McMaster University, combines Michel Deza's interests in polyhedral combinatorics and metric spaces; it describes the metric polytope, whose points represent symmetric distance matrices satisfying the triangle inequality. For metric spaces with seven points, for instance, this polytope has 21 dimensions (the 21 pairwise distances between the points) and 275,840 vertices.
Chepoi, V.; Deza, M.; Grishukhin, V. (1997), "Clin d'oeil on L1-embeddable planar graphs", Discrete Applied Mathematics, 80 (1): 3–19, MR 1489057, doi:10.1016/S0166-218X(97)00066-8 . Much of Deza's work concerns isometric embeddings of graphs (with their shortest path metric) and metric spaces into vector spaces with the L1 distance; this paper is one of many in this line of research. An earlier result of Deza showed that every L1 metric with rational distances could be scaled by an integer and embedded into a hypercube; this paper shows that for the metrics coming from planar graphs (including many graphs arising in chemical graph theory), the scale factor can always be taken to be 2.
Deza, M.; Laurent, M. (1997), Geometry of cuts and metrics, Algorithms and Combinatorics, 15, Springer, ISBN 3-540-61611-X, MR 1460488 . As MathSciNet reviewer Alexander Barvinok writes, this book describes "many interesting connections ... among polyhedral combinatorics, local Banach geometry, optimization, graph theory, geometry of numbers, and probability".
Deza, M.; Grishukhin, V.; Shtogrin, M. (2004), Scale-isometric polytopal graphs in hypercubes and cubic lattices, Imperial College Press, ISBN 1-86094-421-3, MR 2051396 . A sequel to Geometry of cuts and metrics, this book concentrates more specifically on L1 metrics.
Deza, E.; Deza, M. (2006), Dictionary of Distances, Elsevier, ISBN 0-444-52087-2 . Reviewed in Newsletter of the European Mathematical Society 64 (June 2007), p. 57. This book is organized as a list of distances of many types, each with a brief description.
Deza, M.; Dutour Sikirić, M. (2008), Geometry of chemical graphs: polycycles and two-faced maps, Encyclopedia of Mathematics and its Applications, 119, Cambridge University Press, ISBN 978-0-521-87307-9, MR 2429120 . This book describes the graph-theoretic and geometric properties of fullerenes and their generalizations, planar graphs in which all faces are cycles with only two possible lengths.
Deza, M.; Deza, E. (2009), Encyclopedia of Distances, Springer-Verlag, ISBN 978-3-642-00233-5 ,
Deza, E.; Deza, M. (2011), Figurate Numbers, World Scientific, ISBN 978-981-4355-48-3 .
Deza, M.; Deza, E. (2013), Encyclopedia of Distances, 2nd revised edition, Springer-Verlag, ISBN 978-3-642-30957-1 .
Deza, M.; Deza, E. (2014), Encyclopedia of Distances, 3rd revised edition, Springer-Verlag, ISBN 978-3-662-44341-5 .
Deza, M.; Deza, E. (2016), Encyclopedia of Distances, 4th revised edition, Springer-Verlag, ISBN 978-3-662-52844-0 .
Deza, M.; Dutour Sikirić, M.; Shtogrin, M. (2015), Geometric Structure of Chemistry-relevant Graphs, Springer, ISBN 978-81-322-2448-8 .
Deza, E.; Deza, M.; Dutour Sikirić, M. (2016), Generalizations of Finite Metrics and Cuts, World Scientific, ISBN 978-98-147-4039-5 .
Deza, M. (1983), 59--62, Sintaksis, Paris (http://dc.lib.unc.edu/cdm/item/collection/rbr/?id=30912).
Deza, M. (2014), Poems and interviews, Probel-2000, Moscow, ISBN 978-5-98604-442-2 (http://www.liga.ens.fr/~deza/InRussian/DEZA-M.pdf).
Deza, M. (2016), 75--77, Probel-2000, Moscow, ISBN 978-5-98604-555-9 (http://www.liga.ens.fr/~deza/InRussian/DEZA-M2.pdf).
Agudo, Pierre (January 24, 1998), "Le mathématicien a besoin d'être aimé", l'Humanité (in French)
