Mathematics

Gross substitutes is a fundamental property in mathematics, economics and computation, almost as important as convexity. It is at the heart of optimal transport theory – although this is often underrecognized – and understanding the connection key to understanding the extension of optimal transport to other models of matching.

Lecture 1. Introduction to gross substitutes M-matrices and M-maps, nonlinear Perron-Froebenius theory, convergence of Jacobi algorithm. A toy hedonic model.

Lecture 2. Models of matching with transfers Problem formulation, regularized and unregularized case. IPFP and its convergence. Existence and uniqueness of an equilibrium. Lattice structure.

Lecture 3. Models of matching without transfers Gale and Shapley’s stable matchings. Adachi’s formulation. Kelso-Craford. Hatfield-Milgrom.

Gross substitutes is a fundamental property in mathematics, economics and computation, almost as important as convexity. It is at the heart of optimal transport theory – although this is often underrecognized – and understanding the connection key to understanding the extension of optimal transport to other models of matching.

Lecture 1. Introduction to gross substitutes M-matrices and M-maps, nonlinear Perron-Froebenius theory, convergence of Jacobi algorithm. A toy hedonic model.

Lecture 2. Models of matching with transfers Problem formulation, regularized and unregularized case. IPFP and its convergence. Existence and uniqueness of an equilibrium. Lattice structure.

Lecture 3. Models of matching without transfers Gale and Shapley’s stable matchings. Adachi’s formulation. Kelso-Craford. Hatfield-Milgrom.

A classical question in polytope theory is whether an abstract polytope can be realized as a concrete convex object. Beyond dimension 3, there seems to be no concise answer to this question in general. In specific instances, answering the question in the negative is often done via “final polynomials” introduced by Bokowski and Sturmfels. This method involves finding a polynomial which, based on the structure of a polytope if realizable, must be simultaneously zero and positive, a clear contradiction. The search space for these polynomials is ideal of Grassmann-Plücker relations, which quickly becomes too large to efficiently search, and in most instances where this technique is used, additional assumptions on the structure of the desired polynomial are necessary.

In this talk, I will describe how by changing the search space, we are able to use linear programming to exhaustively search for similar polynomial certificates of non-realizability without any assumed structure. We will see that, perhaps surprisingly, this elementary strategy yields results that are competitive with more elaborate alternatives and allows us to prove non-realizability of several interesting polytopes.

PIMS is glad to announce that Sean Graves is the winner of the 2022 Education Prize. Graves is a faculty lecturer in the Department of Mathematical and Statistical Sciences and the Coordinator for the Decima Robinson Support Centre at the University of Alberta. The selection committee was extremely impressed by his energy and enthusiasm towards teaching, and the impact of his work developing mathematical talent through outreach. This prize, awarded annually by PIMS, recognizes individuals and groups in the PIMS network, Western Canada and Washington State who have played a major role in encouraging activities which have enhanced public awareness and appreciation of mathematics.

“(Graves’) hands-on training focuses on communication, diversity, professionalism, and pedagogically strong teaching techniques. Any person who spends time with Sean talking about mathematics perceives that there is an intrinsic beauty within this discipline: a magic of sorts,” noted Arturo Pianzola, Department Chair at UAlberta.

Sean Graves has been a faculty lecturer since 2011 and has received numerous awards from the University of Alberta for his teaching and service. In 2017 he was awarded the William Hardy Alexander Award for Excellence in Undergraduate Teaching. He has been passionate about training future educators in his teaching of math and developed a new course focused on mathematical reasoning for elementary teachers. Sean has also been the lead organizer for UAlberta SNAP Math Fairs each year since 2007, and a co-organizer of the Canadian Mathematics Society’s Alberta Math Summer Camp, for students aged 12-15 years. His continuous dedication to mathematics students of all ages, as well as teachers is inspiring to many.

The semi-random graph process can be thought of as a one player game. Starting with an empty graph on n vertices, in each round a random vertex u is presented to the player, who chooses a vertex v and adds the edge uv to the graph (hence 'semi-random'). The goal of the player is to construct a small fixed graph G as a subgraph of the semi-random graph in as few steps as possible. I will discuss this process, and in particular the asympotically tight bounds we have found on how many steps the player needs to win. This is joint work with Trent Marbach, Pawel Pralat and Andrzej Rucinski.