نظرية فروشت

نظرية فروشت هي نتيجة في نظرية المخططات الجبرية ، افترضها دينيس كونيغ عام 1936 ^{[ 1 ]} وأثبتها روبرت فروشت عام 1939. ^{[ 2 ]} تنص على أن كل زمرة منتهية هي زمرة تناظرات مخطط غير موجه منتهٍ . وبشكل أدق، لأي زمرة منتهية${\displaystyle G}$يوجد عدد لا نهائي من الرسوم البيانية البسيطة المتصلة غير المتماثلة بحيث تكون مجموعة التماثل الذاتي لكل منها متماثلة مع${\displaystyle G}$.

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

باستثناء ثلاث مجموعات - المجموعات الدورية من الرتب 3 و4 و5 - يمكن تمثيل كل مجموعة بتناظرات رسم بياني لا تحتوي رؤوسه إلا على مدارين . وبالتالي، فإن عدد رؤوس الرسم البياني لا يتجاوز ضعف رتبة المجموعة. مع وجود مجموعة أكبر من الاستثناءات، يمكن تمثيل معظم المجموعات المنتهية بتناظرات رسم بياني متعدٍّ على الرؤوس ، حيث يساوي عدد رؤوسه رتبة المجموعة. ^{[ 4 ]}

توجد صيغ أقوى لنظرية فروشت تُظهر أن بعض العائلات المحدودة من الرسوم البيانية لا تزال تحتوي على عدد كافٍ من الرسوم البيانية لتحقيق أي زمرة تناظر. أثبت فروشت ^{[ 5 ]} أنه في الواقع يوجد عدد قابل للعد من الرسوم البيانية المنتظمة من الدرجة 3 التي تتمتع بالخاصية المطلوبة؛ على سبيل المثال، الرسم البياني لفروشت ، وهو رسم بياني منتظم من الدرجة 3 يحتوي على 12 رأسًا و18 ضلعًا، ليس له أي تناظرات غير تافهة، مما يوفر تحقيقًا لهذا النوع للزمرة التافهة . أظهر جيرت سابيدوسي أنه يمكن تحقيق أي زمرة على أنها زمر تناظر لعدد قابل للعد من الرسوم البيانية المنتظمة من الدرجة k ، أو الرسوم البيانية المتصلة بـ k رأسًا ، أو الرسوم البيانية اللونية من الدرجة k ، لجميع قيم k الصحيحة الموجبة ( مع${\displaystyle k\geq 3}$للرسوم البيانية المنتظمة و${\displaystyle k\geq 2}$^{[ 6 ]} من حقيقة أنه يمكن إعادة بناء أي رسم بياني من الترتيب الجزئي لاحتواء حوافه ورؤوسه، وأن كل ترتيب جزئي محدود يكافئ، وفقًا لنظرية تمثيل بيركوف، شبكة توزيعية محدودة ، فإنه يترتب على ذلك أنه يمكن تمثيل كل زمرة محدودة على أنها تناظرات شبكة توزيعية ، وتناظرات الرسم البياني لهذه الشبكة، وهو رسم بياني وسيط . ^{[ 3 ]} من الممكن تمثيل كل زمرة محدودة على أنها زمرة تناظرات رسم بياني منتظم بقوة . ^{[ 7 ]} يمكن أيضًا تمثيل كل زمرة محدودة على أنها تناظرات رسم بياني ذي عدد تمييز اثنين: يمكن تلوين الرسم البياني (بشكل غير صحيح) بلونين بحيث لا يحتفظ أي من تناظرات الرسم البياني بهذا التلوين. ^{[ 8 ]}

مع ذلك، تعجز بعض فئات الرسوم البيانية المهمة عن تمثيل جميع الزمر كتناظرات لها. وقد وصفت كاميل جوردان زمر التناظر للأشجار بأنها أصغر مجموعة من الزمر المنتهية التي تحتوي على الزمرة التافهة ، والمغلقة تحت الضرب المباشر فيما بينها، وتحت الضرب الإكليلي مع الزمر المتناظرة ؛ ^{[ 9 ]} وعلى وجه الخصوص، فإن الزمرة الدورية من الرتبة الثالثة ليست زمرة تناظر لشجرة. كما أن الرسوم البيانية المستوية لا تستطيع تمثيل جميع الزمر كتناظرات لها؛ فعلى سبيل المثال، الزمر البسيطة المنتهية الوحيدة التي تمثل تناظرات للرسوم البيانية المستوية هي الزمر الدورية والزمرة المتناوبة.${\displaystyle A_{5}}$^{[ 10 ]} وبشكل أعم، فإن كل عائلة رسوم بيانية مغلقة جزئيًا غير قادرة على تمثيل جميع الزمر المنتهية بتناظرات رسومها البيانية. ^{[ 11 ]} ويفترض لازلو باباي ، بشكل أقوى، أن كل عائلة مغلقة جزئيًا لا يمكنها تمثيل سوى عدد محدود من الزمر البسيطة المنتهية غير الدورية. ^{[ 12 ]}

قام إزبكي بتوسيع هذه النتائج في عام 1959، وأظهر وجود عدد لا يُحصى من الرسوم البيانية اللانهائية التي تُحقق أي زمرة تناظر منتهية. ^{[ 13 ]} وأخيرًا، أثبت يوهانس دي غروت وجيرت سابيدوسي بشكل مستقل في عامي 1959/1960 أن أي زمرة (مع إسقاط افتراض كونها منتهية، ولكن مع افتراض بديهية الاختيار ) يُمكن تحقيقها كزمرة تناظرات رسم بياني لانهائي؛ وبدلاً من ذلك، تُلغي بديهية الانتظام الحاجة إلى الاختيار. ^{[ 14 ] [ 15 ]} علاوة على ذلك، فإن هذا الاستلزام دقيق، حيث توجد نماذج لـ ZF ناقص الانتظام لا تنطبق عليها نظرية فروخت للزمر اللانهائية. ^{[ 16 ]}