ترتيب الفترات

في الرياضيات ، وخاصةً في نظرية الترتيب ، يُعرف ترتيب الفترات لمجموعة من الفترات على خط الأعداد الحقيقية بأنه الترتيب الجزئي المقابل لعلاقة الأسبقية من اليسار إلى اليمين - حيث تُعتبر فترة ما، I1، أصغر من فترة أخرى، I2 ، إذا كانت I1 تقع بالكامل على يسار _{I2 .} وبصورة أكثر دقة، تُعرف المجموعة المرتبة _{جزئيًا القابلة للعد} باسم مجموعة جزئية قابلة للعد _.${\displaystyle P=(X,\leq )}$يكون ترتيب الفترات إذا وفقط إذا كان هناك تقابل من${\displaystyle X}$إلى مجموعة من الفترات الحقيقية، لذلك${\displaystyle x_{i}\mapsto (\ell _{i},r_{i})}$بحيث يكون لأي${\displaystyle x_{i},x_{j}\in X}$لدينا ${\displaystyle x_{i}<x_{j}}$في${\displaystyle P}$متى بالضبط${\displaystyle r_{i}<\ell _{j}}$.

يمكن وصف هذه المجموعات المرتبة جزئيًا بشكل مكافئ بأنها تلك التي لا تحتوي على مجموعة فرعية متجانسة مع زوج من السلاسل المكونة من عنصرين ، أو بعبارة أخرى، على أنها${\displaystyle (2+2)}$المجموعات الجزئية الخالية من العناصر. ^{[ 1 ]} عند كتابتها بالكامل، هذا يعني أنه لأي زوجين من العناصر${\displaystyle a>b}$و${\displaystyle c>d}$يجب على المرء أن يمتلك${\displaystyle a>d}$أو${\displaystyle c>b}$.

الفئة الفرعية من رتب الفترات التي يتم الحصول عليها عن طريق تقييد الفترات بتلك التي يبلغ طولها وحدة واحدة، بحيث يكون لها جميعًا الشكل التالي:${\displaystyle (\ell _{i},\ell _{i}+1)}$، وهي تحديداً أنصاف الرتب .

مكمل الرسم البياني للمقارنة لترتيب الفترات (${\displaystyle X}$( , ≤) هو الرسم البياني للفترات${\displaystyle (X,\cap )}$.

لا ينبغي الخلط بين ترتيبات الفترات وترتيبات احتواء الفترات، وهي ترتيبات التضمين على الفترات على خط الأعداد الحقيقية (بصورة مكافئة، ترتيبات البعد ≤ 2).

تشمل التطبيقات العملية لترتيب الفترات نمذجة تطور الأنواع والتاريخ الأثري لأنماط الفخار. ^{[ 2 ]}

أحد المعايير المهمة للأوامر الجزئية هو بُعد الأمر : بُعد الأمر الجزئي${\displaystyle P}$هو أقل عدد من الرتب الخطية التي يكون تقاطعها${\displaystyle P}$بالنسبة لترتيبات الفترات، يمكن أن يكون البُعد كبيرًا بشكل تعسفي. وبينما تُعرف مشكلة تحديد بُعد الترتيبات الجزئية العامة بأنها من المسائل الصعبة حسابيًا (NP-hard) ، فإن تحديد بُعد ترتيب الفترات لا يزال مشكلة ذات تعقيد حسابي غير معروف . ^{[ 3 ]}

هناك معيار ذو صلة وهو بُعد الفترة ، والذي يُعرَّف بشكل مماثل، ولكن بدلالة ترتيبات الفترات بدلاً من الترتيبات الخطية. وبالتالي، فإن بُعد الفترة لمجموعة مرتبة جزئياً${\displaystyle P=(X,\leq )}$هو أصغر عدد صحيح${\displaystyle k}$والتي توجد لها ترتيبات فترات${\displaystyle \preceq _{1},\ldots ,\preceq _{k}}$على${\displaystyle X}$مع${\displaystyle x\leq y}$متى بالضبط${\displaystyle x\preceq _{1}y,\ldots ,}$و${\displaystyle x\preceq _{k}y}$لا يتجاوز بُعد الفترة لأي ترتيب بُعد الترتيب نفسه. ^{[ 4 ]}

بالإضافة إلى كونها متماثلة مع${\displaystyle (2+2)}$- مجموعات جزئية خالية من التعقيد، ترتيبات فترات غير مصنفة على${\displaystyle [n]}$كما أنها في تقابل مع مجموعة فرعية من الانعكاسات الخالية من النقاط الثابتة على المجموعات المرتبة ذات العددية${\displaystyle 2n}$[ ^{5 ]} هذه هي الانعكاسات التي لا تحتوي على ما يسمى بالتداخلات المجاورة اليسرى أو اليمنى، حيث بالنسبة لأي ^انعكاس${\displaystyle f}$على${\displaystyle [2n]}$، التعشيش الأيسر هو${\displaystyle i\in [2n]}$بحيث${\displaystyle i<i+1<f(i+1)<f(i)}$والترتيب الصحيح هو${\displaystyle i\in [2n]}$بحيث ${\displaystyle f(i)<f(i+1)<i<i+1}$.

تتمتع هذه الانعكاسات، وفقًا لنصف الطول، بدالة توليد عادية ^{[ 6 ].}

${\displaystyle F(t)=\sum _{n\geq 0}\prod _{i=1}^{n}(1-(1-t)^{i}).}$

معامل${\displaystyle t^{n}}$في توسع${\displaystyle F(t)}$يعطي عدد رتب الفترات غير المصنفة ذات الحجم${\displaystyle n}$يبدأ تسلسل هذه الأرقام (التسلسل A022493 في OEIS )

1، 2، 5، 15، 53، 217، 1014، 5335، 31240، 201608، 1422074، 10886503، 89903100، 796713190، 7541889195، 75955177642، …

• بوسكيه-ميلو، ميريل ؛ كلايسون، أندرس؛ دوكس، مارك؛ كيتايف، سيرجي (2010)، "المجموعات المرتبة الجزئية الحرة (2+2)، ومتواليات الصعود، والتباديل التي تتجنب الأنماط"، مجلة نظرية التوافيق ، السلسلة أ، 117 (7): 884-909 ، arXiv : 0806.0666 ، doi : 10.1016/j.jcta.2009.12.007 ، MR 2652101 ، S2CID 8677150  .
• Felsner, S. (1992)، الأوامر الفاصلة: البنية التوافقية والخوارزميات (PDF) ، دكتوراه. أطروحة، جامعة برلين التقنية.
• فيلسنر، س.؛ حبيب، م.؛ موهرينغ، ر.هـ. (1994)، "حول التفاعل بين بُعد الفترة والبعد" (ملف PDF) ، مجلة SIAM للرياضيات المتقطعة ، 7 (1): 32-40 ، doi : 10.1137/S089548019121885X ، MR 1259007 .
• فيشبورن، بيتر سي. (1970)، "اللامبالاة غير المتعدية مع فترات لامبالاة غير متساوية"، مجلة علم النفس الرياضي ، 7 (1): 144-149 ، doi : 10.1016/0022-2496(70)90062-3 ، MR 0253942 .
• زاغير، دون (2001)، "ثوابت فاسيليف وهوية غريبة مرتبطة بدالة إيتا لديديكيند"، الطوبولوجيا ، 40 (5): 945-960 ، doi : 10.1016/s0040-9383(00)00005-7 ، MR 1860536 .
• ديفي، بكالوريوس؛ بريستلي، هـ. أ. (2002) [1990]. مقدمة في الشبكات والنظام (الطبعة الثانية  ). مطبعة جامعة كامبريدج. رقم ISBN 9780521784511.

• فيشبورن، بيتر (1985)، ترتيب الفترات ورسوم الفترات: دراسة للمجموعات المرتبة جزئيًا ، جون وايلي