You are here

Easy to State but Hard to Solve: Favorite Open Problems in Polyhedral Geometry

Jesus De Loera at the MAA Carriage House
Jesus De Loera

Often-heard comments about math being dead motivate Jesus De Loera to give presentations such as his contribution to MAA’s Distinguished Lecture Series in the MAA Carriage House September 20. His talk, “Easy to State but Hard to Solve: Favorite Open Problems in Polyhedral Geometry,” focused on four examples of what he called “mathematics research alive.”

De Loera studies convex polytopes. Looking at many pictures can give one a sense of these objects, but since mathematicians “like to be extremely precise and picky” about how they talk, De Loera set forth a couple of definitions: A set is convex if it contains any line segment joining two of its points, and a polytope is a bounded subset of space that results from the intersection of finitely many half-spaces. (A half-space is what you get if you slice space in two with a plane.)

The first open problem De Loera posed relates to a formula, credited to Swiss mathematician Leonhard Euler, relating a polytope’s number of vertices (V), edges (E), and faces (F): V + F - E=2. De Loera represented this result as f0 -f1 + f2 =2, adopting this less familiar notation because he would soon venture into higher dimensions and therefore wanted to think of vertices, edges, and faces all as faces, just of different dimensions (0, 1, and 2, respectively). With each three-dimensional polytope, De Loera associated a face- or f-vector (f0, f1, f2).

Given three numbers a, b, and c, one might wonder whether there exists a polytope with a vertices, b edges, and cfaces. Certainly a, b, and c must satisfy Euler’s formula if this is to be the case, but that alone is not sufficient. It wasn’t until 1906, De Loera explained, that Ernst Steinitz laid out additional conditions—two inequalities—that, if met, would guarantee the existence of a polytope with f-vector (a, b, c).

Now, although one of De Loera’s friends had hoped to do so in time for the 2006 centennial of Steinitz’s proof, no one has yet found conditions characterizing the f-vectors (f0, f1, f2, f3) of four-dimensional polytopes.

Switching gears, De Loera next shared his “favorite way to visualize polytopes.” He recalled how, as a child in Mexico, he carefully cut along the edges of a paper polyhedron such that he could unfold it flat into what is called a net.

Even child’s play, though, generates unresolved questions. “You can get your Ph.D. tomorrow,” De Loera told listeners, if you can answer the following: Given any three-dimensional polytope, is it always possible to “find a way to cut, cut, cut, and flatten it … without self-intersections”?

Noting that the mathematics of nets has unexpected applications—NASA has to figure out how to unfurl space telescopes folded for ease of transport—De Loera explained how polytopes can, under the guise of linear programming, solve optimization problems.

Maybe you need to know, given the resource requirements and profit margins of each beverage, how many barrels of ale and beer to produce to maximize monetary gain. Or perhaps you’re tasked with determining for each of several cities which of several manufacturing plants should satisfy each municipality’s laptop demand, given the cost of shipping hardware cross-country.

Watch De Loera's MAA Distinguished Lecture on YouTube

De Loera argued that polytopes, which are really just “solutions to systems of linear inequalities,” can be fruitfully brought to bear on real-world problems such as these.

Finally, perhaps inspired by being in D.C. in the fall of an election year, De Loera used the counting of lattice points—points with integer coordinates—within polytopes to address an electoral question. He calculated the probability that the voting systems used in Mexico (plurality) and France (runoff) would yield different winners in a three-candidate election (12 percent). The analogous result for a five-candidate race remains unknown, he said, since the calculations needed to derive it are too difficult for a computer to figure out.

“We need smart young people to do that,” De Loera told an audience that included college students.

“If you like math,” De Loera encouraged listeners young and old, “please talk to your friends that hate math and convince them that math is awesome.” —Katharine Merow


 Listen to the full lecture (mp3).

 Listen to an interview with Jesus De Loera and MAA Director of Publications Ivars Peterson (mp3)

Watch the lecture on YouTube.

 

This MAA Distinguished Lecture was funded by the National Security Agency.