We derive lower bounds for the size of simplicial covers of simplotopes,
which are products of simplices. These also serve as lower bounds for
triangulations of such polytopes, including triangulations with interior
vertices. We establish that a minimal triangulation of a product of two
simplices is given by a vertex triangulation, i.e., one without interior
vertices. For products of more than two simplices, we produce bounds for
products of segments and triangles.
We derive lower bounds for the size of simplicial covers of simplotopes,
which are products of simplices. These also serve as lower bounds for
triangulations of such polytopes, including triangulations with interior
vertices. We establish that a minimal triangulation of a product of two
simplices is given by a vertex triangulation, i.e., one without interior
vertices. For products of more than two simplices, we produce bounds for
products of segments and triangles.
The classical Lusternik-Schnirelman-Borsuk theorem states that if a d-sphere
is covered by d+1 closed sets, then at least one of the sets must contain a
pair of antipodal points. In this paper, we prove a combinatorial version of
this theorem for hypercubes. It is not hard to show that for any cover of the
facets of a d-cube by d sets of facets, at least one such set contains a pair
of antipodal ridges.
In this paper we prove a new combinatorial theorem for labellings of trees,
and show that it is equivalent to a KKM-type theorem for finite covers of trees
and to discrete and continuous fixed point theorems on finite trees. This is in
analogy with the equivalence of the classical Sperner's lemma, KKM lemma, and
the Brouwer fixed point theorem on simplices. Furthermore, we use these ideas
to develop new KKM and fixed point theorems for infinite covers and infinite
trees.
What is the period of the Fibonacci sequence modulo a prime? The purpose of
our brief expository paper is to illustrate an accessible, motivated treatment
of this classical topic using only ideas from linear and abstract algebra
(rather than the case-by-case analysis found in many papers on the subject, or
techniques from graduate number theory). Our methods extend to general
recurrences with prime moduli and provide some new insights.
In contrast to the classical cake-cutting problem (how to fairly divide a
desirable object), "chore division" is the problem of how to divide an
undesirable object. We develop the first explicit algorithm for envy-free chore
division among N people, a counterpart to the N-person envy-free cake-division
solution of Brams-Taylor (1995). This is accomplished by exploiting a notion of
"irrevocable advantage" for chores. We discuss the differences between
cake-cutting and chore division and additional problems encountered in chore
division.
We introduce a generalized cake-cutting problem in which we seek to divide
multiple cakes so that two players may get their most-preferred piece
selections: a choice of one piece from each cake, allowing for the possibility
of linked preferences over the cakes. For two players, we show that disjoint
envy-free piece selections may not exist for two cakes cut into two pieces
each, and they may not exist for three cakes cut into three pieces each.
However, there do exist such divisions for two cakes cut into three pieces
each, and for three cakes cut into four pieces each.