


Discrete and Convex Geometry
Org: Karoly Bezdek (Calgary) and Jozsef Solymosi (UBC) [PDF]
 KAROLY BEZDEK, University of Calgary, 2500 University Drive NW, Calgary,
Alberta T2N 1N4
Antipodality revisited
[PDF] 
Antipodality is an important concept in discrete geometry with a
variety of meanings. The talk surveys some of the most recent
developments.
 KAROLY BOROCZKY, Eotvos University, Budapest, Pazmany Peter s. 1/C, 1117 Hungary
Transversals of hyperbolic disks
[PDF] 
According to the classical result of Hadwiger, if any three discs have
a transversal in an infinite packing of congruent disks in the
Euclidean plane then the whole family has a transversal. I prove that
if any three sets have a transversal in an infinite packing of
connected sets with uniformly bounded diameters in the hyperbolic
plane then the whole family has a transversal.
Next, Danzer verified that if any five discs have a transversal in a
finite packing of congruent disks in the Euclidean plane then the
whole family has a transversal. I prove the analogous statement in
the hyperbolic plane for disks and for horodisks. In addition I
exhibit packings of arbitrary finite number of congruent disks in the
hyperbolic plane such that any four has a transversal but the whole
family has not. Moreover we exhibit packings of arbitrary finite
number of congruent disks in the hyperbolic plane such that any three
has a transversal but removing any disk from the family, even the rest
has no transversal.
 BOB ERDAHL, Queen's University
Delaunay Polytopes and the Pauli Principle
[PDF] 
Consider the integer lattice Z^{d}, and a lattice polytope P in
Z^{d}. Then, P is Delaunay if it can be circumscribed by an empty
ellipsoid E, where there are no lattice points interior to E, and
the only Z^{d}elements on the boundary are the vertices of P. The
empty ellipsoid E determines an inhomogeneous quadratic function up
to a scale factor. In general there are many empty ellipsoids that
circumscribe P, each determining a single ray of quadratic
functions. The collection of all such rays is a relatively open cone
of quadratic functions, the inhomogeneous domain D(P), of the
Delaunay polytope P.
If the vertices of P are (0,1)vectors, then these can be
interpreted as giving partial information on a quantum system of
electrons that are distributed amongst d oneparticle states. Each
(0,1)vector is a vector of occupation numbers, component k
telling whether state k is occupied or unoccupied; the occupation
numbers are limited to 0 or 1 by the Pauli principle. By taking
averages we have a more general situation; the components belong to
the unit interval and give the probability that state k is occupied.
With this quantum interpretation each quadratic function in the domain
D(P) corresponds to a Hamiltonian operator on the state space of the
quantum system, and the vertices of the Delaunay polytope label a
basis for the degenerate ground state of this Hamiltonian.
Besides the probability distribution for the electrons, it is also
useful to determine the joint probability distributions for pairs of
electrons, and possibly even higher order distributions of electrons.
I will describe how pair probability distributions can be described
within the present framework, and how the convex set of all pair
probability distributions can be described using the family of
operators corresponding to the elements of D(P). I will relate this
discussion to some questions in quantum information theory.
 FERENC FODOR, University of Szeged, Bolyai Institute, 1 Aradi vértanúk
tere, 6720 Szeged, Hungary
Lower bounds on the surface area of Voronoi polyhedra
[PDF] 
One of the most beautiful problems related to 3dimensional unit
ball packings is the Dodecahedral Conjecture formulated by L. Fejes
Tóth in 1943. It states that the minimal volume of a Voronoi cell
in a 3dimensional unit ball packing is at least as large as the
volume of a regular dodecahedron of inradius 1. This problem has
been recently settled in the affirmative by Hales and McLaughlin.
K. Bezdek phrased the following generalized version of the
Dodecahedral Conjecture in 2000. Strong Dodecahedral Conjecture: The
minimum surface area of a Voronoi cell in a unit ball packing in
E^{3} is at least as large as the surface area of the
regular dodecahedron circumscribed about the unit ball.
In this talk, I will present a construction which yields a lower bound
on the surface area of the Voronoi polyhedron. This result improves
on existing lower bounds and provides further support for the Strong
Dodecahedral Conjecture.
This work is joint with Gergely Ambrus.
 MARINA GAVRILOVA, University of Calgary, 2500 University Drive NW, Calgary,
AB T2N 1N4
Exact Point Location in Generalized Voronoi Diagram
[PDF] 
The talk is devoted to the problem of exact pointlocation in a
generalized ddimensional Voronoi Diagram in the Euclidean space.
The exact point location problem typically requires the solution for
expressions of degree four. An approximation of the solution using
using expression of a smaller degree is possible through polyhedral
metrics. In general dimensions two Minkowski metrics can be used
(Manhattan and supremum). The computation uses degree one. We also
show that a polygonal metric can be applied in two dimensions. The
computation involves only O(lg k) calls of the algorithm ESSA for
detecting the sign of a sum using floatingpoint arithmetic.
 MOHAMMAD GHOMI, Georgia Institute of Technology, Atlanta, Georgia 30308
Isoperimetric inequality outside convex bodies
[PDF] 
We prove that the area of a hypersurface which traps a given volume
outside of a convex body in Euclidean nspace must be greater than
or equal to the area of a hemisphere trapping the given volume on one
side of a hyperplane. This result generalizes the classical
isoperimetric inequality. The proof rests on a sharp estimate for
total positive curvature of a hypersurface whose boundary lies on a
convex body and meets that body orthogonally.
This is joint work with J. Choe and M. Ritore.
 LUIS GODDYN, Simon Fraser University
Logdiscrepancy and chromatic number of hyperplane
arrangements
[PDF] 
To sign an arrangement of affine hyperplanes in R^{d} is to to
designate, for each hyperplane, one of its two sides as being
"positive". A vertex is any intersection of d affinely
independent hyperplanes. We seek a signing for which each vertex lies
in the positive side of about 50% of the hyperplanes not containing
the vertex. This differs from "discrepancy theory", where the goal
is to minimize the difference rather than the ratio
between the number of positive and negative sides containing each
vertex. Hence the phrase "logdiscrepancy" in the title.
An old formula of Minty expresses the (circular) chromatic number of a
graph in terms of finding a signing of low logdiscrepancy in an
associated complex. This motivates the invariant we study here. It
also allows us to define a "chromatic number" for any hyperplane
arrangement and, more generally, for any oriented matroid.
Using a probabilistic argument, we prove that the chromatic number of
any loopless oriented matroid is bounded above by a function of its
corank. This generalizes the observation that the chromatic number of
a loopless connected graph (V,E) is bounded above (approximately) by
the square root of its Beti number E  V + 1.
This is joint work with P. Hlineny and W. Hochstaettler.
 BRANKO GRÜNBAUM, University of Washington, Seattle, WA 981954350, USA
Enumeration of squarefaced isogonal infinite polyhedra
[PDF] 
The three wellknown CoxeterPetrie polyhedra are examples of regular
infinite polyhedra with convex faces. This means that the symmetry
group of each acts transitively on its flags, which implies that all
faces are congruent regular polygons and that all vertices are
equivalent under symmetries of the polyhedron. In the finite case the
implication can be reversed resulting in the five Platonic solids.
Not so in the infinite case. Adding to previously known results for
the infinite case, obtained by various authors, we completely
enumerate the infinite polyhedra with square faces, with adjacent
faces either coplanar or perpendicular, and with all vertices
equivalent under symmetries. There are precisely 15 such polyhedra in
which each vertex is incident with five squares, and 6 in which each
is incident with six. These enumerations are accomplished via a
combination of combinatorial and geometric calculations, both manual
and computerized, along with computer graphics visualizations of the
polyhedra. The method can be used in more general situations as well.
The work is a collaboration of Steven Gillispie and the presenter,
both at the University of Washington.
 ALADAR HEPPES, Eotvos, Budapest, Hungary
Neartransversal lines in families of congruent circles
[PDF] 
Let F be a family of congruent circles. We say that F has
property T(3) if every triple of its members has a line transversal.
In 1980, Katchalski and Lewis proved the existence of a constant m
such that in every T(3)family of disjoint congruent discs there is
a line intersecting all but at most m of the discs. A family of
congruent circles of unit diameter is said to be tdisjoint if the
distance of every pair of the circles is larger than t. We have two
generalizations of the above mentioned KatchalskiLewis theorem:
(1) The theorem holds with the conjectured m = 2.
(2) The theorem holds for tdisjoint families as well: To
every t > 0 there exists a constant m(t) such that in every
T(3)family of tdisjoint congruent discs there is a line
intersecting all but at most m(t) of the discs.
 GYORGY KISS, Eötvös Loránd University, 1117 Budapest, Pázmány
s. 1/c, Hungary and University of Szeged, 6720 Szeged, Aradi
vértanúk t. 1, Hungary
On the illumination parameters of convex bodies
[PDF] 
Let K be a convex body of E^{d}. We say that a
point, i.e., a lightsource l, illuminates the boundary
point p of K if the halfline starting at l and
passing through p intersects the interior of K.
Furthermore we say that the lightsources {l_{1},l_{2},...} Ì E^{d} \K illuminate K if each
of its boundary points is illuminated by at least one of the
lightsources {l_{1},l_{2},...}. The wellknown illumination
conjecture of Hadwiger (1960) says that any ddimensional convex
body can be illuminated by 2^{d} lightsources. In this talk we
consider some quantitative versions of Hadwiger's problem. If
B is a centrally symmetric body about the origin o of
E^{d}, then let the illumination parameter of B be defined as
b(B) = 
inf
 
ì í
î


å
i

d(o,l_{i}) : {l_{i}} illuminates B 
ü ý
þ

. 

This ensures that faraway lightsources are penalised. K. Bezdek
proved (1992) that b(B) < 6 holds in E^{2}. He
also proved (2005) that b(B) = 6Ö3 if B
is the unit ball E^{3}.
We prove some theorems about the illumination parameters in E^{3}, and give some possible generalizations in E^{d},
when we consider the illumination by rdimensional linear
lightsources instead of points.
 KEE YUEN LAM, University of British Columbia
The combinatorics of sums of squares as studied via topology
[PDF] 
Historically, the wellknown identity
(x_{1}^{2} + x_{2}^{2}) (y_{1}^{2} + y_{2}^{2}) = (x_{1} y_{1}  x_{2} y_{2})^{2} + (x_{1} y_{2} +x_{2} y_{1})^{2} 

had led to a "sums of square" problem, namely to determine all
identities of the type
(x_{1}^{2} + ... + x_{r}^{2}) (y_{1}^{2} + ... + y_{s}^{2}) = f_{1}^{2} + ... +f_{n}^{2} 

where f_{1},...,f_{n} belong to a polynomial ring L[x_{1},...,x_{r}; y_{1},...,y_{s}]. In this generality the problem
remains wide open. For the case when the commutative ring L
is Z, it reduces to a question of discrete mathematics,
involving "signed intercalate matrices". In this talk I shall
explain what intercalate matrices are, and show how ideas from
algebraic topology can be used in the study of the combinatorics of
such matrices.
 HIROSHI MAEHARA, University of the Ryukyus, Nishihara, Okinawa, 9030213
Japan
Reversing a polyhedral surface
[PDF] 
We introduce a new variety of flexatube, a rhomboflexatube.
It is obtained from a cardboard rhombohedron by removing a pair of
opposite faces (rhombi), and then subdividing the remaining four faces
by pairs of diagonals. It is reversible, that is, it can be turned
inside out by a series of folds, using edges and diagonals of the
rhombi. To turn a rhomboflexatube inside out is quite a challenging
puzzle. We also consider the reversibility of general polyhedral
surfaces. We show that if an orientable polyhedral surface with
boundary is reversible, then its genus is 0 and for every interior
vertex, the sum of face angles at the vertex is at least 2p.
After defining tubeattachment operation, we show that every
polyhedral surface obtained from a rectangular tube by applying
tubeattachment operations one after another can be subdivided so that
it becomes reversible.
 EGON SCHULTE, Northeastern University, Department of Mathematics, Boston,
MA 02115
Local Theorems in Combinatorial Tiling
[PDF] 
A locally finite facetoface tiling of euclidean dspace by convex
dpolytopes is said to be combinatorially crystallographic if its
combinatorial automorphism group has only finitely many orbits on the
tiles. We describe a new Local Theorem, which characterizes
combinatorially crystallographic tilings in terms of large enough
neighborhood complexes (centered coronas) of tiles. This generalizes
the Local Theorem for Monotypic Tilings, which gives necessary and
sufficient conditions for combinatorial tiletransitivity.
Both results are joint work with Nikolai Dolbilin.
 JOZSEF SOLYMOSI, University of British Columbia
The geometry of Schur's theorem
[PDF] 
One of the first results in additive combinatorics belongs to I. Schur
and dates back to 1916. His motivation was to study "the local
version" of the famous equation of Fermat: x^{n}+y^{n} = z^{n}. If there
are integers x, y, z satisfying the above equation, then for
every prime p, they also solve the congruence equation: x^{n} + y^{n} º z^{n} (mod p). He showed that the congruence equation has a
nontrivial solution for all large primes p. This result follows
from the next result, known as Schur's Theorem:
Let r > 1. Then there is a natural number S(r), such as
if N > S(r) and if the numbers {1,2,...,N} are coloured with
r colours, then there are three of them x, y, z of the same
colour satisfying the equation: x + y = z.
We will give a geometriccombinatorial proof for Schur's Theorem and
extend it, to prove a density version, similar to Roth's theorem for
3term arithmetic progressions.
 CSABA D. TOTH, MIT, Cambridge, MA 02144
Spanning trees for disjoint barriers in threespace
[PDF] 
Given n point sites and a set of disjoint barriers in threespace,
we wish to connect the sites with a straight line spanning tree such
that no barrier intersects "too many" edges of the tree. We show
that if the barriers are convex 2dimensional objects of bounded
description complexity, then there is a spanning tree such that every
barrier cuts at most [(O)\tilde](Ön) of its edges. If the
barriers are axisaligned rectangles, then there is a spanning tree
such that every rectangle cuts at most O(n^{1/3}) of its edges.
Both bounds are asymptotically optimal.
Joint work with Eynat Rafalin and Diane Souvaine.
 ASIA IVIC WEISS, York University, 4700 Keele St., Toronto, Ontario
PetrieCoxeter maps revisited
[PDF] 
A technique is presented for constructing new chiral or regular
polyhedra (or maps) from selfdual abstract polytopes of rank 4. From
improperly selfdual chiral polytopes we derive
"PetrieCoxetertype" polyhedra (abstract chiral analogues of the
classical PetrieCoxeter polyhedra) and investigate their groups of
automorphisms.

