نظرية ميرسكي

في الرياضيات ، وتحديدًا في مجالي نظرية الترتيب والتوافقية ، تُحدد نظرية ميرسكي ارتفاع أي مجموعة جزئية الترتيب منتهية بدلالة تقسيم الترتيب إلى أقل عدد ممكن من السلاسل المضادة . سُميت هذه النظرية نسبةً إلى ليون ميرسكي ( 1971 ) ، وهي وثيقة الصلة بنظرية ديلورث حول عرض الترتيبات الجزئية، وكمال رسوم بيانية المقارنة ، ونظرية غالاي-هاس-روي-فيتافير التي تربط أطول المسارات والتلوينات في الرسوم البيانية، ونظرية إردوش-سيكيريس حول المتتاليات الجزئية الرتيبة. 

يُعرَّف ارتفاع المجموعة المرتبة جزئيًا بأنه أكبر عدد من العناصر في سلسلة ، وهي مجموعة جزئية مرتبة كليًا من الترتيب الجزئي المعطى. على سبيل المثال، في مجموعة الأعداد الصحيحة الموجبة من 1 إلى N ، مرتبة حسب قابلية القسمة ، تتكون إحدى أكبر السلاسل من قوى العدد 2 التي تقع ضمن هذا النطاق، ومن ثم فإن ارتفاع هذا الترتيب الجزئي هو${\displaystyle 1+\lfloor \log _{2}N\rfloor }$.

تنص نظرية ميرسكي على أنه لكل مجموعة جزئية مرتبة منتهية، يساوي ارتفاعها أيضًا الحد الأدنى لعدد السلاسل المضادة (المجموعات الجزئية التي لا يكون فيها أي زوج من العناصر مرتبًا) التي يمكن تقسيم المجموعة إليها. في مثل هذا التقسيم، يجب أن ينتمي كل عنصرين من أطول سلسلة إلى سلسلتين مضادتين مختلفتين، لذا فإن عدد السلاسل المضادة يكون دائمًا أكبر من أو يساوي الارتفاع. صيغة أخرى لنظرية ميرسكي هي أنه يوجد دائمًا تقسيم يكون فيه عدد السلاسل المضادة مساويًا للارتفاع. مرة أخرى، في مثال الأعداد الصحيحة الموجبة المرتبة حسب قابلية القسمة، يمكن تقسيم الأعداد إلى السلاسل المضادة {1}، {2، 3}، {4، 5، 6، 7}، إلخ.${\displaystyle 1+\lfloor \log _{2}N\rfloor }$المجموعات في هذا التقسيم، وداخل كل مجموعة من هذه المجموعات، يشكل كل زوج من الأرقام نسبة أقل من اثنين، لذلك لا يمكن أن يكون أي رقمين داخل إحدى هذه المجموعات قابلين للقسمة.

لإثبات وجود تقسيم إلى عدد قليل من السلاسل المضادة لمجموعة مرتبة جزئيًا منتهية عشوائية، نعتبر لكل عنصر x السلاسل التي يكون x أكبر عنصر فيها، ولنرمز إلى حجم أكبر هذه السلاسل بـ N(x) . عندئذٍ ، كل ^مجموعة N⁻¹ ( i ) ، التي تتكون من عناصر لها قيم متساوية لـ N ، هي سلسلة مضادة، وهذه السلاسل المضادة تقسم الترتيب الجزئي إلى عدد من السلاسل المضادة يساوي حجم أكبر سلسلة. في برهانه الأصلي، أنشأ ميرسكي التقسيم نفسه استقرائيًا، باختيار سلسلة مضادة من العناصر القصوى لأطول السلاسل، وإثبات أن طول أطول سلسلة بين العناصر المتبقية ينقص بمقدار واحد.

تمتد نظرية ميرسكي مباشرةً إلى المجموعات المرتبة جزئيًا اللانهائية ذات الارتفاع المحدود. ومع ذلك، فإن العلاقة بين طول السلسلة وعدد السلاسل المضادة في تجزئة إلى سلاسل مضادة لا تمتد إلى أعداد لا نهائية: فلكل عدد أصلي لانهائي κ ، توجد مجموعات مرتبة جزئيًا ليس لها سلسلة لانهائية وليس لها تجزئة إلى سلاسل مضادة تحتوي على κ أو أقل من السلاسل المضادة ( شمرل 2002 ) .

• ديلورث، روبرت ب. (1950)، "نظرية التفكيك للمجموعات المرتبة جزئيًا"، حوليات الرياضيات ، 51 (1): 161-166 ، doi : 10.2307/1969503 ، JSTOR 1969503 .
• غولومبيك، مارتن تشارلز (1980)، "5.7. التلوين ومشاكل أخرى على رسوم بيانية قابلة للمقارنة"، نظرية الرسوم البيانية الخوارزمية والرسوم البيانية المثالية ، نيويورك: أكاديميك برس، ص 132-135 ، ISBN  0-12-289260-7، MR 0562306 .
• لوفاس، لازلو (1972)، "الرسوم البيانية الفائقة العادية وتخمين الرسم البياني المثالي"، الرياضيات المتقطعة ، 2 (3): 253-267 ، doi : 10.1016/0012-365X(72)90006-4.
• ميرسكي، ليون (1971)، "ثنائية لنظرية تفكيك ديلورث"، المجلة الرياضية الأمريكية الشهرية ، 78 (8): 876-877 ، doi : 10.2307/2316481 ، JSTOR 2316481 .
• نيشيتريل، ياروسلاف ؛ أوسونا دي مينديز، باتريس (2012)، "النظرية 3.13"، التناثر: الرسوم البيانية، والهياكل، والخوارزميات ، الخوارزميات والتوافقية، المجلد  28، هايدلبرغ: سبرينغر، ص  42، doi : 10.1007/978-3-642-27875-4 ، ISBN 978-3-642-27874-7MR 2920058​ .
• شمرل، جيمس هـ. (2002)، "عقبات أمام توسيع نظرية ميرسكي"، النظام ، 19 (2): 209-211 ، doi : 10.1023/A:1016541101728 ، MR 1922918 ، S2CID 26514679  .