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

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

سُميت مخططات بالي نسبةً إلى ريموند بالي . وهي ترتبط ارتباطًا وثيقًا ببناء بالي لإنشاء مصفوفات هادامارد من البواقي التربيعية. ^{[ 1 ]} وقد قُدِّمت هذه المخططات بشكل مستقل من قِبَل ساكس (1962) وإردوش وريني ( 1963) . اهتم ساكس بها لخصائصها التكميلية الذاتية، ^{[ 2 ]} بينما درس إردوش وريني تناظراتها. ^{[ 3 ]}

تُعدّ مخططات بالي الموجهة نظائر موجهة لمخططات بالي، وتُنتج مصفوفات مؤتمرات متناظرة عكسيًا . وقد قدّمها غراهام وسبنسر (1971) (بشكل مستقل عن ساكس وإردوش وريني) كوسيلة لبناء بطولات ذات خاصية كانت معروفة سابقًا بأنها موجودة فقط في البطولات العشوائية: في مخطط بالي الموجه، يهيمن رأس آخر على كل مجموعة فرعية صغيرة من الرؤوس. ^{[ 4 ]}

ليكن q قوة عدد أولي بحيث${\textstyle q\equiv 1{\pmod {4}}}$أي أن q يجب أن يكون إما قوة اختيارية لعدد أولي يوافق 1  بتردد  4 ( عدد أولي فيثاغورسي )، أو قوة زوجية لعدد أولي فردي غير فيثاغورسي. هذا الاختيار لـ q يعني أنه في الحقل المنتهي الوحيد F _q من الرتبة q ، يكون للعنصر  -1 جذر تربيعي.

الآن، لنفترض أن V = F _q ولنفترض

${\displaystyle E=\left\{\{a,b\}\$ :\ ab\in (\mathbf {F} _{q}^{\times })^{2}\right\}} .

إذا كان الزوج { أ ، ب } مُضمّنًا في المجموعة E ، فإنه يكون مُضمّنًا بغض النظر عن ترتيب عنصريه. فبما أن ( أ  - ب) = (-( ب - أ ))، و (-1) مربع، فإن (أ - ب) يكون مربعًا إذا وفقط إذا كان (ب - أ) مربعًا.         

بحسب التعريف، فإن G  =  ( V , E ) هو الرسم البياني لبالي من الرتبة q .  

يبدأ تسلسل رتب مخططات بالي

1، 5، 9، 13، 17، 25، 29، 37، 41، 49، 53، 61، 73، ... (التسلسل A085759 في OEIS )

عندما تكون قيمة q تساوي 13، فإن الحقل F _q هو مجرد حساب الأعداد الصحيحة بتردد 13. الأعداد التي لها جذور تربيعية بتردد 13 هي:

• ±1 (الجذور التربيعية ±1 لـ +1، ±5 لـ -1 )
• ±3 (الجذور التربيعية ±4 لـ +3، ±6 لـ − 3)
• ±4 (الجذور التربيعية ±2 لـ +4، ±3 لـ − 4).

وهكذا، في الرسم البياني لـ Paley، نقوم بتشكيل رأس لكل عدد صحيح في النطاق [0،12]، ونقوم بتوصيل كل عدد صحيح x بستة جيران: x  ±  1  (mod  13)، x  ±  3  (mod  13)، و x  ±  4  (mod  13).

تُعتبر رسوم بالي مُكمِّلة ذاتيًا : أي أن مُكمِّل أي رسم بالي يكون مُتماثلًا معه. أحد أوجه التماثل هو عبر التطبيق الذي يأخذ رأسًا x إلى xk (mod q ) ، حيث k هو أي باقي تربيعي modulo q . ^{[ 2 ]}

تُعتبر رسوم بالي البيانية رسومًا بيانية منتظمة بقوة ، ذات معلمات

${\displaystyle srg\left(q,{\tfrac {1}{2}}(q-1),{\tfrac {1}{4}}(q-5),{\tfrac {1}{4}}(q-1)\right).}$

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

القيم الذاتية لمخططات بالي هي${\displaystyle {\tfrac {1}{2}}(q-1)}$(بتعددية 1) و${\displaystyle {\tfrac {1}{2}}(-1\pm {\sqrt {q}})}$(كلاهما بتعددية)${\displaystyle {\tfrac {1}{2}}(q-1)}$). ويمكن حسابها باستخدام مجموع جاوس التربيعي أو باستخدام نظرية الرسوم البيانية المنتظمة بقوة. ^{[ 6 ]}

إذا كان q عددًا أوليًا، فإن العدد المتساوي المحيط i ( G ) للرسم البياني لبالي يحقق الحدود التالية:

${\displaystyle \displaystyle {\frac {q-{\sqrt {q}}}{4}}\leq i(G)\leq {\frac {q-1}{4}}.}$^{[ 7 ]}

عندما يكون q عددًا أوليًا، فإن الرسم البياني المرتبط به هو رسم بياني دائري هاميلتوني .

تعتبر رسوم بالي شبه عشوائية : عدد مرات ظهور كل رسم بياني ذي رتبة ثابتة كرسم بياني فرعي من رسم بياني بالي (في حالة q الكبيرة ) هو نفسه بالنسبة للرسوم البيانية العشوائية، كما أن مجموعات الرؤوس الكبيرة لها تقريبًا نفس عدد الحواف كما هو الحال في الرسوم البيانية العشوائية. ^{[ 8 ]}

• الرسم البياني لبالي من الرتبة 9 هو رسم بياني خطي محليًا ، ورسم بياني للرخ ، ورسم بياني للمنشور المزدوج 3-3 .
• يحتوي الرسم البياني لـ Paley من الرتبة 13 على سمك كتاب 4 ورقم طابور 3. ^{[ 9 ]}
• الرسم البياني لبالي من الرتبة 17 هو أكبر رسم بياني فريد G بحيث لا يحتوي G ولا مكمله على رسم بياني فرعي كامل مكون من 4 رؤوس. ^{[ 10 ]} ويترتب على ذلك أن عدد رامزي R (4,  4)  =  18.
• يُعد الرسم البياني Paley من الرتبة 101 حاليًا أكبر رسم بياني معروف G بحيث لا يحتوي G ولا مكمله على رسم بياني فرعي كامل مكون من 6 رؤوس.
• يستخدم ساسوكارا وآخرون (1993) رسوم بيانية بالي لتعميم بناء حزمة هوروكس-مامفورد . ^{[ 11 ]}

ليكن q قوة أولية بحيث يكون q = 3 (mod 4). بالتالي، فإن الحقل المنتهي من الرتبة q ، Fq ، لا يحتوي على جذر تربيعي للعدد _-1 . ونتيجة لذلك، لكل زوج ( a , b ) من العناصر المختلفة في Fq ، يكون إما a - b أو b - a مربعًا، وليس كلاهما. الرسم البياني الموجه لبالي هو الرسم البياني الموجه الذي مجموعة رؤوسه V = Fq ومجموعة أقواسه V = _{q .}

${\displaystyle A=\left\{(a,b)\in \mathbf {F} _{q}\times \mathbf {F} _{q}\$ :\ ba\in (\mathbf {F} _{q}^{\times })^{2}\right\}.}

يُعد الرسم البياني الموجه لـ Paley بمثابة بطولة لأن كل زوج من الرؤوس المتميزة مرتبط بقوس في اتجاه واحد فقط.

يؤدي الرسم البياني الموجه لـ Paley إلى بناء بعض مصفوفات المؤتمرات المتناظرة عكسيًا وهندسة المستويين .

ترتبط الجيران الستة لكل رأس في مخطط بالي من الرتبة 13 بدورة؛ أي أن المخطط دوري محليًا . لذلك، يمكن تضمين هذا المخطط كتثليث ويتني لسطح حلقي ، حيث يكون كل وجه مثلثًا وكل مثلث وجهًا. وبشكل أعم، إذا أمكن تضمين أي مخطط بالي من الرتبة q بحيث تكون جميع وجوهه مثلثات، فيمكننا حساب جنس السطح الناتج باستخدام خاصية أويلر .${\displaystyle {\tfrac {1}{24}}(q^{2}-13q+24)}$يفترض بوجان موهار أن الحد الأدنى لجنس السطح الذي يمكن تضمين رسم بياني بالي فيه قريب من هذا الحد في حالة كون q مربعًا، ويتساءل عما إذا كان هذا الحد قد ينطبق بشكل أعم. على وجه التحديد ، يفترض موهار أنه يمكن تضمين رسوم بيانية بالي من الرتبة المربعة في أسطح ذات جنس

${\displaystyle (q^{2}-13q+24)\left({\tfrac {1}{24}}+o(1)\right),}$

حيث يمكن أن يكون الحد o(1) أي دالة لـ q تؤول إلى الصفر في النهاية عندما تؤول q إلى اللانهاية. ^{[ 12 ]}

وجد وايت (2001) تمثيلاتٍ لرسوم بالي البيانية من الرتبة q  ≡  1  (mod  8) تتميز بتناظرٍ عالٍ وتماثلٍ ذاتي، مُعمِّمًا بذلك تمثيلًا طبيعيًا لرسم بالي البياني من الرتبة 9 على شكل شبكة مربعة 3×3 على سطحٍ حلقي. مع ذلك، فإن جنس تمثيلات وايت البيانية أعلى بثلاثة أضعاف تقريبًا من الحدّ الذي افترضه موهار. ^{[ 13 ]}

• بيكر، آر دي؛ إيبرت، جي إل؛ هيمتر، جيه؛ وولدار، إيه جيه (1996). "الزمر القصوى في مخطط بالي من الرتبة المربعة". مجلة الإحصاء والتخطيط والاستدلال . 56 : 33-38 . doi : 10.1016/S0378-3758(96)00006-7 .
• بروير، آي.؛ دومان، د.؛ ريدلي، جيه إن (1988). "أعداد الزمر والأعداد اللونية لبعض رسوم بالي البيانية". كويستيونيس ماتيماتيكاي . 11 : 91-93 . doi : 10.1080/16073606.1988.9631945 .

• بروير، أندرياس إي. "رسوم بيانية بالي" .
• موهار، بويان (2005). "جنس الرسوم البيانية بالي" .