REAL

On contact graphs of totally separable packings in low dimensions

Bezdek, Károly and Naszódi, Márton (2018) On contact graphs of totally separable packings in low dimensions. ADVANCES IN APPLIED MATHEMATICS, 101. pp. 266-280. ISSN 0196-8858

[img] Text
BezdekNaszodi_ContactGraphs2018.pdf
Restricted to Repository staff only

Download (403kB) | Request a copy
[img]
Preview
Text
1803.09139.pdf

Download (216kB) | Preview

Abstract

The contact graph of a packing of translates of a convex body in Euclidean d-space E-d is the simple graph whose vertices are the members of the packing, and whose two vertices are connected by an edge if the two members touch each other. A packing of translates of a convex body is called totally separable, if any two members can be separated by a hyperplane in E-d disjoint from the interior of every packing element. We give upper bounds on the maximum degree (called separable Hadwiger number) and the maximum number of edges (called separable contact number) of the contact graph of a totally separable packing of n translates of an arbitrary smooth convex body in E-d with d = 2, 3, 4. In the proofs, linear algebraic and convexity methods are combined with volumetric and packing density estimates based on the underlying isoperimetric (resp., reverse isoperimetric) inequality. (C) 2018 Elsevier Inc. All rights reserved.

Item Type: Article
Additional Information: Funding Agency and Grant Number: Natural Sciences and Engineering Research Council of Canada; National Research, Development and Innovation Office (NKFIH) [NKFI-K119670]; Hungarian Academy of Sciences; Ministry of Human Capacities [UNKP-17-4]\n Funding text: We are indebted to the anonymous referee for careful reading and valuable comments. Karoly Bezdek was partially supported by a Natural Sciences and Engineering Research Council of Canada Discovery Grant. Marton Naszodi was partially supported by the National Research, Development and Innovation Office (NKFIH) grant NKFI-K119670 and by the Janos Bolyai Research Scholarship of the Hungarian Academy of Sciences, as well as the UNKP-17-4 New National Excellence Program of the Ministry of Human Capacities.\n
Uncontrolled Keywords: NUMBER; Convex body; Contact number; Totally separable packing; Hadwiger number; Separable Hadwiger number; Contact graph; UNIT-SPHERE;
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 22 Sep 2019 16:33
Last Modified: 22 Sep 2019 16:33
URI: http://real.mtak.hu/id/eprint/100303

Actions (login required)

Edit Item Edit Item