مجمع كليك

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

إنّ مُركّب الزمر X ( G ) للرسم البياني غير الموجّه G هو مُركّب تبسيطي مُجرّد (أي عائلة من المجموعات المنتهية المغلقة تحت عملية أخذ المجموعات الجزئية)، ويتكوّن من مجموعات الرؤوس في زمر G. أي مجموعة جزئية من زمرة هي نفسها زمرة، لذا فإنّ عائلة المجموعات هذه تُلبّي شرط المُركّب التبسيطي المُجرّد، وهو أن كل مجموعة جزئية من مجموعة في العائلة يجب أن تكون أيضًا في العائلة.

يمكن أيضًا النظر إلى مُركَّب الزمر على أنه فضاء طوبولوجي، حيث تُمثَّل كل زمرة من k رأسًا بمُجَسَّم بسيط ذي بُعد k – 1. الهيكل الأحادي لـ X ( G ) (المعروف أيضًا باسم الرسم البياني الأساسي للمُركَّب) هو رسم بياني غير مُوجَّه، يحتوي على رأس لكل مجموعة من عنصر واحد في العائلة ^، وحافة لكل مجموعة من عنصرين في العائلة؛ وهو مُتماثل مع G. ^{[ 1} ]

إنّ مُركّب الاستقلال I ( G ) للرسم البياني غير الموجّه G هو مُركّب تبسيطي مُجرّد يتكوّن من مجموعات الرؤوس في المجموعات المستقلة لـ G. ويُكافئ مُركّب الزمرة لـ G مُركّب الاستقلال للرسم البياني المُكمّل لـ G.

مجمع العلم هو مجمع تبسيطي مجرد مع خاصية إضافية تسمى "محدد-2": لكل مجموعة فرعية S من الرؤوس، إذا كان كل زوج من الرؤوس في S موجودًا في المجمع، فإن S نفسها موجودة في المجمع أيضًا.

كل مجموعة من الزمر هي مجموعة من الأعلام: إذا كان كل زوج من الرؤوس في S عبارة عن زمرة بحجم 2، فهناك حافة بينهما، لذا فإن S عبارة عن زمرة.

كل مُركّب علم هو مُركّب زمرة: إذا كان لدينا مُركّب علم، نُعرّف رسمًا بيانيًا G على مجموعة جميع الرؤوس، حيث يكون رأسان u وv متجاورين في G إذا وفقط إذا كان {u,v} ينتمي إلى المُركّب (يُسمى هذا الرسم البياني الهيكل الأحادي للمُركّب ). بحسب تعريف مُركّب العلم، فإن كل مجموعة من الرؤوس المتصلة ثنائيًا تنتمي إلى المُركّب. لذلك، فإن مُركّب العلم يُساوي مُركّب الزمرة على G.

وبالتالي، فإنّ مُركّبات الأعلام ومُركّبات الزمر هي في جوهرها شيء واحد. مع ذلك، في كثير من الحالات، يكون من الأنسب تعريف مُركّب الأعلام مباشرةً من بيانات أخرى غير الرسم البياني، بدلاً من تعريفه بشكل غير مباشر كمُركّب زمر لرسم بياني مُستمد من تلك البيانات. ^{[ 2 ]}

عرّف ميخائيل غروموف شرط عدم وجود دلتا بأنه شرط كون الشيء عبارة عن مجموعة أعلام.

تُعرف مُركّبات الزمر أيضًا باسم مُركّبات ويتني ، نسبةً إلى هاسلر ويتني . التثليث الويتني ، أو التثليث النظيف، لمتشعب ثنائي الأبعاد هو تضمين للرسم البياني G على المتشعب بحيث يكون كل وجه مثلثًا وكل مثلث وجهًا. إذا كان للرسم البياني G تثليث ويتني، فلا بد أن يُشكّل مُركّبًا خلويًا مُتماثلًا مع مُركّب ويتني الخاص بـ G. في هذه الحالة، يكون المُركّب (عند النظر إليه كفضاء طوبولوجي) مُتماثلًا شكليًا مع المتشعب الأساسي. يحتوي الرسم البياني G على مُركّب زمر ثنائي الأبعاد، ويمكن تضمينه كتثليث ويتني، إذا وفقط إذا كان G دوريًا محليًا ؛ وهذا يعني أنه لكل رأس v في الرسم البياني، يُشكّل الرسم البياني الفرعي المُستحثّ المُكوّن من جيران v دورةً واحدة. ^{[ 3 ]}

الرسم البياني الأولي G ( H ) للرسم البياني الفائق هو الرسم البياني على نفس مجموعة الرؤوس الذي تكون حوافه أزواج الرؤوس التي تظهر معًا في نفس الحافة الفائقة . يُقال إن الرسم البياني الفائق متطابق إذا كانت كل زمرة عظمى في رسمه البياني الأولي حافة فائقة، أو بصورة مكافئة، إذا كانت كل زمرة في رسمه البياني الأولي موجودة في حافة فائقة ما. ^{[ 4 ]} إذا كان مطلوبًا أن يكون الرسم البياني الفائق مغلقًا تنازليًا (بحيث يحتوي على جميع الحواف الفائقة الموجودة في حافة فائقة ما)، فإن الرسم البياني الفائق يكون متطابقًا تحديدًا عندما يكون مُركبًا من الأعلام. هذا يربط لغة الرسوم البيانية الفائقة بلغة المُركبات التبسيطية.

التقسيم المركزي لأي مُركّب خلوي C هو مُركّب علم، حيث يحتوي على رأس واحد لكل خلية من خلايا C. تُشكّل مجموعة رؤوس التقسيم المركزي مُركّبًا بسيطًا إذا وفقط إذا شكّلت المجموعة المُقابلة من خلايا C علمًا (سلسلة في ترتيب تضمين الخلايا). ^{[ 2 ]} على وجه الخصوص، يُؤدي التقسيم المركزي لمُركّب خلوي على مُتشعب ثنائي الأبعاد إلى تثليث ويتني لهذا المُتشعب.

يتألف مُركّب الترتيب لمجموعة مُرتبة جزئيًا من سلاسل ( مجموعات جزئية مُرتبة كليًا ) الترتيب الجزئي. إذا كان كل زوج من مجموعة جزئية ما مُرتبًا في حد ذاته، فإن المجموعة الجزئية بأكملها تُشكّل سلسلة، وبالتالي يُحقق مُركّب الترتيب شرط عدم وجود دلتا. يُمكن تفسيره على أنه مُركّب الزمر لمخطط قابلية المقارنة للترتيب الجزئي. ^{[ 2 ]}

يتألف مُركّب المطابقة للرسم البياني من مجموعات الحواف التي لا تشترك أي حافتين منها في نقطة نهاية واحدة؛ وتُحقق هذه المجموعة شرط عدم وجود دلتا. ويمكن اعتباره مُركّب الزمر للرسم البياني المُكمّل للرسم البياني الخطي للرسم البياني المُعطى. وعند الإشارة إلى مُركّب المطابقة دون أي رسم بياني مُحدد في السياق، فإنه يعني مُركّب المطابقة للرسم البياني الكامل . يُعرف مُركّب المطابقة للرسم البياني الثنائي الكامل K_{_{m , n}} باسم مُركّب رقعة الشطرنج . وهو الرسم البياني للزمر للرسم البياني المُكمّل لرسم بياني للرخ ، ^{[ 5 ]} ويمثل كل مُجسّم بسيط فيه موضعًا للرخ على رقعة شطرنج m × n بحيث لا يهاجم أي رخين بعضهما البعض. عندما m = n ± 1، يُشكّل مُركّب رقعة الشطرنج شبه مُتشعب .      

إن مجموعة فيتوريس-ريبس لمجموعة من النقاط في فضاء متري هي حالة خاصة من مجموعة الزمر، تتكون من الرسم البياني للقرص الواحد للنقاط؛ ومع ذلك، يمكن تفسير كل مجموعة زمر X ( G) على أنها مجموعة فيتوريس-ريبس لمقياس أقصر مسار على الرسم البياني الأساسي G.

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

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

أثبت ميشولام ^{[ 7 ]} النظرية التالية حول تماثل مُركّب الزمرة. بفرض وجود أعداد صحيحة${\displaystyle l\geq 1,t\geq 0}$لنفترض أن الرسم البياني G يحقق خاصية تسمى${\displaystyle P(l,t)}$وهذا يعني أن:

• كل مجموعة من${\displaystyle l}$الرؤوس في G لها جار مشترك؛
• توجد مجموعة A من الرؤوس، تحتوي على جار مشترك لكل مجموعة من${\displaystyle l}$الرؤوس، بالإضافة إلى ذلك، فإن الرسم البياني المستحث G [ A ] لا يحتوي، كرسم بياني فرعي مستحث، على نسخة من الهيكل العظمي أحادي البعد للكرة ثمانية الأوجه ذات البعد t .

عندئذٍ، يكون التماثل المختزل من الرتبة j للمركب المعقد X( G ) تافهاً لأي قيمة j بين 0 و${\displaystyle \max(lt,\lfloor {l}/{2}\rfloor )-1}$.

• الرسم البياني البسيط ، وهو نوع من الرسوم البيانية يحتوي على عقدة واحدة لكل مجموعة فرعية من الرسم البياني الأساسي
• الماترويد المقسم ، وهو نوع من الماترويدات التي قد تشكل تقاطعاتها مجمعات كليك.

• باندلت، هـ.-ج.؛ تشيبوي، ف. (2008)، "نظرية الرسم البياني المتري والهندسة: دراسة استقصائية"، في غودمان، ج.إ .؛ باتش، ج .؛ بولاك، ر. (محررون)، دراسات استقصائية حول الهندسة المنفصلة والحسابية: بعد عشرين عامًا (ملف PDF) ، الرياضيات المعاصرة، المجلد 453، بروفيدنس، رود آيلاند: الجمعية الأمريكية  للرياضيات، الصفحات 49-86 .
• بيرج، سي. (1989)، المخططات الفائقة: توافقية المجموعات المنتهية ، نورث هولاند، رقم ISBN 0-444-87489-5.
• تشاتيرجي، آي .؛ نيبلو، جي. (2005)، "من فضاءات الجدران إلى مجمعات المكعبات CAT(0)"، المجلة الدولية للجبر والحساب ، 15 ( 5-6 ): 875-885 ، arXiv : math.GT/0309036 ، doi : 10.1142/S0218196705002669 ، S2CID 2786607 .
• ديفيس ، إم دبليو (2002)، "الانحناء غير الموجب ومجموعات الانعكاس"، في دافرمان، آر جيه ؛ شير، آر بي (محرران)، دليل الطوبولوجيا الهندسية ، إلسيفير، ص 373-422 .
• دونغ، إكس.؛ واكس، إم إل (2002)، "لابلاس التوافقي للمركب المطابق" ، المجلة الإلكترونية للتوافقية ، 9 R17، doi : 10.37236/1634.
• هارتسفيلد، ن.؛ رينجل، غيرهارد (1991)، “التثليث النظيف”، Combinatorica ، 11 (2): 145–155 ، دوى : 10.1007 / BF01206358 ، S2CID 28144260 .
• هودكينسون، آي.؛ أوتو، إم. (2003)، "أغطية المخططات الفائقة المطابقة المحدودة ومجموعات غايفمان في البنى المحدودة"، نشرة المنطق الرمزي ، 9 (3): 387-405 ، CiteSeerX 10.1.1.107.5000 ، doi : 10.2178/bsl/1058448678 .
• لاريون، ف.؛ نيومان-لارا، ف .؛ بيزانا، م.أ. (2002)، "تثليثات ويتني، والمحيط المحلي، ورسوم بيانية الزمر المتكررة" ، الرياضيات المتقطعة ، 258 ( 1-3 ): 123-135 ، doi : 10.1016/S0012-365X(02)00266-2.
• مالنيتش، أ.؛ موهار، ب. (1992)، "توليد التثليثات الدورية المحلية للأسطح"، مجلة نظرية التوافيق، السلسلة ب ، 56 (2): 147-164 ، doi : 10.1016/0095-8956(92)90015-P.