nach oben

2018 | Buch

Kapitel lesen Erstes Kapitel lesen

Discrete Geometry and Symmetry

Dedicated to Károly Bezdek and Egon Schulte on the Occasion of Their 60th Birthdays

herausgegeben von: Prof. Marston D. E. Conder, Prof. Antoine Deza, Prof. Asia Ivić Weiss

Verlag: Springer International Publishing

Buchreihe : Springer Proceedings in Mathematics & Statistics

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book consists of contributions from experts, presenting a fruitful interplay between different approaches to discrete geometry. Most of the chapters were collected at the conference “Geometry and Symmetry” in Veszprém, Hungary from 29 June to 3 July 2015. The conference was dedicated to Károly Bezdek and Egon Schulte on the occasion of their 60th birthdays, acknowledging their highly regarded contributions in these fields.
While the classical problems of discrete geometry have a strong connection to geometric analysis, coding theory, symmetry groups, and number theory, their connection to combinatorics and optimization has become of particular importance. The last decades have seen a revival of interest in discrete geometric structures and their symmetry. The rapid development of abstract polytope theory has resulted in a rich theory featuring an attractive interplay of methods and tools from discrete geometry, group theory and geometry, combinatorial group theory, and hyperbolic geometry and topology. This book contains papers on new developments in these areas, including convex and abstract polytopes and their recent generalizations, tiling and packing, zonotopes, isoperimetric inequalities, and on the geometric and combinatorial aspects of linear optimization. The book is a valuable resource for researchers, both junior and senior, in the field of discrete geometry, combinatorics, or discrete optimization. Graduate students find state-of-the-art surveys and an open problem collection.

Inhaltsverzeichnis

Frontmatter

The Geometry of Homothetic Covering and Illumination

Abstract

At a first glance, the problem of illuminating the boundary of a convex body by external light sources and the problem of covering a convex body by its smaller positive homothetic copies appear to be quite different. They are in fact two sides of the same coin and give rise to one of the important longstanding open problems in discrete geometry, namely, the Illumination Conjecture. In this paper, we survey the activity in the areas of discrete geometry, computational geometry and geometric analysis motivated by this conjecture. Special care is taken to include the recent advances that are not covered by the existing surveys. We also include some of our recent results related to these problems and describe two new approaches – one conventional and the other computer-assisted – to make progress on the illumination problem. Some open problems and conjectures are also presented.

Károly Bezdek, Muhammad A. Khan

Stability of the Simplex Bound for Packings by Equal Spherical Caps Determined by Simplicial Regular Polytopes

Abstract

It is well known that the vertices of any simplicial regular polytope in \(\mathbb R^d\) determine an optimal packing of equal spherical balls in \(S^{d-1}\). We prove a stability version of optimal order of this result.

Károly Böröczky, Károly J. Böröczky, Alexey Glazyrin, Ágnes Kovács

Vertex-Transitive Haar Graphs That Are Not Cayley Graphs

Abstract

In a recent paper in Electron. J. Combin. 23 (2016), Estélyi and Pisanski raised a question whether there exist vertex-transitive Haar graphs that are not Cayley graphs. In this note we construct an infinite family of trivalent Haar graphs that are vertex-transitive but non-Cayley. The smallest example has 40 vertices and is the well-known Kronecker cover over the dodecahedron graph G(10, 2), occurring as the graph ‘40’ in the Foster census of connected symmetric trivalent graphs.

Marston D. E. Conder, István Estélyi, Tomaž Pisanski

On the Volume of Boolean Expressions of Large Congruent Balls

Abstract

We consider the volume of a Boolean expression of some congruent balls about a given system of centers in the d-dimensional Euclidean space. When the radius r of the balls is large, this volume can be approximated by a polynomial of r, which will be computed up to an \(O(r^{d-3})\) error term. We study how the top coefficients of this polynomial depend on the set of the centers. It is known that in the case of the union of the balls, the top coefficients are some constant multiples of the intrinsic volumes of the convex hull of the centers. Thus, the coefficients in the general case lead to generalizations of the intrinsic volumes, in particular, to a generalization of the mean width of a set. Some known results on the mean width, along with the theorem on its monotonicity under contractions are extended to the “Boolean analogues” of the mean width.

Balázs Csikós

Small Primitive Zonotopes

Abstract

We study a family of lattice polytopes, called primitive zonotopes, describe instances with small parameters, and discuss connections to the largest diameter of lattice polytopes and to the computational complexity of multicriteria matroid optimization. Complexity results and open questions are also presented.

Antoine Deza, George Manoussakis, Shmuel Onn

Delone Sets: Local Identity and Global Symmetry

Abstract

In the paper we present a proof of the local criterion for crystalline structures which generalizes the local criterion for regular systems. A Delone set is called a crystal if it is invariant with respect to a crystallographic group. Locally antipodal Delone sets, i.e. those in which all 2R-clusters are centrally symmetrical, are considered and we prove that they have crystalline structure. Moreover, if in a locally antipodal set all 2R-clusters are the same, then the set is a regular system, i.e. a Delone set whose symmetry group operates transitively on the set.

Nikolay Dolbilin

The Twist Operator on Maniplexes

Abstract

Maniplexes are combinatorial objects that generalize, simultaneously, maps on surfaces and abstract polytopes. We are interested on studying highly symmetric maniplexes, particularly those having maximal ‘rotational’ symmetry. This paper introduces an operation on polytopes and maniplexes which, in its simplest form, can be interpreted as twisting the connection between facets. This is first described in detail in dimension 4 and then generalized to higher dimensions. Since the twist on a maniplex preserves all the orientation preserving symmetries of the original maniplex, we apply the operation to reflexible maniplexes, to attack the problem of finding chiral polytopes in higher dimensions.

Ian Douglas, Isabel Hubard, Daniel Pellicer, Steve Wilson

Hexagonal Extensions of Toroidal Maps and Hypermaps

Abstract

The rank 3 concept of a hypermap has recently been generalized to a higher rank structure in which hypermaps can be seen as “hyperfaces” but very few examples can be found in literature. We study finite rank 4 structures obtained by hexagonal extensions of toroidal hypermaps. Many new examples are produced that are regular or chiral, even when the extensions are polytopal. We also construct a new infinite family of finite nonlinear hexagonal extensions of the tetrahedron.

Maria Elisa Fernandes, Dimitri Leemans, Asia Ivić Weiss

Noncongruent Equidissections of the Plane

Abstract

Nandakumar asked whether there is a tiling of the plane by pairwise non-congruent triangles of equal area and equal perimeter. Here a weaker result is obtained: there is a tiling of the plane by pairwise non-congruent triangles of equal area such that their perimeter is bounded by some common constant. Several variants of the problem are stated, some of them are answered.

D. Frettlöh

Pascal’s Triangle of Configurations

Abstract

We introduce an infinite class of configurations which we call Desargues–Cayley–Danzer configurations. The term is motivated by the fact that they generalize the classical \((10_3)\) Desargues configuration and Danzer’s \((35_4)\) configuration; moreover, their construction goes back to Cayley. We show that these configurations can be arranged in a triangular array which resembles the classical Pascal triangle also in the sense that it can be recursively generated. As an interesting consequence, we show that all these configurations are connected to incidence theorems, like in the classical case of Desargues. We also show that these configurations can be represented not only by points and lines, but points and circles, too.

Gábor Gévay

Volume of Convex Hull of Two Bodies and Related Problems

Abstract

In this paper we deal with problems concerning the volume of the convex hull of two “connecting” bodies. After a historical background we collect some results, methods and open problems, respectively.

Ákos G. Horváth

Integers, Modular Groups, and Hyperbolic Space

Abstract

In each of the normed division algebras over the real field \(\mathbb {R}\)—namely, \(\mathbb {R}\) itself, the complex numbers \(\mathbb {C}\), the quaternions IH, and the octonions \(\mathbb {O}\)—certain elements can be characterized as integers. An integer of norm 1 is a unit. In a basic system of integers the units span a 1-, 2-, 4-, or 8-dimensional lattice, the points of which are the vertices of a regular or uniform Euclidean honeycomb. A modular group is a group of linear fractional transformations whose coefficients are integers in some basic system. In the case of the octonions, which have a nonassociative multiplication, such transformations form a modular loop. Each real, complex, or quaternionic modular group can be identified with a subgroup of a Coxeter group operating in hyperbolic space of 2, 3, or 5 dimensions.

Norman W. Johnson

Monge Points, Euler Lines, and Feuerbach Spheres in Minkowski Spaces

Abstract

It is surprising, but an established fact that the field of elementary geometry referring to normed spaces (= Minkowski spaces) is not a systematically developed discipline. There are many natural notions and problems of elementary and classical geometry that were never investigated in this more general framework, although their Euclidean subcases are well known and this extended viewpoint is promising. An example is the geometry of simplices in non-Euclidean normed spaces; not many papers in this direction exist. Inspired by this lack of natural results on Minkowskian simplices, we present a collection of new results as non-Euclidean generalizations of well-known fundamental properties of Euclidean simplices. These results refer to Minkowskian analogues of notions like Euler line, Monge point, and Feuerbach sphere of a simplex in a normed space. In addition, we derive some related results on polygons (instead of triangles) in normed planes.

Undine Leopold, Horst Martini

An Algorithm for Classification of Fundamental Polygons for a Plane Discontinuous Group

Abstract

Based on the procedure given in [15] we describe an algorithm, implemented in a computer program, for complete enumeration of combinatorial equivalence classes of fundamental polygons for any fixed plane discontinuous group given by its signature. This is a solution of a long standing problem, we call it Poincaré-Delone problem to honour of Henry Poincaré and Boris Nikolaevich Delone (Delaunay). We give examples and computations together with some complete lists of combinatorially different polygons which serve as fundamental domains for the groups with the Macbeath signatures, e.g. \((2,+,[\ ];\{\,\})\),\((3,-,[\ ];\{\,\})\) and \((3,+,[\ ];\{\,\})\).

Zoran Lučić, Emil Molnár, Nebojša Vasiljević

Self-inscribed Regular Hyperbolic Honeycombs

Abstract

This paper describes ways that certain regular honeycombs of non-finite type in d-dimensional hyperbolic space \(\mathbb {H}^d\) for \(d = 2,3\) and 5 can be inscribed in others, in particular showing that some can be inscribed properly in copies of themselves.

Peter McMullen

Sphere-of-Influence Graphs in Normed Spaces

Abstract

We show that any k-th closed sphere-of-influence graph in a d-dimensional normed space has a vertex of degree less than \(5^d k\), thus obtaining a common generalization of results of Füredi and Loeb (Proc Am Math Soc 121(4):1063–1073, 1994 [1]) and Guibas et al. (Sphere-of-influence graphs in higher dimensions, Intuitive geometry [Szeged, 1991], 1994, pp. 131–137 [2]).

Márton Naszódi, János Pach, Konrad Swanepoel

On Symmetries of Projections and Sections of Convex Bodies

Abstract

In this paper we discuss several questions of unique determination of convex (or star-shaped) bodies with projections (sections) satisfying a certain symmetry property.

Dmitry Ryabogin

Regular Incidence Complexes, Polytopes, and C-Groups

Abstract

Regular incidence complexes are combinatorial incidence structures generalizing regular convex polytopes, regular complex polytopes, various types of incidence geometries, and many other highly symmetric objects. The special case of abstract regular polytopes has been well-studied. The paper describes the combinatorial structure of a regular incidence complex in terms of a system of distinguished generating subgroups of its automorphism group or a flag-transitive subgroup. Then the groups admitting a flag-transitive action on an incidence complex are characterized as generalized string C-groups. Further, extensions of regular incidence complexes are studied, and certain incidence complexes particularly close to abstract polytopes, called abstract polytope complexes, are investigated.

Egon Schulte

Titel: Discrete Geometry and Symmetry
herausgegeben von: Prof. Marston D. E. Conder
Prof. Antoine Deza
Prof. Asia Ivić Weiss
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-78434-2
Print ISBN: 978-3-319-78433-5
DOI: https://doi.org/10.1007/978-3-319-78434-2