Any sequence of more than (r minus 1) times (s minus 1) distinct real numbers contains either an increasing subsequence of length r or a decreasing subsequence of length s. Proved by Paul Erdos and George Szekeres, it is a classical result connecting Ramsey-type combinatorics to the structure of sequences, originally developed in their work on the 'happy ending problem' for points in general position.
Facts
StatementAny sequence of distinct real numbers with length at least (r-1)(s-1)+1 contains a monotonically increasing subsequence of length r or a monotonically decreasing subsequence of length s. 1 Classification
Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Proved By
Sources
1. Erdos-Szekeres Theorem (Wikipedia)
Wikimedia FoundationLead section
contains a monotonically increasing subsequence of length r or a monotonically decreasing subsequence of length s.
Lead section, proof year
The proof appeared in the same 1935 paper that mentions the Happy Ending problem.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.