Mathematics & Statistics Department

A cubical complex is CAT(0) if it has global non-positive curvature; informally, "all its triangles are thin". These complexes play an important role in pure mathematics (group theory) and in applications (phylogenetics, robot motion planning, etc.). In particular, as Abrams and Ghrist observed, when one studies the possible states of a discrete robot, one often finds that they naturally form a CAT(0) cube complex.

Gromov gave a remarkable topological/combinatorial characterization of CAT(0) cube complexes. We give an alternative, purely combinatorial description of them, allowing a number of applications. In particular, for many robots, we can use these tools to find the fastest way to move from one position to another one.

The talk will describe joint work with Tia Baker, Megan Owen, Seth Sullivant, and Rika Yatchak. It will require no previous knowledge of the subject, and be accessible to undergraduate students.

You can do this in many ways. You can even arrange for all the triangles have exactly the same area. However, an old theorem (1970) of Paul Monsky asserts that it is impossible to cut a square into an odd number of triangles of equal area.  The proof of this theorem is a delightful blend of geometry, combinatorics, and number theory. This aim of this talk is to prove Monsky’s Theorem and understand some of the geometrical, combinatorial, and algebraic ingredients that go into its proof.

The talk may also serve as motivation for Aaron Abrams’s talk next week (October 2), in which Aaron will probably discuss a current research project which grew out of a desire to better understand Monsky’s Theorem.

This will be a sequel to Jamie's talk from 9/25, but his talk is not a prerequisite. The main theorem of his talk is that it is impossible to cut a square into an odd number of triangles of equal area. In my talk we will explore, more generally, what restrictions there are on the areas of triangles in a triangulation of a square. It turns out that for each combinatorial type of triangulation, there's a polynomial relation that must be satisfied by the areas. I will describe some of the things we know about this polynomial.

Maddie Brandt: Packing Polynomials on Sectors of \(\mathbb{R}^2\)

Abstract: A polynomial \(p(x,y)\) on a region \(S\) in the plane is called a packing polynomial if the restriction of \(p(x,y)\) to \(S\cap \mathbb{Z}^2\) yields a bijection to \(\mathbb{N}\). In this talk, we classify all quadratic packing polynomials on rational sectors of \(\mathbb{R}^2\).

Joshua Gancher: Weierstrass Points on Graphs

Abstract: TBA

Justin Katz: A primary decomposition in computer vision

Abstract: The pinhole model for a projective camera is given by a projective plane \(P\) and a focal point \(p\), embedded in an ambient 3-dimensional projective space. The image of a point \(x\) in the projective space under the pinhole camera is given by the unique point of intersection between the line connecting \(x\) and \(p\) and the image plane \(P\). Given a collection of distinct pinhole cameras, the image of a point in any one image plane constrains the possible corresponding points in the other image planes. Analyzing a camera system by considering pairs of cameras determines a bilinear constraint polynomial on the image coordinates, and considering triples of cameras determines a related trilinear polynomial constraint, known as the trifocal tensor. This talk will consider the ideal generated by selecting a particular subset of bilinear constraints, and demonstrate that the whole ideal generated by the trilinear constraints arises as a primary component. Such a primary decomposition has the potential to speed up image matching algorithms.

Pick's Theorem relates the area of a two-dimensional polyhedron to the number of integer points in each face. The theorem is patently false in three or more dimensions, but in this talk I will describe (infinitely many) ways of constructing higher-dimensional analogues. In order to do so, it will be helpful to generalize the notions of "volume" and "number of integer points", in order to give us something meaningful even when the polyhedron is unbounded.

This is joint work with Jamie Pommersheim that evolved out of my senior thesis at Reed in 2009. No prior familiarity with polyhedra will be assumed - only a basic knowledge of linear algebra and calculus.

Imagine two companies are trying to decide the merit of merging. Doing so requires comparing the books and client lists of the two companies, but both are reluctant to show this proprietary information to each other. Is there a way for them to do these complicated financial calculations without either seeing the other’s books?

Secure multiparty computation (MPC) gives us a way to do exactly this sort of joint computation. In this talk we will see how it’s done. On the way, we’ll see how modern cryptography defines security for a problem like this and we’ll look at encryption, oblivious transfer, and other tools that are used in solving it. We’ll also take a quick step away from the theoretical work to look at how MPC results are being used in the real world.

Since the beginning of the HIV epidemic, mathematical models have been used as a virtual laboratory for projecting how the infection is likely to spread.  Now, 30 years into the global pandemic, new biomedical interventions -- early treatment (Treatment as Prevention or TasP) and pre-exposure Prophylaxis (PreP) -- are leading many to predict the "End of AIDS".  Increasingly sophisticated models lie behind these optimistic projections.  This talk will take a look behind the curtain to see what these models include and what they assume, the new developments in modeling networks that challenge these findings, and the politics behind the math.

Come meet alumni and other mathematics majors to see what they are doing with their degrees! 

Featuring:

• Christopher Fesler ‘96 - Principal Engineer at Peak6 Investments
• Laura Heiser - Assistant Professor of Biomedical Engineering at OHSU
• Greg Morgan ‘77 - Former Managing Director at Huron Consulting Group
• Rose Peterman ‘10 - Actuary at Regence Blue Cross Blue Shield
• Steve Swanson '84 - Software Engineer Manager at Elemental Technologies

A classic exercise in geometry is to make certain constructions using only a ruler and compass. This restriction in what instruments to use was set by Euclid, the "father of geometry". Some constructions became famous for being impossible to obtain according to these rules, for example doubling the cube, trisecting the angle and squaring the circle. 

Given a graph with n vertices and m edges, did you know that you can delete m/4 vertices and leave behind a forest? It turns out that deleting fewer vertices will get you graphs that are almost as simple as forests: deleting m/4.5 vertices will get you a pseudoforest, deleting m/5 vertices will get you a partial 2-tree and deleting m/5.2174 vertices will get you a planar partial 3-tree. It also turns out that there is a limit to this: deleting m/6 vertices won't get you anything interesting.

This talk will teach you what these structures are (pseudoforests and 2-trees and so on). The results are based on recent work with David Eppstein and Pingan Zhu.

If I just told you directly that this week's colloquium was going to be about math and magic tricks, you'd probably think it would be about as cool and/or interesting as this guy: 

But what if I told you that I'd be talking about a magic trick invented by this guy: 

And that this was some of the math involved:

Then you'd probably want to come.