Dushnik–Miller dimension of TD-Delaunay complexes. (August 2020)

• Record Type: Journal Article
• Authors: Gonçalves, Daniel; Isenmann, Lucas
• Is Part Of: European journal of combinatorics. Volume 88(2020)
• Publication Date: 2020-08
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103110
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: TD-Delaunay graphs, where TD stands for triangular distance, are a variation of the classical Delaunay triangulations obtained from a specific convex distance function (Chew and Drysdale, 1985). In Bonichon et al. (2010) the authors noticed that every triangulation is the TD-Delaunay graph of a set of points in R 2, and conversely every TD-Delaunay graph is planar. It seems natural to study the generalization of this property in higher dimensions. Such a generalization is obtained by defining an analogue of the triangular distance for R d . It is easy to see that TD-Delaunay complexes of R d − 1 are of Dushnik–Miller dimension d . The converse holds for d = 2 or 3 and it was conjectured to hold for larger d (Mary, 2010). Here we disprove the conjecture already for d = 4 .