چرا گراف پترسنِ ۳-منظمِ ۱۰-گرهای نمی تواند یک گراف کیلی باشد؟

Question

ثابت کنید گراف پترسنِ ۳-منظمِ ۱۰-گره‌ای نمی‌تواند یک گراف کیلی Cayley graph باشد.

ویرایشگر: پرسش‌کننده توضیح بیشتری وارد نکرده‌است.

Answer 1

نخست تعریف گرافِ کِیلی Cayley را برای کاربرانی که این تعریف را نمی‌دانند مرور می‌کنیم. یک گروهِ $G$ و یک مولد برای آن مانند $S$ بردارید. $S$ یک زیرمجموعه از $G$ است که تمام عضوهای گروه بوسیلهٔ اعضای این زیرمجموعه و عمل گروه ساخته می‌شوند. آنگاه یک گراف با توجه به این دوتاییِ مرتبِ $(G,S)$ می‌سازیم که به گرافِ کیلیِ این دوتایی شناخته می‌شود و با نماد $C_{G,S}$ نمایش می‌دهیم. مجموعهٔ گره‌های این گراف عضوهای $G$ هستند و دو گرهٔ $g_1,g_2\in G$ با یک یالِ جهت‌دار از $g_1$ به $g_2$ وصل می‌شود اگر و تنها اگر عضوی در $S$ مانند $h\in S$ وجود داشته باشد که $g_2=g_1h$. معمولا یال‌های این گراف را رنگ می‌کنند و رنگ‌ها را اینگونه انتخاب می‌کنند که برای هر عضو از $S$ یک رنگ متفاوت برمی‌داریم و یال وصل کنندهٔ $g_1$ و $g_2$ را با رنگ مربوط به $h$ رنگ می‌کنیم اگر $h$ عضوی بوده‌است که $g_2=g_1h$ شده‌است. پس این گراف یک گرافِ جهت‌دارِ وزن‌دار است (که به جای نوشتن وزن‌ها به عنوان برچسب روی یال‌ها، با رنگ‌ها وزن‌ها را مشخص می‌کنند).

برای گرافِ پترسن که پیش‌فرض جهت‌دار نیست، پرسش شما اینگونه تعبیر می‌شود که آیا گراف $G$ و مولد $S$ای از $G$ وجود دارد که زمانی که گراف $C_{G,S}$ را رسم می‌کنیم، پس از صرف نظر کردن رنگ‌ها و جهت‌ها گراف پترسن حاصل شود؟

در این پست برای ترسیم گراف‌ها از نرم‌افزار Mathematica استفاده می‌کنم. اگر با چگونگیِ استفاده از نرم‌افزار Mathematica برای کار با مفاهیم نظریهٔ گراف آشنا نیستید می‌توانید پاسخ دیگری که در این سایت قرار داده‌ام را نگاه کنید (این پست). نخست گراف ۳-منظمِ پترسن Petersen با ۱۰ گره را رسم می‌کنیم که ممکن است برای برخی از کاربرها ناآشنا باشد. برای تعریفِ گراف پترسن با $2n$تا گره و درجهٔ هر گره برابر با $r$ باشد از دستورِ PetersenGraph[n,r] استفاده کنید. پس اگر این گراف را Gr1 بنامم باید کد زیر را تایپ کنم.

Gr1=PetersenGraph[5,3]

شکل گراف در زیر آمده‌است.

اکنون به سراغ گراف‌های کیلی می‌رویم. توجه کنید که اگر گراف پترسن‌مان بخواهد کیلی باشد باید یک گروه ۱۰ عضوی وجود داشته باشد که نقشِ $G$ را در تعریف گراف کیلی برایش بازی کند. خوشبختانه تعداد گروه‌های متناهیی تا حد یکریختی متناهی است و بدیهیاً گروه‌های یکریخت گراف‌های کیلیِ یکسانی دارند. حتی فرض کنیم که رشتهٔ شما جبر نباشد یا جبر خوبی نداشته‌باشید و صرفا به قسمت گرافیِ کار بیشتر علاقه دارید، خبر خوب این است که گروه‌های متناهی تا مرتبهٔ خوبی دسته‌بندی شده‌اند و جدول و اطلاعاتشان را با یک جستجوی ساده می‌توانید در اینترنت هم بیابید. برای نمونه در این پیوند https://groupprops.subwiki.org/wiki/Groups_of_order_10 می‌بینید که تنها دو نوع گروه از مرتبه (عدد اصلی)-ِ ۱۰ داریم.

1. گروه دوری از مرتبهٔ ۱۰ که برخی با نماد $C_{10}$ و برخی با نماد $\overline{\mathbb{Z}}_{10}$ (که با گروه رده‌های باقیمانده‌ای به پیمانهٔ ۱۰ و عمل جمع‌شان یکی است) نمایش می‌دهند.
2. گروه تقارن‌ها و دوران‌های روی یک ۵-گوشه که به انگلیسی Dihedral group of order 10 نیز گفته می‌شود و با $D_{10}$ نمایش داده می‌شود (در واقع $D_{2n}$ که $n=5$).

پس کافیست گراف کیلی این دو گروه را رسم کنیم و ببینیم آیا پس از حذف رنگ و جهت با گراف پترسن یکی می‌شوند یا خیر. توجه کنید که گروه نخست مولد تک‌عضوی دارد و گروه دوم مولد دوعضوی دارد. هر ابرگروه از یک مولد، مولد نیز می‌شود ولی گرافِ کیلیِ آنها فقط یال اضافه کردن به گرافِ کیلیِ متناظر به مولد کمینه است پس ما فقط یک مولد را در هر مورد برمی‌داریم که کمینه هم است. پس فقط دو گراف باید رسم کنیم که زیاد زمانگیر نخواهد بود. به هر حال ما این کار را با نرم‌افزار انجام می‌دهیم. ابتدا باید گروه را تعریف کنیم و سپس بخواهیم که گراف کیلی‌اش را رسم کند. اگر با چگونگیِ به کار بردن نرم‌افزار Mathematica برای نظریهٔ گروه‌ها آشنایی ندارید می‌توانید به پاسخ دیگری که در این سایت قرار داده‌ام نگاه کنید (این پست). برای تعریف گروه دوری از مرتبهٔ $n$ از دستورِ CyclicGroup[n] استفاده کنید و برای تعریف گروه تقارن‌ها و دوران‌های روی یک $n$-یالی از دستورِ DihedralGroup[n] استفاده کنید. سپس چون فقط مولد بدیهیِ این گروه‌ها را مدنظر داریم برای تعریف کردن گراف کیلی آنها از دستور CayleyGraph[G] استفاده می‌کنیم. پس کدهای زیر را می‌نویسیم.

G1=CyclicGroup[10]
Gr2=CayleyGraph[G1]
G2=DihedralGroup[5]
Gr3=CayleyGraph[G2]

گراف‌های بدست‌آمده در زیر آورده‌شده‌اند. اگر نشانه‌گرِ موش‌واره‌تان را بر روی یال‌های گراف کیلیِ رسم‌شده در Mathematica ببرید نمایش جایگشتیِ عضو مولد مربوط به یال را نشان‌تان می‌دهد. برای نمونه برای یال‌های قرمزرنگ گراف آخر نشان می‌دهد Cycles[{{2,5},{3,4}}] که یعنی جایگشتی که تجزیه‌اش به دورهای مجزا می‌شود $(2\;5)(3\;4)$ که در واقع همان تقارنی است که گوشهٔ شمارهٔ یک از ۵-ضلعیِ منتظم را ثابت نگه می‌دارد و گوشه‌های ۲ و ۳ را به ترتیب به گوشه‌های ۵ و ۴ می‌برد (گوشه‌های ۵-ضلعی منتظم در یک جهت ساعتگرد یا پادساعتگرد شماره‌گذاری‌شده‌اند). برای یال‌های آبی‌رنگ گراف آخر نشان می‌دهد Cycles[{{1,2,3,4,5}}] که دورِ $(1\;2\;3\;4\;5)$ است که در واقع دورانی است که هر گوشهٔ پنج‌ضلعی منتظم‌مان را به گوشهٔ پَسینَش می‌برد. برای گراف کیلی گروه دوری‌مان نیز همهٔ یال‌ها یک‌رنگ و مربوط به تنها عضو مولد کمینه‌مان است که نمایشَش را اینگونه نشان می‌دهد Cycles[{1,2,3,4,5,6,7,8,9,0}]. شاید ابتدا جا بخورید که چرا جایگشت و دور در اینجا نمایش می‌دهد؟! ولی باید گوش‌زد کرد که قضیهٔ کِیلی در جبر را هرگز فراموش نکنید که می‌گفت هر گروهی را می‌توان در یک گروهِ جایگشتیِ $S_n$ای نشاند یعنی یک عدد طبیعیِ $n$ای یافت می‌شود و یک زیرگروه از $S_n$ که گروهمان یکریخت با این زیرگروه است. در اینجا نیز گروهِ $S_{10}$ یکریخت با زیرگروه تولید شده توسط دورِ $(1\;2\;\cdots\;10)$ در $S_{10}$ است که دورِ یادشده در تناظر با عضو تولیدکنندهٔ $C_{10}$ است یا اگر با نمایشِ $\overline{\mathbb{Z}}_{10}$ و عمل جمع‌اش کار می‌کنید، در تناظر با عضوِ $\bar{1}$ است.

به هر حال همانطور که می‌بینید گراف نخست پس از حذف رنگ و جهت یک دور است و بدیهی است که گراف پترسن ما یک دور نیست. گراف دوم نیز پس از حذف زنگ و جهت دارای یال‌های موازی است که گراف پترسن ما ندارد. به غیر از آن حتی پس از یکی‌کردنِ یال‌های موازی، در این گراف ما دور به درازای ۴ داریم ولی در گراف پترسن‌مان هیچ دوری با درازای ۴ وجود ندارد!

این ثابت می‌کند که هیچ گروهی وجود ندارد که گراف پترسن گراف کیلی آن باشد. (توجه کنید که اگر مجموعهٔ مولد بیشتر از دو عضوی برای گروه $D_{10}$ برداریم، گراف کیلی جدید گراف آخر بالا را به عنوان زیرگراف خواهد داشت در نتیجه پس از حذف رنگ و جهت و یکی کردن یال‌های موازی باز هم دور به درازای ۴ خواهد داشت. برای گروه دوری خودتان فکر کنید که چرا اگر مولد بیشتر از یک عضوی برایش برداریم گراف کیلی پس از حذف رنگ و جهت و یال موازی باز هم نمی‌تواند گراف پترسن شود).