Michel Marie Deza (27 April 1939 – 23 November 2016) was a Soviet and French mathematician, specializing in combinatorics, discrete geometry and graph theory. He was the 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.
Selected papers Deza, M. (1974), "Solution d'un problème de Erdös-Lovász", Journal of Combinatorial Theory, Series B, 16 (2): 166–167, doi:10.1016/0095-8956(74)90059-8, MR 0337635. 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, doi:10.1007/BF02579189, MR 0729786, S2CID 46336677. 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, doi:10.1007/BF01580897, MR 1183645, S2CID 18981099. 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, vol. 1120, Springer-Verlag, pp. 112–128, doi:10.1007/3-540-61576-8_78, ISBN 978-3-540-61576-7, MR 1448925. This paper with his son Antoine Deza, a fellow of the Fields Institute 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, doi:10.1016/S0166-218X(97)00066-8, MR 1489057. 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.
… excerpt ends here. Continue reading the full article.
