Source author record

Michel Deza

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.MG Discrete Mathematics Information Theory math.GT math.IT

Catalog footprint

Research overview

11works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

On the lengths of zigzags in thin complexes

We consider zigzags in thin complexes. The main result states that the sum of the lengths of all zigzags in an $n$ -complexe is equal to the sum of the lengths of all zigzags in all $(n-1)$ -faces of this complex, and this sum also is the twice of the sum of the lengths of all zigzags in all $(n-2)$ -faces. For simplicial and cubical $n$ -complexes, the sum depends on the rank $n$ and the number of $(n-1)$ -faces only. We also describe the sum of the lengths of all generalized zigzags, it depends on the rank and the number of flags. As an application, we find the number of zigzags in Coxeter complexes.

preprint2015arXiv

Enumeration of the facets of cut polytopes over some highly symmetric graphs

We report here a computation giving the complete list of facets for the cut polytopes over several very symmetric graphs with $15-30$ edges, including $K_8$ , $K_{3,3,3}$ , $K_{1,4,4}$ , $K_{5,5}$ , some other $K_{l,m}$ , $K_{1,l,m}$ , $Prism_7, APrism_6$ , Möbius ladder $M_{14}$ , Dodecahedron, Heawood and Petersen graphs. For $K_8$ , it shows that the huge lists of facets of the cut polytope $CUTP_8$ and cut cone $CUT_8$ , given in [CR] is complete. We also confirm the conjecture that any facet of $CUTP_8$ is adjacent to a triangle facet. The lists of facets for $K_{1,l,m}$ with $(l,m)=(4,4),(3,5),(3,4)$ solve problems (see, for example, [Werner]) in quantum information theory.

preprint2015arXiv

Hypercube emulation of interconnection networks topologies

We address various topologies (de Bruijn, chordal ring, generalized Petersen, meshes) in various ways ( isometric embedding, embedding up to scale, embedding up to a distance) in a hypercube or a half-hypercube. Example of obtained embeddings: infinite series of hypercube embeddable Bubble Sort and Double Chordal Rings topologies, as well as of regular maps.

preprint2015arXiv

The hypermetric cone on $8$ vertices and some generalizations

The lists of facets -- $298,592$ in $86$ orbits -- and of extreme rays -- $242,695,427$ in $9,003$ orbits -- of the hypermetric cone $HYP_8$ are computed. The first generalization considered is the hypermetric polytope $HYPP_n$ for which we give general algorithms and a description for $n\le 8$ . Then we shortly consider generalizations to simplices of volume higher than $1$ , hypermetric on graphs and infinite dimensional hypermetrics.

preprint2015arXiv

The joint weight enumerator of an LCD code and its dual

A binary linear code is called {\em LCD} if it intersects its dual trivially. We show that the coefficients of the joint weight enumerator of such a code with its dual satisfy linear constraints, leading to a new linear programming bound on the size of an LCD code of given length and minimum distance. In addition, we show that this polynomial is, in general, an invariant of a matrix group of dimension $4$ and order $12$ . Also, we sketch a Gleason formula for this weight enumerator.

preprint2013arXiv

Voronoi Polytopes for Polyhedral Norms on Lattices

A polyhedral norm is a norm N on R^n for which the set N(x)\leq 1 is a polytope. This covers the case of the L^1 and L^{\infty} norms. We consider here effective algorithms for determining the Voronoi polytope for such norms with a point set being a lattice. The algorithms, that we propose, use the symmetries effectively in order to compute a decomposition of the space into convex polytopes named {\em $VN$ -spaces}. The Voronoi polytopes and other geometrical information are easily obtained from it.

preprint2012arXiv

Cones of weighted quasi-metrics, weighted quasi-hypermetrics and of oriented cuts

We show that the cone of weighted n-point quasi-metrics WQMet_n, the cone of weighted quasi-hypermetrics WHyp_n and the cone of oriented cuts OCut_n are projec- tions along an extreme ray of the metric cone Metn+1, of the hypermetric cone Hypn+1 and of the cut cone Cut_{n+1}, respectively. This projection is such that if one knows all faces of an original cone then one knows all faces of the projected cone.

preprint2011arXiv

Cones of Weighted and Partial Metrics

A partial semimetric on V_n={1, ..., n} is a function f=((f_{ij})): V_n^2 -> R_>=0 satisfying f_ij=f_ji >= f_ii and f_ij+f_ik-f_jk-f_ii >= 0 for all i,j,k in V_n. The function f is a weak partial semimetric if f_ij >= f_ii is dropped, and it is a strong partial semimetric if f_ij >= f_ii is complemented by f_ij <= f_ii+f_jj. We describe the cones of weak and strong partial semimetrics via corresponding weighted semimetrics and list their 0,1-valued elements, identifying when they belong to extreme rays. We consider also related cones, including those of partial hypermetrics, weighted hypermetrics, l_1-quasi semimetrics and weighted/partial cuts.

preprint2011arXiv

Fullerene-like spheres with faces of negative curvature

Given R\subset N, an (R,k) $-sphere is a k-regular map on the sphere whose faces have gonalities i\in R. The most interesting/useful are (geometric) fullerenes, i.e., (\{5,6\},3)$ -spheres. Call κ_i=1 + \frac{i}{k} - \frac{i}{2} the curvature of i-gonal faces. (R,k)-spheres admitting κ_i<0 are much harder to study. We consider the symmetries and construction for three new instances of such spheres: ({a,b},k)-spheres with p_b\le 3 (they are listed), icosahedrites (i.e., ({3,4},5)$-spheres) and, for any c\in N, fullerene c-disks, i.e., ({5,6,c},3)-spheres with p_c=1.

preprint2010arXiv

({2,3}, 6)-spheres and their generalizations

We consider here 6-regular plane graphs whose faces have size 1, 2 or 3. In Section 2 a practical enumeration method is given that allowed us to enumerate them up to 53 vertices. Subsequently, in Section 3 we enumerate all possible symmetry groups of the spheres that showed up. In Section 4 we introduce a new Goldberg-Coxeter construction that takes a 6-regular plane graph G0, two integers k and l and returns two 6-regular plane graphs. Then in the final section, we consider the notions of zigzags and central circuits for the considered graphs. We introduced the notions of tightness and weak tightness for them and we prove an upper bound on the number of zigzags and central circuits of such tight graphs. We also classify the tight and weakly tight graphs with simple zigzags or central circuits.

preprint2010arXiv

Enumeration of Hamiltonian Cycles in 6-cube

Finding the number 2H6 of directed Hamiltonian cycles in 6-cube is problem 43 in Section 7.2.1.1 of Knuth's ' The Art of Computer Programming'; various proposed estimates are surveyed below. We computed exact value: H6=14,754,666,508,334,433,250,560=6*2^4*217,199*1,085,989*5,429,923. Also the number Aut6 of those cycles up to automorphisms of 6-cube was computed as 147,365,405,634,413,085

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Michel Deza

Research overview

Is this your work?

11 publications

On the lengths of zigzags in thin complexes

Enumeration of the facets of cut polytopes over some highly symmetric graphs

Hypercube emulation of interconnection networks topologies

The hypermetric cone on $8$ vertices and some generalizations

The joint weight enumerator of an LCD code and its dual

Voronoi Polytopes for Polyhedral Norms on Lattices

Cones of weighted quasi-metrics, weighted quasi-hypermetrics and of oriented cuts

Cones of Weighted and Partial Metrics

Fullerene-like spheres with faces of negative curvature

({2,3}, 6)-spheres and their generalizations

Enumeration of Hamiltonian Cycles in 6-cube

See the researcher in context

Building this map preview

Michel Deza

Research overview

Is this your work?

11 publications

On the lengths of zigzags in thin complexes

Enumeration of the facets of cut polytopes over some highly symmetric graphs

Hypercube emulation of interconnection networks topologies

The hypermetric cone on 888 vertices and some generalizations

The joint weight enumerator of an LCD code and its dual

Voronoi Polytopes for Polyhedral Norms on Lattices

Cones of weighted quasi-metrics, weighted quasi-hypermetrics and of oriented cuts

Cones of Weighted and Partial Metrics

Fullerene-like spheres with faces of negative curvature

({2,3}, 6)-spheres and their generalizations

Enumeration of Hamiltonian Cycles in 6-cube

See the researcher in context

Building this map preview

The hypermetric cone on $8$ vertices and some generalizations