Michel Deza

Selected papers

• . This paper solved a conjecture of Paul Erdős and László Lovász 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.
• . 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.
• . 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.
• . 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 and 275,840 vertices.
• . Much of Deza's work concerns isometric embeddings of graphs and metric spaces into vector spaces with the L₁ distance; this paper is one of many in this line of research. An earlier result of Deza showed that every L₁ 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, the scale factor can always be taken to be 2.

  Books

• . 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".
• . A sequel to Geometry of cuts and metrics, this book concentrates more specifically on L₁ metrics.
• . Reviewed in , p. 57. This book is organized as a list of distances of many types, each with a brief description.
• . 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.
• ,
• .
• .
• .
• .
• .
• .

  Poetry in Russian

• Deza, M., 59--62, Sintaksis, Paris.
• .
• .