Every Large Point Set Contains Many Collinear Points or an Empty Pentagon

Zachary  Abel; Brad  Ballinger; Prosenjit  Bose; Sébastien  Collette; Vida  Dujmović; Ferran  Hurtado; Scott Duke Kominers; Stefan  Langerman; Attila  Pór; David  Wood

Article | Graphs and Combinatorics

Every Large Point Set Contains Many Collinear Points or an Empty Pentagon

by Zachary Abel, Brad Ballinger, Prosenjit Bose, Sébastien Collette, Vida Dujmović, Ferran Hurtado, Scott Duke Kominers, Stefan Langerman, Attila Pór and David Wood

Abstract

We prove the following generalised empty pentagon theorem for every integer ℓ ≥ 2, every sufficiently large set of points in the plane contains ℓ collinear points or an empty pentagon. As an application, we settle the next open case of the “big line or big clique” conjecture of Kára, Pór, and Wood [Discrete Comput. Geom. 34(3):497–506, 2005].

Keywords: Erdős-Szekeres theorem; happy end problem; big line or big clique conjecture; empty quadrilateral; empty pentagon; empty hexagon;

Format: Print

Find at Harvard Purchase

Citation:

Abel, Zachary, Brad Ballinger, Prosenjit Bose, Sébastien Collette, Vida Dujmović, Ferran Hurtado, Scott Duke Kominers, Stefan Langerman, Attila Pór, and David Wood. "Every Large Point Set Contains Many Collinear Points or an Empty Pentagon." Graphs and Combinatorics 27, no. 1 (January 2011): 47–60.

The U.S. residential real estate agency market presents a puzzle for economic theory: commissions on real estate transactions have remained constant and high for decades even though agent entry is frequent and agents’ costs of providing service are low. We model the real estate agency market, and other brokered markets, via repeated extensive form games; in our game, brokers first post prices for customers and then choose which agents on the other side of the market to work with. We show that prices appreciably higher than the competitive prices can be sustained (for a fixed discount factor) regardless of the number of brokers; this is done through strategies that condition willingness to transact with each broker on that broker’s initial posted prices. Our results can thus rationalize why brokered markets exhibit pricing high above marginal cost despite fierce competition for customers; moreover, our model can help explain why agents and platforms who have tried to reduce commissions have had trouble entering the market.

We introduce a new model of school choice with reserves in which a social planner is constrained by a limited supply of reserve seats and tries to find an optimal matching according to a social welfare function. We construct the optimal distribution of reserves via a quartic-time dynamic programming algorithm. Due to the modular nature of the dynamic program, the mechanism is strategy-proof for reserve-eligible students.

This case is set in mid-2019, when Qualcomm was struggling with unwanted takeover battles, fights with Apple and the Chinese government, and internal dissension on the board of directors. Ten years earlier Qualcomm was hailed as a monopoly on CDMA technologies and its derivatives—it appeared to be positioned to become the next dominant technology company in the tradition of Microsoft and Intel. But as the industry changed, Qualcomm’s competitive position seriously weakened. The purpose of the case is to explore central questions in strategy formulation: 1. how to build a long-term sustainable position based on technology, 2. how to design an IP strategy to lock in customers for the long run, 3. how to build a global standard and appropriate returns on that standard, and 4. how to respond when your historical business model starts to crumble.

Faculty & Research

Every Large Point Set Contains Many Collinear Points or an Empty Pentagon

Abstract

Citation:

About the Author

More from the Author