مراسلات روبنسون-شينستيد

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

أبسط وصف لهذه العلاقة هو استخدام خوارزمية شينستيد (شينستيد، 1961 ) ، وهي إجراء يُنشئ جدولًا واحدًا بإدخال قيم التبديل تباعًا وفقًا لقاعدة محددة، بينما يسجل الجدول الآخر تطور الشكل أثناء الإنشاء. وقد وُصفت هذه العلاقة، بشكل مختلف تمامًا، في وقت سابق بكثير من قِبل روبنسون ( روبنسون، 1938 ) ، في محاولة لإثبات قاعدة ليتلوود-ريتشاردسون . غالبًا ما يُشار إلى هذه العلاقة باسم خوارزمية روبنسون-شينستيد ، على الرغم من أن الإجراء الذي استخدمه روبنسون يختلف جذريًا عن خوارزمية شينستيد، وقد طواه النسيان تقريبًا. تشمل الطرق الأخرى لتعريف هذه العلاقة خوارزمية غير حتمية باستخدام لعبة "جو دي تاكين" .  

إن الطبيعة التقابلية للمطابقة تربطها بالهوية العددية

${\displaystyle \sum _{\lambda \in {\mathcal {P}}_{n}}(t_{\lambda })^{2}=n!}$

أين${\displaystyle {\mathcal {P}}_{n}}$يشير إلى مجموعة التقسيمات لـ n (أو مخططات يونغ مع n مربعات)، و t _λ يشير إلى عدد جداول يونغ القياسية ذات الشكل λ .

تبدأ خوارزمية شينستيد من التبديل σ المكتوب بصيغة سطرين.

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&\cdots &n\\\sigma _{1}&\sigma _{2}&\sigma _{3}&\cdots &\sigma _{n}\end{pmatrix}}}$

حيث σ _i = σ ( i ) ، ويستمر من خلال إنشاء سلسلة من الأزواج المرتبة (الوسيطة) من جداول يونغ من نفس الشكل:

${\displaystyle (P_{0},Q_{0}),(P_{1},Q_{1}),\ldots ,(P_{n},Q_{n}),}$

حيث P₀ = Q₀ هما جدولان فارغان _. أما جدولا الإخراج فهما P = Pₙ و Q = Qₙ . بعد إنشاء Pᵢ₋₁، يتم تكوين _{Pᵢ بإدخال σᵢ} فيه ، _ثم Qᵢ _بإضافة المدخل i إلى _Qᵢ₋₁ في المربع الناتج عن الإدخال (بحيث _{يكون لـ} Pᵢ _{و Qᵢ} نفس الشكل لجميع قيم i ) . _{نظرًا للدور} السلبي لجدول Qᵢ ، _{يُسمى الجدول} الأخير Qₙ _{، الذي يُعد} جزءًا من الإخراج والذي يمكن من خلاله قراءة قيم Qᵢ السابقة بسهولة ، بجدول _{التسجيل} ؛ في المقابل، يُسمى جدولا _Pᵢ بجدولي الإدخال .

الإدخال

تُسمى الطريقة الأساسية لإدراج كل قيمة _σᵢ بإدراج شينستيد أو إدراج الصف (لتمييزها عن طريقة أخرى تُسمى إدراج العمود). تُعرَّف أبسط صورها باستخدام "الجداول القياسية غير المكتملة": فهي، كالجداول القياسية، تحتوي على مدخلات مميزة، تُشكِّل صفوفًا وأعمدة متزايدة، ولكن قد تغيب بعض القيم (التي لم تُدرج بعد) كمدخلات. تأخذ هذه الطريقة كمدخلات جدولًا T وقيمة x غير موجودة كمدخل في T ؛ وتُنتج كمخرج جدولًا جديدًا يُرمز له بـ T ← x ومربعًا s يُمثل حجم الجدول الجديد. تظهر القيمة x في الصف الأول من T ← x ، إما بإضافتها في النهاية (إذا لم تكن هناك مدخلات أكبر من x )، أو باستبدالها بالمدخل الأول y > x في الصف الأول من T. في الحالة الأولى، يكون s هو المربع الذي تُضاف إليه x ، وبذلك يكتمل الإدراج. في الحالة الأخيرة، يتم إدخال الإدخال المستبدل y بشكل مماثل في الصف الثاني من T ، وهكذا، حتى يتم تطبيق الحالة الأولى في خطوة ما (وهو ما يحدث بالتأكيد إذا تم الوصول إلى صف فارغ من T ).

^{بصورة أكثر رسمية، يصف} الكود الزائف التالي عملية إدخال صف جديد بقيمة x في T. [ ^{1 ]}

1. اجعل i = 1 و j أكبر بواحد من طول الصف الأول من T.
2. بينما j > 1 و x < T _{i , j −1} ، قم بإنقاص j بمقدار 1. (الآن ( i , j ) هو المربع الأول في الصف i الذي يحتوي إما على عنصر أكبر من x في T ، أو لا يحتوي على أي عنصر على الإطلاق.)
3. إذا كان المربع ( i , j ) فارغًا في T ، فقم بالإنهاء بعد إضافة x إلى T في المربع ( i , j ) وتعيين s = ( i , j ) .
4. قم بتبديل القيمتين x و T _{i, j} . (هذا يُدرج قيمة x القديمة في الصف i ، ويحفظ القيمة التي يحل محلها لإدراجها في الصف التالي.)
5. قم بزيادة قيمة i بمقدار 1 ثم عد إلى الخطوة 2.

يكبر شكل T بمقدار مربع واحد بالضبط، وهو s .

الصواب

إن حقيقة أن T ← x لها صفوف وأعمدة متزايدة، إذا كان الأمر نفسه ينطبق على T ، ليست واضحة من هذه العملية (إذ لا تتم مقارنة القيم في العمود نفسه مطلقًا). ومع ذلك، يمكن توضيح ذلك على النحو التالي: في جميع الأوقات باستثناء ما بعد الخطوة  4 مباشرةً، يكون المربع ( i , j ) إما فارغًا في T أو يحتوي على قيمة أكبر من x ؛ وتعيد الخطوة  5 تأكيد هذه الخاصية لأن ( i , j ) أصبح الآن المربع الذي يلي مباشرةً المربع الذي كان يحتوي على x في T. وبالتالي، فإن تأثير الاستبدال في الخطوة  4 على قيمة T _{i, j} هو تصغيرها؛ وعلى وجه الخصوص، لا يمكن أن تصبح أكبر من جيرانها على اليمين أو الأسفل. من ناحية أخرى، فإن القيمة الجديدة ليست أقل من جارتها على اليسار (إن وجدت)، كما هو مضمون من خلال المقارنة التي أنهت الخطوة  2 للتو. وأخيرًا، للتأكد من أن القيمة الجديدة أكبر من جارتها العليا T _{i −1, j} إن وجدت، لاحظ أن T _{i −1, j} تتحقق بعد الخطوة  5، وأن تقليل j في الخطوة  2 يقلل فقط من القيمة المقابلة T _{i −1, j} .

إحدى أهم الخصائص الأساسية، ولكنها غير واضحة من خلال البناء الخوارزمي، هي التناظر:

• إذا ربطت مطابقة روبنسون-شينستيد الجداول ( P ، Q ) بالتبديل σ ، فإنها تربط ( Q ، P ) بالتبديل العكسي σ ⁻¹ .

ويمكن إثبات ذلك، على سبيل المثال، بالرجوع إلى البناء الهندسي لفينو .

خصائص أخرى، وكلها تفترض أن المراسلات تربط الجداول ( P ، Q ) بالتبديل σ = ( σ1 _، ... ، σn ₎ .

• في زوج الجداول ( P ′، Q ′) المرتبطة بالتبديل المعكوس ( σn _، ...، σ1 ₎ ، يكون الجدول P ′ هو منقول الجدول P ، ويكون Q ′ جدولًا محددًا بواسطة Q ، بشكل مستقل عن P (أي منقول الجدول الذي تم الحصول عليه من Q بواسطة عملية شوتزنبرغر ).
• طول أطول سلسلة فرعية متزايدة من σ ₁ ، ... ، σ _n يساوي طول الصف الأول من P (و Q ).
• طول أطول سلسلة فرعية متناقصة من σ ₁ ، ... ، σ _n يساوي طول العمود الأول من P (و Q )، كما يتضح من الخاصيتين السابقتين.
• مجموعة الانحدار { i  : σ _i > σ _{i +1} } لـ σ تساوي مجموعة الانحدار { i  : i +1 في صف أسفل صف i تمامًا } لـ Q.
• حدد المتتاليات الجزئية من π مع مجموعات مؤشراتها. تنص نظرية غرين على أنه لأي عدد صحيح k ≥ 1 ، فإن حجم أكبر مجموعة يمكن كتابتها كاتحاد k متتالية _جزئية متزايدة على الأكثر هو λ₁ + ... + λₖ _. وبالتحديد، λ₁ _يساوي أطول طول لمتتالية جزئية متزايدة من π .
• إذا كانت σ عبارة عن انعكاس ، فإن عدد النقاط الثابتة لـ σ يساوي عدد الأعمدة ذات الطول الفردي في λ .

• البناء الهندسي لفينو ، والذي يقدم تفسيراً تخطيطياً للتطابق.
• أحادي بلاستيك : يمكن استخدام عملية الإدخال لتعريف منتج ترابطي لجداول يونغ ذات مدخلات بين 1 و n ، والذي يشار إليه باسم أحادي بلاستيك من الرتبة n .

• فولتون، ويليام (1997)، جداول يونغ ، نصوص طلاب الجمعية الرياضية بلندن، المجلد  35، مطبعة جامعة كامبريدج ، رقم ISBN 978-0-521-56144-0MR 1464693​ .
• كنوت، دونالد إي. (1970)، "التباديل والمصفوفات وجداول يونغ المعممة" ، مجلة المحيط الهادئ للرياضيات ، 34 (3): 709-727 ، doi : 10.2140/pjm.1970.34.709 ، MR 0272654 
• روبنسون، جي. دي بي. (1938)، "حول تمثيلات المجموعة المتناظرة"، المجلة الأمريكية للرياضيات ، 60 (3): 745-760 ، doi : 10.2307/2371609 ، JSTOR 2371609 ، Zbl 0019.25102  .
• ساغان، بي إي (2001)، المجموعة المتناظرة ، نصوص الدراسات العليا في الرياضيات، المجلد  203، نيويورك: سبرينغر-فيرلاغ، رقم ISBN 0-387-95067-2.
• شينستيد، سي. (1961)، "أطول المتتاليات الفرعية المتزايدة والمتناقصة"، المجلة الكندية للرياضيات ، 13 : 179-191 ، doi : 10.4153/CJM-1961-015-3 ، MR 0121305 .
• ستانلي، ريتشارد ب. (1999)، التوافقية العددية، المجلد 2 ، دراسات كامبريدج في الرياضيات المتقدمة، المجلد  62، مطبعة جامعة كامبريدج ، رقم ISBN 978-0-521-56069-6MR 1676282​ .
• زيليفينسكي، أ. ف. (1981)، "تعميم لقاعدة ليتلوود-ريتشاردسون وتطابق روبنسون-شينستيد-كنوث"، مجلة الجبر ، 69 (1): 82-94 ، doi : 10.1016/0021-8693(81)90128-9 ، MR 0613858 .

• غرين، جيمس أ. (2007). التمثيلات متعددة الحدود لـ GL _n . سلسلة محاضرات في الرياضيات. المجلد  830. مع ملحق حول تناظر شينستيد ومسارات ليتلمان بقلم ك. إردمان، ج. أ. غرين، وم. شوكر (  الطبعة الثانية المصححة والموسعة). برلين: سبرينغر-فيرلاغ . ISBN 978-3-540-46944-5. Zbl 1108.20044 . 

• فان ليوين، MAA (2001) [1994]، "مراسلة روبنسون-شينستيد" ، موسوعة الرياضيات ، مطبعة EMS
• ويليامز، ل.، الرسوم المتحركة التفاعلية لخوارزمية روبنسون-شينستيد