رسم بياني لكايلي

في الرياضيات ، يُعرف مخطط كايلي ، أو مخطط ألوان كايلي ، أو مخطط المجموعة ، أو المجموعة اللونية ، ^{[ 1 ]} بأنه مخطط يُجسد البنية المجردة لمجموعة . يستند تعريفه إلى نظرية كايلي (نسبةً إلى آرثر كايلي )، ويستخدم مجموعة محددة من المولدات للمجموعة. يُعدّ مخطط كايلي أداةً أساسيةً في نظرية المجموعات التوافقية والهندسية . كما أن بنيته وتناظره يجعلان منه مرشحًا مثاليًا لبناء مخططات التوسيع .

يترك${\displaystyle G}$كن مجموعة و${\displaystyle S}$لتكن مجموعة مولدة من${\displaystyle G}$الرسم البياني لكايلي${\displaystyle \Gamma =\Gamma (G,S)}$هو رسم بياني موجه ملون الحواف تم إنشاؤه على النحو التالي: ^{[ 2 ]}

• كل عنصر${\displaystyle g}$ل${\displaystyle G}$يتم تعيين رأس: مجموعة رؤوس${\displaystyle \Gamma }$يُعرف بـ${\displaystyle G.}$
• كل عنصر${\displaystyle s}$ل${\displaystyle S}$يتم تخصيص لون له${\displaystyle c_{s}}$.
• لكل${\displaystyle g\in G}$و${\displaystyle s\in S}$يوجد حافة لونية موجهة${\displaystyle c_{s}}$من الرأس المقابل لـ${\displaystyle g}$إلى ما يتوافق مع${\displaystyle gs}$.

لا يشترط كل اتفاق ذلك${\displaystyle S}$قم بإنشاء المجموعة. إذا${\displaystyle S}$ليست مجموعة مولدة لـ${\displaystyle G}$، ثم${\displaystyle \Gamma }$غير متصل ، ويمثل كل مكون متصل مجموعة مشاركة للمجموعة الفرعية المولدة بواسطة${\displaystyle S}$.

إذا كان عنصر${\displaystyle s}$ل${\displaystyle S}$هو عكس نفسه،${\displaystyle s=s^{-1},}$ثم يتم تمثيلها عادةً بحافة غير موجهة.

المجموعة${\displaystyle S}$يُفترض غالبًا أن تكون محدودة، خاصة في نظرية الزمر الهندسية ، وهو ما يتوافق مع${\displaystyle \Gamma }$كونها محدودة محليًا و${\displaystyle G}$كونها مولدة بشكل نهائي.

المجموعة${\displaystyle S}$يُفترض أحيانًا أنه متناظر (${\displaystyle S=S^{-1}}$) ولا يحتوي على عنصر محايد للمجموعة . في هذه الحالة، يمكن تمثيل الرسم البياني لكايلي غير الملون كرسم بياني بسيط غير موجه .

• لنفترض أن${\displaystyle G=\mathbb {Z} }$هي المجموعة الدورية اللانهائية والمجموعة${\displaystyle S}$يتكون من المولد القياسي 1 ومعكوسه (-1 في الترميز الجمعي)؛ ثم يكون الرسم البياني لكايلي مسارًا لا نهائيًا.
• وبالمثل، إذا${\displaystyle G=\mathbb {Z} _{n}}$هي المجموعة الدورية المنتهية من الرتبة${\displaystyle n}$والمجموعة${\displaystyle S}$يتكون من عنصرين، مولد قياسي لـ${\displaystyle G}$وإذا كان معكوسه، فإن مخطط كايلي هو الدورة${\displaystyle C_{n}}$. وبشكل عام، فإن مخططات كايلي للمجموعات الدورية المنتهية هي بالضبط المخططات الدائرية .
• إن مخطط كايلي للضرب المباشر للمجموعات (مع اعتبار الضرب الديكارتي للمجموعات المولدة مجموعة مولدة) هو الضرب الديكارتي لمخططات كايلي المناظرة. ^{[ 3 ]} وبالتالي، فإن مخطط كايلي للمجموعة الأبيلية${\displaystyle \mathbb {Z} ^{2}}$مع مجموعة المولدات المكونة من أربعة عناصر${\displaystyle (\pm 1,0),(0,\pm 1)}$هي الشبكة اللانهائية على المستوى${\displaystyle \mathbb {R} ^{2}}$أما بالنسبة للمنتج المباشر${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{m}}$باستخدام مولدات مماثلة، يكون مخطط كايلي هو${\displaystyle n\times m}$شبكة محدودة على سطح حلقي .

• رسم بياني لكايلي لمجموعة الزوايا الثنائية${\displaystyle D_{4}}$على مولدين${\displaystyle a}$و${\displaystyle b}$يظهر الشكل على اليسار. تشير الأسهم الحمراء إلى التكوين مع${\displaystyle a}$. منذ${\displaystyle b}$هي معكوسة ذاتيًا ، الخطوط الزرقاء، التي تمثل التركيب مع${\displaystyle b}$، وهي غير موجهة. لذلك، فإن الرسم البياني مختلط: له ثمانية رؤوس، وثمانية أسهم، وأربعة حواف. جدول كايلي للمجموعة${\displaystyle D_{4}}$يمكن استخلاص ذلك من العرض التقديمي الجماعي$${\displaystyle \langle a,b\mid a^{4}=b^{2}=e,ab=ba^{3}\rangle .}$$رسم بياني مختلف لكايلي${\displaystyle D_{4}}$يظهر على اليمين.${\displaystyle b}$لا يزال الانعكاس أفقيًا ويتم تمثيله بخطوط زرقاء، و${\displaystyle c}$هو انعكاس قطري ويُمثَّل بالخطوط الوردية. ولأن كلا الانعكاسين معكوسان ذاتيًا، فإن الرسم البياني لكايلي على اليمين غير موجه تمامًا. يتوافق هذا الرسم البياني مع العرض التقديمي.$${\displaystyle \langle b,c\mid b^{2}=c^{2}=e,bcbc=cbcb\rangle .}$$
• الرسم البياني لكايلي للمجموعة الحرة على مولدين${\displaystyle a}$و${\displaystyle b}$المقابل للمجموعة${\displaystyle S=\{a,b,a^{-1},b^{-1}\}}$يظهر ذلك في أعلى المقال، مع${\displaystyle e}$كونها العنصر المحايد. يمثل التحرك على طول الحافة إلى اليمين عملية الضرب من اليمين بواسطة${\displaystyle a,}$بينما يتوافق التحرك على طول الحافة لأعلى مع الضرب في${\displaystyle b.}$ بما أن المجموعة الحرة لا تحتوي على علاقات ، فإن مخطط كايلي لا يحتوي على دورات : إنه شجرة منتظمة رباعية لانهائية . وهو عنصر أساسي في برهان مفارقة باناخ-تارسكي .
• وبشكل أعم، فإن شبكة بيث أو شجرة كايلي هي رسم بياني كايلي للمجموعة الحرة على${\displaystyle n}$مولدات. عرض تقديمي لمجموعة${\displaystyle G}$بواسطة${\displaystyle n}$تتوافق المولدات مع تشاكل شامل من المجموعة الحرة على${\displaystyle n}$مولدات للمجموعة${\displaystyle G,}$تحديد خريطة من شجرة كايلي إلى رسم كايلي البياني لـ${\displaystyle G}$. تفسير الرسوم البيانية طوبولوجيًا على أنها مجمعات تبسيطية أحادية البعد ، الشجرة اللانهائية المتصلة ببساطة هي الغطاء الشامل لرسم كايلي البياني؛ ونواة التطبيق هي المجموعة الأساسية لرسم كايلي البياني.

• رسم بياني لكايلي لمجموعة هايزنبرغ المنفصلة$${\displaystyle \left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}},\ x,y,z\in \mathbb {Z} \right\}}$$يظهر الشكل على اليمين. المولدات المستخدمة في الصورة هي المصفوفات الثلاث.${\displaystyle X,Y,Z}$يتم تحديدها من خلال التباديل الثلاثة للأرقام 1، 0، 0 للمدخلات${\displaystyle x,y,z}$إنها تلبي العلاقات${\displaystyle Z=XYX^{-1}Y^{-1},XZ=ZX,YZ=ZY}$ويمكن فهم ذلك أيضاً من الصورة. هذه مجموعة لانهائية غير تبادلية ، وعلى الرغم من كونها مضمنة في فضاء ثلاثي الأبعاد ، فإن مخطط كايلي له نمو حجمي رباعي الأبعاد . ^{[ 4 ]}

المجموعة${\displaystyle G}$يؤثر على نفسه عن طريق الضرب من اليسار (انظر نظرية كايلي ). يمكن اعتبار هذا بمثابة فعل لـ${\displaystyle G}$على مخطط كايلي الخاص به. بشكل صريح، عنصر${\displaystyle h\in G}$يرسم رأسًا${\displaystyle g\in V(\Gamma )}$إلى الرأس${\displaystyle hg\in V(\Gamma ).}$يتم الحفاظ على مجموعة حواف الرسم البياني لكايلي ولونها من خلال هذا الإجراء: الحافة${\displaystyle (g,gs)}$يتم تعيينها على الحافة${\displaystyle (hg,hgs)}$كلاهما ذو لون${\displaystyle c_{s}}$في الواقع، جميع التشاكلات الذاتية للرسم البياني الموجه الملون${\displaystyle \Gamma }$تكون على هذا الشكل، بحيث${\displaystyle G}$متماثل مع مجموعة التناظر لـ${\displaystyle \Gamma }$[ ^{ملاحظة 1 ] [ ملاحظة 2 ]}

إن عملية الضرب من اليسار لمجموعة على نفسها هي عملية متعدية ، وعلى وجه الخصوص، فإن مخططات كايلي هي مخططات متعدية على مستوى الرؤوس . وفيما يلي نوع من عكس ذلك:

لاستعادة المجموعة${\displaystyle G}$ومجموعة التوليد${\displaystyle S}$من الرسم البياني الموجه غير المصنف${\displaystyle \Gamma }$حدد رأسًا${\displaystyle v_{1}\in V(\Gamma )}$وقم بتسميته بالعنصر المحايد للمجموعة. ثم قم بتسمية كل رأس${\displaystyle v}$ل${\displaystyle \Gamma }$بفضل العنصر الفريد من${\displaystyle G}$تلك الخرائط${\displaystyle v_{1}}$ل${\displaystyle v.}$المجموعة${\displaystyle S}$من مولدات${\displaystyle G}$وهذا ينتج عنه${\displaystyle \Gamma }$كما هو الحال في الرسم البياني لكايلي${\displaystyle \Gamma (G,S)}$هي مجموعة تصنيفات الجيران الخارجيين لـ${\displaystyle v_{1}}$. منذ${\displaystyle \Gamma }$إذا كانت غير ملونة، فقد تحتوي على عدد أكبر من التشاكلات الذاتية للرسوم البيانية الموجهة مقارنةً بخرائط الضرب اليسرى، على سبيل المثال التشاكلات الذاتية للمجموعات لـ${\displaystyle G}$والتي تبدل${\displaystyle S}$.

• رسم كايلي البياني${\displaystyle \Gamma (G,S)}$يعتمد ذلك بشكل أساسي على اختيار المجموعة${\displaystyle S}$من المولدات. على سبيل المثال، إذا كانت مجموعة المولدات${\displaystyle S}$لديه${\displaystyle k}$إذا كان عدد العناصر في الرسم البياني لكايلي هو${\displaystyle k}$الوارد و${\displaystyle k}$الحواف الموجهة الخارجة. في حالة مجموعة توليد متناظرة${\displaystyle S}$مع${\displaystyle r}$العناصر، مخطط كايلي هو مخطط منتظم موجه من الدرجة${\displaystyle r.}$
• تشير الدورات (أو المسارات المغلقة ) في مخطط كايلي إلى العلاقات بين عناصر${\displaystyle S.}$في البناء الأكثر تفصيلاً لمركب كايلي لمجموعة ما، يتم "ملء" المسارات المغلقة التي تتوافق مع العلاقات بواسطة المضلعات . وهذا يعني أن مشكلة بناء مخطط كايلي لعرض معين تصبح أكثر تعقيدًا.${\displaystyle {\mathcal {P}}}$وهو ما يعادل حل المسألة اللفظية لـ${\displaystyle {\mathcal {P}}}$[ ^{1 ]​}
• لو${\displaystyle f:G'\to G}$هو تشاكل زمرة شاملة وصور عناصر المجموعة المولدة${\displaystyle S'}$ل${\displaystyle G'}$إذا كانت متميزة، فإنها تُنشئ تغطية للرسوم البيانية.$${\displaystyle {\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),}$$أين${\displaystyle S=f(S').}$على وجه الخصوص، إذا كانت مجموعة${\displaystyle G}$لديه${\displaystyle k}$المولدات، وكلها من رتبة مختلفة عن 2، والمجموعة${\displaystyle S}$يتكون من هذه المولدات بالإضافة إلى معكوساتها، ثم مخطط كايلي${\displaystyle \Gamma (G,S)}$مغطاة بالشجرة المنتظمة اللانهائية من الدرجة${\displaystyle 2k}$المقابل للمجموعة الحرة على نفس مجموعة المولدات.
• بالنسبة لأي رسم بياني من نوع كايلي محدود، يُعتبر غير موجه، فإن ترابط الرؤوس يساوي على الأقل ثلثي درجة الرسم البياني. إذا كانت المجموعة المولدة صغرى (أي أن إزالة أي عنصر، ومعكوسه إن وجد، من المجموعة المولدة لا ينتج عنه مجموعة مولدة)، فإن ترابط الرؤوس يساوي درجة الرسم البياني. أما ترابط الحواف فيساوي درجة الرسم البياني في جميع الحالات. ^{[ 6 ]}
• لو${\displaystyle \rho _{\text{reg}}(g)(x)=gx}$هو التمثيل المنتظم الأيسر مع${\displaystyle |G|\times |G|}$الشكل المصفوفي المشار إليه${\displaystyle [\rho _{\text{reg}}(g)]}$، مصفوفة التجاور لـ${\displaystyle \Gamma (G,S)}$يكون${\textstyle A=\sum _{s\in S}[\rho _{\text{reg}}(s)]}$.
• كل شخصية جماعية${\displaystyle \chi }$من المجموعة${\displaystyle G}$يُنتج متجهًا ذاتيًا لمصفوفة التجاور لـ${\displaystyle \Gamma (G,S)}$القيمة الذاتية المرتبطة هي $${\displaystyle \lambda _{\chi }=\sum _{s\in S}\chi (s),}$$والذي، عندما${\displaystyle G}$أبيلية، تأخذ الشكل$${\displaystyle \sum _{s\in S}e^{2\pi ijs/|G|}}$$للأعداد الصحيحة${\displaystyle j=0,1,\dots ,|G|-1.}$وعلى وجه الخصوص، فإن القيمة الذاتية المرتبطة بالحرف التافه (الذي يجعل كل عنصر يساوي 1) هي درجة${\displaystyle \Gamma (G,S)}$أي ترتيب${\displaystyle S}$. لو${\displaystyle G}$هي مجموعة أبيلية ، يوجد بالضبط${\displaystyle |G|}$تُحدد الخصائص جميع القيم الذاتية. ويُعطى الأساس المتعامد المقابل للمتجهات الذاتية بواسطة${\displaystyle v_{j}={\tfrac {1}{\sqrt {|G|}}}{\begin{pmatrix}1&e^{2\pi ij/|G|}&e^{2\cdot 2\pi ij/|G|}&e^{3\cdot 2\pi ij/|G|}&\cdots &e^{(|G|-1)2\pi ij/|G|}\end{pmatrix}}.}$من المثير للاهتمام ملاحظة أن هذه القاعدة الذاتية مستقلة عن المجموعة المولدة${\displaystyle S}$.
  وبشكل أعم بالنسبة للمجموعات المولدة المتناظرة، خذ${\displaystyle \rho _{1},\dots ,\rho _{k}}$مجموعة كاملة من التمثيلات غير القابلة للاختزال لـ${\displaystyle G,}$ودع${\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)}$مع مجموعة القيم الذاتية${\displaystyle \Lambda _{i}(S)}$ثم مجموعة القيم الذاتية لـ${\displaystyle \Gamma (G,S)}$هو بالضبط${\textstyle \bigcup _{i}\Lambda _{i}(S),}$حيث القيمة الذاتية${\displaystyle \lambda }$يظهر بتعدد${\displaystyle \dim(\rho _{i})}$لكل ظهور لـ${\displaystyle \lambda }$كقيمة ذاتية لـ${\displaystyle \rho _{i}(S).}$

إذا اعتبرنا بدلاً من ذلك رؤوسًا مشاركة يمنى لمجموعة جزئية ثابتة${\displaystyle H,}$يحصل المرء على بنية ذات صلة، وهي مخطط شريير للمجموعات المشتركة ، والذي يمثل أساس تعداد المجموعات المشتركة أو عملية تود-كوكسيتر .

يمكن الحصول على معرفة حول بنية المجموعة من خلال دراسة مصفوفة التجاور للرسم البياني، وتحديدًا تطبيق نظريات نظرية الرسم البياني الطيفي . وعلى العكس من ذلك، بالنسبة للمجموعات المولدة المتناظرة، فإن نظرية الطيف والتمثيل لـ${\displaystyle \Gamma (G,S)}$يرتبطان ببعضهما ارتباطًا مباشرًا: خذ${\displaystyle \rho _{1},\dots ,\rho _{k}}$مجموعة كاملة من التمثيلات غير القابلة للاختزال لـ${\displaystyle G,}$ودع${\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)}$مع القيم الذاتية${\displaystyle \Lambda _{i}(S)}$ثم مجموعة القيم الذاتية لـ${\displaystyle \Gamma (G,S)}$هو بالضبط${\textstyle \bigcup _{i}\Lambda _{i}(S),}$حيث القيمة الذاتية${\displaystyle \lambda }$يظهر بتعدد${\displaystyle \dim(\rho _{i})}$لكل ظهور لـ${\displaystyle \lambda }$كقيمة ذاتية لـ${\displaystyle \rho _{i}(S).}$

جنس المجموعة هو أصغر جنس لأي رسم بياني لكايلي لتلك المجموعة . ^{[ 7 ]}

متى${\displaystyle S=S^{-1}}$، الرسم البياني لكايلي${\displaystyle \Gamma (G,S)}$يكون${\displaystyle |S|}$بما أن الرسم البياني منتظم، يمكن استخدام التقنيات الطيفية لتحليل خصائص تمدده . وبالنسبة للمجموعات الأبيلية تحديدًا، فإن القيم الذاتية لرسم كايلي البياني أسهل في الحساب، وتُعطى بواسطة${\textstyle \lambda _{\chi }=\sum _{s\in S}\chi (s)}$مع قيمة ذاتية عليا تساوي${\displaystyle |S|}$لذلك يمكننا استخدام متباينة شيغر لتقييد نسبة تمدد الحافة باستخدام الفجوة الطيفية.

يمكن استخدام نظرية التمثيل لإنشاء رسوم بيانية متوسعة من نوع كايلي، على شكل خاصية كازدان (T) . العبارة التالية صحيحة: ^{[ 9 ]}

إذا كانت مجموعة منفصلة${\displaystyle G}$يمتلك ممتلكات كازدان (T)، و${\displaystyle S}$هي مجموعة مولدة متناظرة ومنتهية من${\displaystyle G}$إذن يوجد ثابت${\displaystyle c>0}$بالاعتماد فقط على${\displaystyle G,S}$بحيث يكون لأي خارج قسمة محدود${\displaystyle Q}$ل${\displaystyle G}$رسم كايلي البياني لـ${\displaystyle Q}$فيما يتعلق بصورة${\displaystyle S}$هو${\displaystyle c}$-موسع.

على سبيل المثال المجموعة${\displaystyle G=\mathrm {SL} _{3}(\mathbb {Z} )}$لها الخاصية (T) ويتم توليدها بواسطة المصفوفات الأولية وهذا يعطي أمثلة واضحة نسبياً للرسوم البيانية الموسعة.

الرسم البياني التكاملي هو الرسم البياني الذي تكون جميع قيمه الذاتية أعدادًا صحيحة. وبينما لا يزال التصنيف الكامل للرسوم البيانية التكاملية مسألة مفتوحة ، فإن رسوم كايلي البيانية لبعض المجموعات تكون دائمًا تكاملية. باستخدام التوصيفات السابقة لطيف رسوم كايلي البيانية، لاحظ أن${\displaystyle \Gamma (G,S)}$تكون صحيحة إذا وفقط إذا كانت القيم الذاتية لـ${\displaystyle \rho (S)}$تُعد جزءًا لا يتجزأ من كل تمثيل${\displaystyle \rho }$ل${\displaystyle G}$.

طُرحت مخططات كايلي لأول مرة في سياق الزمر المنتهية على يد آرثر كايلي عام 1878. ^{[ 2 ]} أعاد ماكس دين، في محاضراته غير المنشورة حول نظرية الزمر بين عامي 1909 و1910، تقديم مخططات كايلي تحت اسم "مخطط الزمر" (Gruppenbild)، مما أدى إلى ظهور نظرية الزمر الهندسية المعروفة اليوم. وكان أهم تطبيقاته حل مسألة الكلمات للزمرة الأساسية للأسطح ذات الجنس ≥ 2 ، وهي مسألة طوبولوجية تُعنى بتحديد المنحنيات المغلقة على السطح التي تتقلص إلى نقطة. ^{[ 12 ]}

• رسم بياني متعدٍ على الرؤوس
• مجموعة مولدة لمجموعة
• تخمين لوفاس
• دورات متصلة مكعبة
• نظرية الرسم البياني الجبرية
• الرسم البياني الدوري (الجبر)

• مخططات كايلي
• وايسشتاين، إريك دبليو. "مخطط كايلي" . عالم الرياضيات .