|
DIMACS DCI 2002 July 18, 2002 REU Abstracts Students Jakub Cerny, Charles University,
Czech Republic Zdenek Dvorak, Charles
University, Czech Republic Vit Jelinek, Charles University,
Czech Republic Pavel Podbrdsky, Charles
University, Czech Republic Mentors Janos Komlos, Department of
Mathematics Martin Mares, Charles University
Let k, l ≥ 3 be integers. Consider two polygons in a plane
with k
and l vertices respectively. We are
interested in the problem of determining the maximum possible number of
intersections of their boundaries for given k and
l. Denote this maximum by f(k,l). When k and
l are both even, it is
easy to show that f(k,l)=kl. If k is even
and l is odd then f(k,l)=k(l
−1). However, if k and l are
both odd the problem seems extremely difficult and the exact value of
f(k,l)
is unknown. In this last case, if k ≤l then (k
−1)(l
−1) + 2 ≤ f(k,l) ≤ (k
− 1)l. The hypothesis is that the lower bound is
tight. This hypothesis is proved for the cases k=3 and k=5. In this talk we
present the methods used to improved the upper bound to obtain
f(k,l) ≤ kl − l −(k
−3)/2. Student Samuel Stechmann, University of ST.
Thomas, MN Mentor Mathew Leingang, Department of Mahtematics Hilbert’s 3rd Problem
and Hyperbolic Geometry Two polygons are scissors congruent if one of them can be cut up into
polygon pieces and put back together to form the other. Clearly if two polygons are scissors
congruent, then they have the same area.
The converse, i.e. if two polygons have the same area then they are
scissor congruent, is also true.
Hilbert’s 3rd Problem asks the analogous question in three
dimensions: If two polyhedra have the
same volume then are they scissors congruet?
Hilbert’s student Max Dehn provided a counterexample to show that
equal volume does not imply scissors congruence in Euclidean geometry. Hilbert’s 3rd Problem in hyperbolic
geometry, however, has yet to be solved. Student Yuki Saka, University of California
at Berkeley, CA Mentors Leonid Khachiyan, Department of
Computer Science
Student Paul Gross, Rose-Hulman Institute
of Technology, IN Mentors Eric Allender, Computer Science
Department A planar graph is a graph that can be drawn in the plane such that
no two edges intersect. The Planarity
Problem is to determine if a given graph is planar and if so to provide a
planar embedding of the graph. An efficient parallel algorithm for solving
the Planarity Problem will be mentioned and the project goals of the student.
|
|
|