Baranyais teoremasi - Baranyais theorem - Wikipedia

A qismi to'liq grafik 8 ta tepada 7 rangga (mukammal mosliklar ), ish r = Baranyai teoremasining 2 tasi

Yilda kombinatorial matematika, Baranyai teoremasi (tomonidan isbotlangan va nomlangan Zsolt Baranyai ) bilan ishlaydi parchalanish to'liq gipergrafalar.

Teorema bayoni

Natijaning bayonoti shundan iboratki, agar ${ displaystyle 2 leq r$ natural sonlar va r ajratadi k, keyin to'liq gipergraf ${ displaystyle K_ {r} ^ {k}}$ parchalanadi 1-omillar. ${ displaystyle K_ {r} ^ {k}}$ bilan gipergrafdir k har bir kichik to'plami bo'lgan tepaliklar r tepaliklar gipergezni hosil qiladi; bu gipergrafning 1-faktori har bir tepaga to'liq bir marta tegadigan yoki unga teng keladigan giperadjirlar to'plamidir. bo'lim tepaliklarning kattalikdagi kichik to'plamlarigar. Shunday qilib, teorema k gipergrafaning tepalari pastki qismlarga bo'linishi mumkin r tepaliklar ${ displaystyle { binom {k} {r}} { frac {r} {k}} = { binom {k-1} {r-1}}}$ har xil yo'llar bilan, shunday qilib har biri r-element pastki qismi aynan bitta bo'limda ko'rinadi.

Ish ${ displaystyle r = 2}$

Maxsus holatda ${ displaystyle r = 2}$, bizda to'liq grafik mavjud ${ displaystyle K_ {n}}$ kuni ${ displaystyle n}$ tepaliklar va biz qirralarning rangini bo'yashni xohlaymiz ${ displaystyle { binom {n} {2}} { frac {2} {n}} = n-1}$ ranglar, shunda har bir rangning chekkalari mukammal moslikni hosil qiladi. Baranyai teoremasida buni har doim qilishimiz mumkinligi aytilgan ${ displaystyle n}$ hatto.

Tarix

The r = 2 ta holatni har birini bildirgan holda o'zgartirish mumkin to'liq grafik tepaliklarning juft soniga ega bo'yash uning ranglari soni unga teng daraja yoki unga teng ravishda uning qirralari bo'linishi mumkin mukammal mosliklar. Bu rejalashtirish uchun ishlatilishi mumkin davra bo'yicha musobaqalar va uning echimi XIX asrda allaqachon ma'lum bo'lgan. Ish shunday k = 2r ham oson.

The r = 3 ta voqea R. Pelteson tomonidan 1936 yilda aniqlangan. Umumiy holat isbotlangan Zsolt Baranyai 1975 yilda.

Adabiyotlar

• Baranyai, Zs. (1975), "To'liq bir xil gipergrafiyani faktorizatsiya qilish to'g'risida", yilda Hajnal, A.; Rado, R.; So, V. T. (tahr.), Cheksiz va cheklangan to'plamlar, Proc. Coll. Keszthely, 1973 yil, Colloquia matematikasi. Soc. Xanos Bolyay, 10, Shimoliy-Gollandiya, 91-107 betlar.
• van Lint, J. H.; Uilson, R. M. (2001), Kombinatorika kursi (2-nashr), Kembrij universiteti matbuoti.
• Pelteson, R. (1936), Das Turnierproblem für Spiele zu je dreien, Birinchi dissertatsiya, Berlin.