مبرهنة إيردوس-سيكريس

في الرياضيات، تنص مبرهنة إيردوس-سيكريس على أنه في كل متتالية مكونة من أعداد حقيقية بطول $rs+1$ ، يوجد لها متتالية جزئية متزايدة بطول $r+1$ أو متتالية جزئية متناقصة بطول $s+1$ . هذه المبرهنة هي مبرهنة مثالية في نظرية رمزي، التي تبحث الانتظام وسط الفوضى.

تمت برهنة المبرهنة على يد بول إيردوس وجورج سيكريس في مقال لهما سنة 1935.

مثال

لـ r = 1 و s = 2، تخبرنا الصيغة بأنه لأي تبديل من 3 أعداد يوجد متتالية جزئية متزايدة بطون 3 أو متتالية جزئية متناقصة بطول 2. ننظر إلى جميع التبديلات من الأعداد 1,2,3:

1,2,3 متتالية جزئية متزايدة مكونة من كل الأعداد
1,3,2 يملك متتالية جزئية متناقصة 3,2
2,1,3 يملك متتالية جزئية متناقصة 2,1
2,3,1 يملك متتاليتين متناقصين 2,1 و 3,1
3,1,2 يملك متتاليتين متناقصين 3,1 و 3,2
3,2,1 متتالية جزئية متناقصة مكونة من كل الأعداد

برهان

يمكن برهنة مبرهنة إيردوس-سيكريس بالعديد من الطرق; steele (1995) عاين ستة براهين مختلفة لمبرهنة إيردوس-سيكريس، بما في ذلك البرهان التالي. ^[1]

مبدأ برج الحمام

إذا كانت معطاه متتالية بطول rs + 1، نميز كل عدد n_i في المتتالية بالزوج (a_i,b_i)، بحيث أن a_i هو طول أطول متتالية متزايدة تنتهي بـ n_i و b_i هو طول أطول ممتالية متناقصة تنتهي بـ ,n_i. كل عددين في المتتالية مميزين بزوج مختلف:

إذا كان i < j و n_i < n_j إذن a_i < a_j
إذا كان i < j و n_i > n_j إذن b_i < b_j

ولكن هنالك rs علامة مميّزة بحيث أن a_i على الأكثر r و b_i على الأكثر s، ولذلك وفقا لمبدأ برج الحمام يجب أن تكون قيمة i بحيث a_i أو b_i خارج المجال. إذا كانت a_i خارج المجال إذن n_i هي جزء من متتالية متزايدة بطول 1 + r على الأقل، وإذا كانت b_i خارج المجال إذن n_i هي جزء من متتالية متناقصة بطول 1 + s على الأقل.

انظر أيضا

مبرهنة رمزي

مراجع

^ Steele، J. Michael (1995)، "Variations on the monotone subsequence theme of Erdős and Szekeres"، في Aldous، David؛ Diaconis، Persi؛ Spencer، Joel؛ Steele، J. Michael (المحررون)، Discrete Probability and Algorithms (PDF)، IMA Volumes in Mathematics and its Applications، Springer-Verlag، ج. 72، ص. 111–131، مؤرشف من الأصل (PDF) في 2019-06-11.

وصلات خارجية

إيريك ويستاين، Erdős-Szekeres Theorem، ماثوورلد Mathworld (باللغة الإنكليزية).

هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. فضلًا شارك في تحريرها.

Read other articles:

Lviv

Lambang Lviv. Motto: Semper Fidelis (Bahasa Latin:Selalu Setia) L'viv (Львів dalam bahasa Ukraina; Львов, Lvov dalam bahasa Rusia; Lwów dalam bahasa Polandia; Leopolis dalam bahasa Latin; Lemberg dalam bahasa Jerman atau Lemberk dalam bahasa Yiddish) adalah sebuah kota yang sekarang terletak di sebelah barat Ukraina. Kota ini memiliki penduduk sekitar 730.000 jiwa (dengan tambahan 200.000 jiwa yang hidup di sekitar kota ini. Kota ini merupakan ibu kota daerah L'viv dan sebuah pusat...

Farewell, My Dear Cramer

Farewell, My Dear Cramerさよなら私のクラマー(Sayonara Watashi no Kuramā)GenreSports[1] MangaPengarangNaoshi ArakawaPenerbitKodanshaPenerbit bahasa InggrisNA Kodansha ComicsMajalahMonthly Shōnen MagazineDemografiShōnenTerbit6 Mei, 2016 – 4 Desember, 2020Volume14 Seri animeSutradaraSeiki TakunoSkenarioNatsuko TakahashiMusikMasaru YokoyamaStudioLiden FilmsPelisensiCrunchyroll SEA Muse CommunicationSaluranasliTokyo MXTayang 4 April, 2021 – 27 Juni, 2021Episode13 (Daftar e...

Markus Antonius

Patung Markus Antonius Markus Antonius (Roma, ± 14 Januari 83 SM - 1 Agustus 30 SM) merupakan politikus dan jenderal Romawi Kuno. Ia merupakan pendukung penting Julius Caesar sebagai jenderal dan administrator. Setelah pembunuhan Caesar, Antonius bergabung dengan Oktavianus dan Lepidus untuk membentuk Triumvirat Kedua. Pemerintahan ini berakhir pada tahun 33 SM dan Antonius membunuh diri bersama Kleopatra. Selama masa kekuasaan Julius Caesar, ia adalah salah satu jenderalnya dan pendukung ya...

Bahasa Tawoyan

PemberitahuanTemplat ini mendeteksi bahwa artikel bahasa ini masih belum dinilai kualitasnya oleh ProyekWiki Bahasa dan ProyekWiki terkait dengan subjek. Perhatian: untuk penilai, halaman pembicaraan artikel ini telah diisi sehingga penilaian akan berkonflik dengan isi sebelumnya. Harap salin kode dibawah ini sebelum menilai. {{PW Bahasa|importance=|class=}} Terjadi [[false positive]]? Silakan laporkan kesalahan ini. 14.22, Jumat, 29 Maret, 2024 (UTC) • hapus singgahan Seban...

Bahasa Persia Pertengahan

Cari artikel bahasa Cari berdasarkan kode ISO 639 (Uji coba) Kolom pencarian ini hanya didukung oleh beberapa antarmuka Halaman bahasa acak Bahasa Persia Pertengahan (𐭯𐭠𐭫𐭮𐭩𐭪), Pārsīk / Pārsīg Pahlavi Pārsīk ditulis dalam abjad Pahlavi Prasasti (dari kanan ke kiri) Dituturkan diKekaisaran SasaniyahWilayahAsia BaratEtnisBangsa PersiaEraberkembang menjadi bahasa Persia Baru pada abad ke-9; selanjutnya hanya digunakan dalam upacara keagamaan Zoroastrianism...

Coat of arms of the Crown of Aragon

This article is about the arms of the former Crown of Aragon. For the arms of the Autonomous Community of Aragon, see Coat of arms of Aragon. Arms of the Crown of Aragon Page of a manuscript of the Book of Knowledge of All Kingdoms (14th century) showing the coat of arms of Aragon. The so-called Bars of Aragon, Royal sign of Aragon, Royal arms of Aragon, Four Bars, Red Bars or Coat of arms of the Crown of Aragon, which bear four red pallets on gold background, depicts the familiar coat of the...

Morphine

Pour les articles homonymes, voir Morphine (homonymie). Morphine Structure 2D de la morphine et animation 3D. Identification DCI Morphine Nom UICPA 17-méthyl-7,8-didéshydro-4,5α-époxymorphinan-3,6α-diol No CAS 57-27-2 64-31-3 (sulfate de morphine) No ECHA 100.000.291 No CE 200-320-2 No RTECS QC8760000 (pentahydrate de sulfate) Code ATC N02AA01 DrugBank DB00295 PubChem 5288826 ChEBI 17303 SMILES [H][C@]12C=C[C@H](O)[C@@H]3Oc4c(O)ccc5C[C@H]1N(C)CC[C@@]23c45 PubChem, vue 3D InChI InChI...

Rim (basketball)

Typical professional hoop with backboard The rim is a piece of basketball equipment, the circular metal ring holding up the net. It hangs from the backboard. The rim had a diameter of 18 inches.[1] A slam dunk requires one to jump high enough to get his hand above or over the rim.[2] Today there are breakaway rims. References ^ Norman D. Graubart. The Science of Basketball. p. 20. ^ Inside the Cage. p. 92. vteBasketballGeneral topics Glossary of terms Index of articl...

Kawésqar

Pour la langue, voir Kawésqar (langue). Kawésqars (ou Alacalufes) L'une des dernières représentantes des Kawésqars encore en vie vendant des articles d'artisanat aux touristes Populations importantes par région Population totale 3448 (2017) Autres Langues Kawésqar,Espagnol chilien Religions Chrétienne,animiste,chamanisme Ethnies liées kaweskars (ou alacalufs) modifier Régions habitées par les Kawésqars et les Yagans. En gris, frontière entre l'Argentine et le Chili. (Détail de ...

Гарпунная пушка

Гарпунная пушка старого образца (дульнозарядная) Гарпу́нная пушка — орудие китобойного промысла. Представляет собой короткоствольную пушку, укреплённую на палубе судна-китобойца, стреляющую гарпуном, который, как правило, имеет в головной части заряд взрывчатого веще�...

Оксид иттрия-бария-меди

Оксид иттрия-бария-меди (YBCO) Общие Систематическоенаименование Оксид иттрия-бария-меди Хим. формула YBa2Cu3O7−x Физические свойства Состояние твёрдое Молярная масса 666,19 г/моль Плотность 6,3 г/см³[1][2] Термические свойства Температура • ...

Zhou Xuan

Artikel ini bukan mengenai Zhou Xun. Zhou XuanNama Tionghoa周璇PinyinZhōu Xuán (Mandarin)Nama LahirSu Pu (蘇璞)Lahir(1918-08-01)1 Agustus 1918Changzhou, Jiangsu, ChinaWafat22 September 1957(1957-09-22) (umur 39)ShanghaiPekerjaanPenyanyi, aktrisGenreShidaiquTahun aktif1935-57 Ini adalah nama Tionghoa; marganya adalah Zhou. Zhou Xuan (1 Agustus 1918 – 22 September 1957), juga diromanisasikan sebagai Chow Hsuan, adalah seorang aktris film dan penyanyi Tiongkok ikonik. ...

River City Rollergirls

Roller derby league This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: River City Rollergirls – news · newspapers · books · scholar · JSTOR (June 2010) (Learn how and when to remove this message) River City RollergirlsMetro areaRichmond, VirginiaCountryUnited StatesFounded2006TeamsPoes PunishersUncivil Warriors...

Culture of Turkey

Overview of the culture of the Republic of Turkey This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Culture of Turkey – news · newspapers · books · scholar · JSTOR (March 2021) (Learn how and when to remove this message) Part of a series on theCulture of Turkey History Agriculture Anatolian peoples Christianit...

Kaba Diawara

Questa voce sull'argomento calciatori guineani è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Kaba Diawara Nazionalità Francia Guinea (dal 2004) Calcio Ruolo Allenatore (ex attaccante) Squadra Guinea Termine carriera 2011 - giocatore CarrieraSquadre di club1 1993-1995 Tolone40 (11)1995-1998 Bordeaux43 (9)1998→ Rennes12 (3)1998 Bordeaux17 (5)1999 Arsenal12 (0)199...

美国众议院

此條目需要补充更多来源。 (2021年7月4日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。致使用者：请搜索一下条目的标题（来源搜索：美国众议院 — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。美國眾議院 United States House of Representatives第118届美国国会众议院徽章众议院旗...

2020年夏季奧林匹克運動會波蘭代表團

2020年夏季奥林匹克运动会波兰代表團波兰国旗IOC編碼POLNOC波蘭奧林匹克委員會網站olimpijski.pl（英文）（波兰文）2020年夏季奥林匹克运动会（東京）2021年7月23日至8月8日（受2019冠状病毒病疫情影响推迟，但仍保留原定名称）運動員206參賽項目24个大项旗手开幕式：帕维尔·科热尼奥夫斯基（游泳）和马娅·沃什乔夫斯卡（自行车）[1]闭幕式：卡罗利娜·纳亚（皮划艇）&#...

2020年夏季奧林匹克運動會波蘭代表團

Лисичанський пивоварний завод

Лисичанський пивоварний заводТип товариство з обмеженою відповідальністюФорма власності недержавна власністьГалузь пивоварінняЗасновано 1 листопада 1994, існує з 1972Засновник(и) Біла К. Ю.Штаб-квартира вул. Генерала Потапенка, 500, Лисичанськ, УкраїнаКлючові особи Ко...

Nationalization of history

Nationalization of history is the term used in historiography to describe the process of separation of one's own history from the common universal history, by way of perceiving, understanding and treating the past that results with construction of history as history of a nation.[1] If national labeling of the past is not treated with great care, it can result in the retrospective nationalization of history[2] and even assigning nonexistent or exaggerated existing national attr...