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

في الرياضيات ، تُعدّ رسوم جونسون فئة خاصة من الرسوم البيانية غير الموجهة، تُعرَّف من أنظمة المجموعات. رؤوس رسم جونسون البياني${\displaystyle J(n,k)}$هي${\displaystyle k}$مجموعات فرعية من عناصر${\displaystyle n}$مجموعة من العناصر؛ يكون رأسان متجاورين عندما يحتوي تقاطع هذين الرأسين (المجموعات الجزئية) على${\displaystyle (k-1)}$-العناصر. ^{[ 1 ]} سميت كل من مخططات جونسون ومخطط جونسون ذي الصلة الوثيقة على اسم سيلمر إم جونسون .

• كلاهما${\displaystyle J(n,1)}$و${\displaystyle J(n,n-1)}$هي الرسم البياني الكامل K _n .
• ${\displaystyle J(4,2)}$هو الرسم البياني ثماني الأوجه . ^{[ 2 ]}
• ${\displaystyle J(5,2)}$هو مكمل مخطط بيترسن ، ^{[ 1 ]} ومن ثم فهو مخطط الخط لـ K _5. وبشكل أعم، لجميع${\displaystyle n}$، الرسم البياني لجونسون${\displaystyle J(n,2)}$يمثل الرسم البياني الخطي لـ K _n ومكمل الرسم البياني لـ Kneser${\displaystyle K(n,2).}$

• ${\displaystyle J(n,k)}$متماثل مع​${\displaystyle J(n,nk).}$
• للجميع${\displaystyle 0\leq j\leq \operatorname {diam} (J(n,k))}$أي زوج من الرؤوس على مسافة${\displaystyle j}$يشارك${\displaystyle kj}$العناصر المشتركة.
• ${\displaystyle J(n,k)}$هي متصلة هاميلتونياً ، مما يعني أن كل زوج من الرؤوس يشكل نهايتي مسار هاميلتوني في الرسم البياني. وهذا يعني تحديداً أنها تحتوي على دورة هاميلتونية . ^{[ 3 ]}
• ومن المعروف أيضاً أن الرسم البياني لجونسون${\displaystyle J(n,k)}$يكون${\displaystyle k(nk)}$-vertex-connected. ^{[ 4 ]}
• ${\displaystyle J(n,k)}$يشكل الرسم البياني للرؤوس والحواف لمتعدد السطوح ذي ( ن  -  1) أبعاد ، والذي يسمى هايبرسيمبلكس . ^{[ 5 ]}
• أي زمرة قصوى تكون إما من الشكل${\displaystyle \{S\cup \{x\}\mid x\in \{1,\dots ,n\}\setminus S\}}$لـ${\displaystyle (k-1)}$مجموعة فرعية من العناصر${\displaystyle S}$و${\displaystyle k<n-1}$أو على شكل${\displaystyle \{S\setminus \{x\}\mid x\in S\}}$لـ${\displaystyle (k+1)}$مجموعة العناصر${\displaystyle S}$ل${\displaystyle k>1}$أو على شكل${\displaystyle \{\{1\},\{2\}\}}$في الحالات الاستثنائية${\displaystyle (n,k)=(2,1)}$[ ^{6 ]​}
• رقم الزمرة لـ${\displaystyle J(n,k)}$يتم التعبير عنها بصيغة بدلالة أصغر وأكبر قيمها الذاتية :${\displaystyle \omega (J(n,k))=1-\lambda _{\max }/\lambda _{\min }}$أو، وفقًا للوصف الصريح أعلاه للمجموعات القصوى،${\displaystyle \omega (J(n,k))=\max\{k+1,N-k+1\}.}$
• رقم غلاف المجموعة${\displaystyle J(n,k)}$يرضي${\displaystyle \theta (J(n,1))=1}$ل${\displaystyle n>1}$،${\displaystyle \theta (J(n,2))=n-2}$ل${\displaystyle n>2}$و${\displaystyle \theta (J(n,3))=\lfloor (n-1)^{2}/4\rfloor }$ل${\displaystyle n>5}$لكنها غير معروفة بشكل عام. ^{[ 7 ]}
• العدد اللوني لـ${\displaystyle J(n,k)}$هو على الأكثر${\displaystyle n,\chi (J(n,k))\leq n.}$^{[ 8 ]}
• كل رسم بياني لجونسون هو رسم بياني شبكي محليًا ، مما يعني أن الرسم البياني الفرعي المستحث لجيران أي رأس هو رسم بياني للرخ . وبشكل أدق، في الرسم البياني لجونسون${\displaystyle J(n,k)}$كل حي هو${\displaystyle k\times (n-k)}$رسم بياني للرخ. ^{[ 9 ]}

توجد مجموعة فرعية متعدية للمسافة من${\displaystyle \operatorname {Aut} (J(n,k))}$متماثل مع${\displaystyle \operatorname {Sym} (n)}$. في الحقيقة،${\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)}$إلا أنه عندما${\displaystyle n=2k\geq 4}$،${\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)\times C_{2}}$[ ^{10 ]​}

نتيجة لكونها متعدية على المسافة،${\displaystyle J(n,k)}$وهي أيضًا منتظمة المسافة . التأجير${\displaystyle d}$لنرمز إلى قطرها ، مصفوفة التقاطع لـ${\displaystyle J(n,k)}$يُعطى بواسطة

${\displaystyle \left\{b_{0},\ldots ,b_{d-1},c_{1},\ldots c_{d}\right\}}$

أين:

${\displaystyle {\begin{aligned}b_{j}&=(k-j)(n-k-j)&&0\leq j<d\\c_{j}&=j^{2}&&0<j\leq d\end{aligned}}}$

اتضح أنه ما لم${\displaystyle J(n,k)}$يكون${\displaystyle J(8,2)}$، ولا تشترك مصفوفة التقاطع الخاصة بها مع أي رسم بياني آخر منتظم المسافة؛ مصفوفة التقاطع لـ${\displaystyle J(8,2)}$يشترك مع ثلاثة رسوم بيانية أخرى منتظمة المسافة ليست رسوم بيانية لجونسون. ^{[ 1 ]}

• متعددة الحدود المميزة لـ${\displaystyle J(n,k)}$يُعطى بواسطة

${\displaystyle \phi (x):=\prod _{j=0}^{\operatorname {diam} (J(n,k))}\left(x-A_{n,k}(j)\right)^{{\binom {n}{j}}-{\binom {n}{j-1}}}.}$

أين${\displaystyle A_{n,k}(j)=(k-j)(n-k-j)-j.}$^{[ 10 ]}

• المتجهات الذاتية لـ${\displaystyle J(n,k)}$^{[ 11 ]}​

رسم بياني لجونسون${\displaystyle J(n,k)}$يرتبط هذا ارتباطًا وثيقًا بمخطط جونسون ، وهو مخطط ارتباط يُربط فيه كل زوج من المجموعات المكونة من k عنصرًا برقم يساوي نصف الفرق المتناظر بين المجموعتين. ^{[ 12 ]} يحتوي مخطط جونسون على حافة لكل زوج من المجموعات على مسافة واحد في مخطط الارتباط، وتكون المسافات في مخطط الارتباط هي بالضبط أقصر مسافات المسار في مخطط جونسون. ^{[ 13 ]}

يرتبط مخطط جونسون أيضًا بعائلة أخرى من الرسوم البيانية المتعدية للمسافة، وهي الرسوم البيانية الفردية ، التي تكون رؤوسها${\displaystyle k}$مجموعات فرعية من عناصر${\displaystyle (2k+1)}$مجموعة من العناصر التي تتوافق حوافها مع أزواج منفصلة من المجموعات الجزئية. ^{[ 12 ]}

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

بشكل عام، يعد تحديد العدد اللوني لمخطط جونسون مشكلة مفتوحة . ^{[ 15 ] [ 16 ]}

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

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