Discrete mathematics and graph theory · Maths EE idea · Accessible

Surprising results from the pigeonhole principle

A research question to start from

How can the pigeonhole principle prove results such as the Erdős–Szekeres theorem on increasing and decreasing subsequences?

A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.

Why it works as a maths EE

A simple principle with a deep result as the target and smaller ones as steps.

Mathematics you would need

Pigeonhole principle
Sequences
Proof by contradiction
Sharpness constructions

Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.

One possible line of attack

Prove warm-up results.
Prove Erdős–Szekeres.
Construct sequences showing the bound is sharp.

Scope and difficulty

Accessible. Accessible.

Pitfalls

A list of puzzles with no main result.
Sharpness not shown.

Where to start reading

Search a library catalogue or a university's open lecture notes for: Erdos-Szekeres theorem pigeonhole proof sharpness. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).

Make it your EE

Plan this EEOpens the free EE planner with this question as a starting point. Sharpen the questionSix quick checks for a focused research question. Self-check a draftCheck a section against each criterion, free.