Some Problems on Graphs and Arrangements of Convex Bodies
Abstract
Arrangements of convex bodies are ubiquitous in discrete geometry. Covering and packing problems are two major classes of problems arising from these arrangements. This thesis makes contributions to some open questions on covering a convex body by its homothetic copies and packings of translates of a convex body. The packings we study lead to the notion of a contact graph, a tool used by mathematicians, material scientists and physicists while investigating these packings. This brings a combinatorial flavour to this thesis and leads to the algorithmic question of generating graphs and hypergraphs with desired properties. We introduce the covering index of a convex body as a measure of how economically the body can be covered by a relatively few smaller positive homothetic copies. Determining the covering index can be thought of as a quantitative version of the sixty-year old Covering Conjecture in discrete and convex geometry. We prove several interesting properties of the covering index, compute its values for large classes of convex bodies and use it to devise an approach to attack the Covering Conjecture. We then consider the problem of determining the separable Hadwiger number of a smooth convex domain and the maximum contact numbers of totally separable translative packings of a smooth strictly convex domain. Both these questions have links with crystallography and self-assembly of material particles, and are completely solved here. Moreover, we show that for smooth Radon domains the extremal packings always lie on special kinds of lattices and characterize the underlying contact graphs. Next, we fully address the algorithmic questions of constructing tournaments from their imbalance sets and hypertournaments from their score sequences. The former relates to the Equal-Sum Subsets problem from computer science, while the latter is a special instance of the degree sequence problem that asks for the generation of all graphs or hypergraphs in some large class that have the same degree sequence. We characterize imbalance sets of tournaments, give an algorithm to generate tournaments from their imbalance sets and define a rapidly mixing Markov chain that uniformly samples all hypertournaments with a given score sequence.
Description
Keywords
Mathematics, Computer Science
Citation
Khan, M. A. (2017). Some Problems on Graphs and Arrangements of Convex Bodies (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/27829