Michel Deza
Encyclopedia
Michel Marie Deza is 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 five books and about 250 academic papers with 75 different co-authors and co-editors, 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.
of Paul Erdős
and László Lovász
(in http://www.math-inst.hu/~p_erdos/1975-32.pdf, 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.. 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 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.. 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 graph
s (including many graphs arising in chemical graph theory
), the scale factor can always be taken to be 2.
s and their generalizations, planar graphs in which all faces are cycles with only two possible lengths...
France
The French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
, specializing in combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, discrete geometry
Discrete geometry
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles,...
and graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
. 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
European Academy of Sciences
The European Academy of Sciences has as mission to promote excellence in science and technology and their essential roles in fostering social and economic development and progress. It is registered in and operates under rules and regulations of Belgium. The European Academy of Sciences is an...
, 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
European Journal of Combinatorics
The European Journal of Combinatorics , is a peer-reviewed scientific journal for combinatorics. It is an international, bimonthly journal of pure mathematics, specializing in theories arising from combinatorial problems...
.
Deza graduated from Moscow University in 1961, after which he worked at the Soviet Academy of Sciences
Russian Academy of Sciences
The Russian Academy of Sciences consists of the national academy of Russia and a network of scientific research institutes from across the Russian Federation as well as auxiliary scientific and social units like libraries, publishers and hospitals....
until emigrating to France in 1972. In France, he worked at CNRS from 1973 until his 2005 retirement.
He has written five books and about 250 academic papers with 75 different co-authors and co-editors, including four papers with Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
, giving him an Erdős number
Erdos number
The Erdős number describes the "collaborative distance" between a person and mathematician Paul Erdős, as measured by authorship of mathematical papers.The same principle has been proposed for other eminent persons in other fields.- Overview :...
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
. This paper solved a conjectureErdos conjecture
The prolific mathematician Paul Erdős and his various collaborators made many famous mathematical conjectures, over a wide field of subjects.Some of these are the following:* The Cameron–Erdős conjecture on sum-free sets of integers, proved by Ben Green....
of Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and László Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
(in http://www.math-inst.hu/~p_erdos/1975-32.pdf, 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.. 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
Family of sets
In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called 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
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
, which Deza and his co-authors investigate.. This paper in polyhedral combinatorics
Polyhedral combinatorics
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....
describes some of the facets of a polytope
Polytope
In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...
that encodes cuts in a complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
. As the maximum cut
Maximum cut
For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the max-cut problem.The problem can be stated simply as follows...
problem is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, but could be solved by linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
given a complete description of this polytope's facets, such a complete description is unlikely.. This paper with Antoine Deza, who holds a Canada Research Chair in Combinatorial Optimization at McMaster University
McMaster University
McMaster University is a public research university whose main campus is located in Hamilton, Ontario, Canada. The main campus is located on of land in the residential neighbourhood of Westdale, adjacent to Hamilton's Royal Botanical Gardens...
, 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.. Much of Deza's work concerns isometric
Isometry
In mathematics, an isometry is a distance-preserving map between metric spaces. Geometric figures which can be related by an isometry are called congruent.Isometries are often used in constructions where one space is embedded in another space...
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
Hypercube
In geometry, a hypercube is an n-dimensional analogue of a square and a cube . It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length.An...
; this paper shows that for the metrics coming from planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s (including many graphs arising in chemical graph theory
Chemical graph theory
Chemical graph theory is the topology branch of mathematical chemistry which applies graph theory to mathematical modelling of chemical phenomena....
), 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 L1 metrics.. 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.. This book describes the graph-theoretic and geometric properties of fullereneFullerene
A fullerene is any molecule composed entirely of carbon, in the form of a hollow sphere, ellipsoid, or tube. Spherical fullerenes are also called buckyballs, and they resemble the balls used in association football. Cylindrical ones are called carbon nanotubes or buckytubes...
s and their generalizations, planar graphs in which all faces are cycles with only two possible lengths...