قضیه اردیش–سکرش

قضیهٔ اردیش–سکرش در ریاضیات نتیجه ای متناهی است که یکی از نتایج قضیهٔ رمزی را دقیق می سازد. به خاطر اینکه با استفاده از قضیهٔ رمزی اثباتی آسان برای اینکه هر دنباله نامتناهی از اعداد حقیقی متمایز دارای زیردنباله ای نامتناهی به صورت صعودی یا نزولی است، وجود دارد؛ با اثبات پل اردیش (به مجاری: Erdős Pál) و جرج سکرش (به مجاری: Szekeres György) این قضیه بسط داده می شود. آن ها اثبات کردند که برای هر دنباله ای به طول K که K>mn؛ دارای زیردنباله ای صعودی به طول n+1 یا زیردنباله ای نزولی به طول m+1 است (یا هر دو). این اثبات در سال ۱۹۳۵ در ورقهٔ اثبات مسئله پایان یافتن شادی به عنوان یادکرد آمده است.
۱٬۲٬۳ هر سه عدد خود یک زیردنبالهٔ صعودی هستند.
۱٬۳٬۲ دارای زیردنبالهٔ نزولی ۳٬۲ است.
۲٬۱٬۳ دارای زیر دنبالهٔ نزولی ۲٬۱ است.
۲٬۳٬۱ دارای دو زیردنبالهٔ نزولی ۲٬۱ و ۳٬۱ است.
۳٬۱٬۲ دارای دو زیردنبالهٔ ۳٬۱ و ۳٬۲ است.
۳٬۲٬۱ دارای سه زیردنباله نزولی به طول ۲ شامل ۳٬۲، ۳٬۱ و ۲٬۱ است.
به عنوان مثال در جایگشت اعداد ۱ تا ۳:
فرض می کنیم اعضای دنباله به صورت a1،a2،... ،ak است.
به ازای هر i بین ۱ تا bi k را طول بلندترین زیردنبالهٔ صعودی در دنباله در نظر می گیریم که جملهٔ آخرش ai است.