Skip to Main Content
HBS Home
  • About
  • Academic Programs
  • Alumni
  • Faculty & Research
  • Baker Library
  • Giving
  • Harvard Business Review
  • Initiatives
  • News
  • Recruit
  • Map / Directions
Faculty & Research
  • Faculty
  • Research
  • Featured Topics
  • Academic Units
  • …→
  • Harvard Business School→
  • Faculty & Research→
Publications
Publications
  • 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
  • Format:Print
ShareBar

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

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.
  • Find it at Harvard
  • Purchase

About The Author

Scott Duke Kominers

Entrepreneurial Management
→More Publications

More from the Authors

    • January 12, 2023
    • a16zcrypto.com

    Progressive Decentralization: A High-level Framework

    By: Jad Esber and Scott Duke Kominers
    • December 7, 2022
    • Harvard Business Review Digital Articles

    Why Decentralized Crypto Platforms Are Weathering the Crash

    By: Shai Bernstein and Scott Duke Kominers
    • Winter 2022
    • Oxford Review of Economic Policy

    Distributing a Billion Vaccines: COVAX Successes, Challenges, and Opportunities

    By: Eric Budish, Hannah Kettler, Scott Duke Kominers, Erik Osland, Canice Prendergast and Andrew A. Torkelson
More from the Authors
  • Progressive Decentralization: A High-level Framework By: Jad Esber and Scott Duke Kominers
  • Why Decentralized Crypto Platforms Are Weathering the Crash By: Shai Bernstein and Scott Duke Kominers
  • Distributing a Billion Vaccines: COVAX Successes, Challenges, and Opportunities By: Eric Budish, Hannah Kettler, Scott Duke Kominers, Erik Osland, Canice Prendergast and Andrew A. Torkelson
ǁ
Campus Map
Harvard Business School
Soldiers Field
Boston, MA 02163
→Map & Directions
→More Contact Information
  • Make a Gift
  • Site Map
  • Jobs
  • Harvard University
  • Trademarks
  • Policies
  • Accessibility
  • Digital Accessibility
Copyright © President & Fellows of Harvard College