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

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

مثال‌ها

به عنوان مثال در جایگشت اعداد ۱ تا ۳:

• ۱٬۲٬۳ هر سه عدد خود یک زیردنبالهٔ صعودی هستند.
• ۱٬۳٬۲ دارای زیردنبالهٔ نزولی ۳٬۲ است.
• ۲٬۱٬۳ دارای زیر دنبالهٔ نزولی ۲٬۱ است.
• ۲٬۳٬۱ دارای دو زیردنبالهٔ نزولی ۲٬۱ و ۳٬۱ است.
• ۳٬۱٬۲ دارای دو زیردنبالهٔ ۳٬۱ و ۳٬۲ است.
• ۳٬۲٬۱ دارای سه زیردنباله نزولی به طول ۲ شامل ۳٬۲، ۳٬۱ و ۲٬۱ است.

اثبات

فرض می‌کنیم اعضای دنباله به صورت a₁،a₂،... ،a_k است.

به ازای هر i بین ۱ تا b_i k را طول بلندترین زیردنبالهٔ صعودی در دنباله در نظر می‌گیریم که جملهٔ آخرش a_i است.

اگر به ازای یکی از iها b_i≥n+1 حکم اثبات می‌شود؛ پس فرض می‌کنیم چنین نباشد؛ در این صورت b_iها بین ۱ تا n هستند. پس بنابر اصل لانه کبوتری حداقل m+۱ تا از b_i برابر هستند. فرض کنید b_i1=b_i2=... =b_im+1 که i_jها صعودی هستند.

حال زیردنبالهٔ a_i1،a_i2،... ،a_im+1 نزولی است زیرا اگر قرار باشد چنین نباشد به این نتیجه می‌رسیم که ۱+b_i1≥b_i2؛ که با فرضمان (b_i1=b_i2) تناقض دارد. پس حکم مسئله اثبات می‌شود.

این مسئله هم‌چنین به کمک قضیهٔ دیلورث اثبات می‌شود.

جستارهای وابسته

• طولانی‌ترین زیررشته صعودی

پیوند به بیرون

• Weisstein, Eric W. "Erdős-Szekeres Theorem". MathWorld.