معضلة سبيرنر

في بُعد واحد، يمكن اعتبار مبرهنة سبيرنر بمثابة نسخة منفصلة من مبرهنة القيمة المتوسطة . في هذه الحالة، تنص المبرهنة أساسًا على أنه إذا كانت دالة منفصلة تأخذ القيمتين 0 و1 فقط، وتبدأ من القيمة 0 وتنتهي عند القيمة 1، فإنها يجب أن تغير قيمها عددًا فرديًا من المرات.

الحالة ثنائية الأبعاد هي الأكثر شيوعاً، وهي موضحة على النحو التالي:

قسّم المثلث ABC بشكل عشوائي إلى مثلثات أصغر متصلة ببعضها. ثم يُعرَّف تلوين سبيرنر لهذه المثلثات بأنه تخصيص ثلاثة ألوان لرؤوس المثلثات بحيث

1. لكل رأس من رؤوس المثلث الأولي الثلاثة A و B و C لون مميز
2. رؤوس المثلث ABC الواقعة على أي ضلع لها لونان فقط، وهما اللونان الموجودان عند طرفي الضلع. على سبيل المثال، يجب أن يكون لكل رأس على AC نفس لون A أو C.

إذن، يحتوي كل تلوين سبيرنر لكل مثلث على "مثلث قوس قزح" واحد على الأقل، وهو مثلث أصغر في المثلث نفسه، رؤوسه ملونة بالألوان الثلاثة المختلفة. وبشكل أدق، يجب أن يكون عدد مثلثات قوس قزح فرديًا.

في الحالة العامة، تشير اللمة إلى مُجَسَّم بسيط ذي n بُعد :

${\displaystyle {\mathcal {A}}=A_{1}A_{2}\ldots A_{n+1}.}$

لنفترض أي عملية تثليث T ، وهي تقسيم منفصل لـ${\displaystyle {\mathcal {A}}}$إلى أشكال بسيطة أصغر ذات أبعاد n ، تلتقي وجهاً لوجه مرة أخرى. لنرمز إلى دالة التلوين كما يلي:

${\displaystyle f:S\to \{1,2,3,\dots ,n,n+1\},}$

حيث S هي مجموعة رؤوس T. تُعرّف دالة التلوين تلوين سبيرنر عندما:

1. يتم تلوين رؤوس المجسم البسيط الكبير بألوان مختلفة، أي بدون فقدان للعمومية ، f ( A _i ) = i لـ 1 ≤ i ≤ n + 1 .
2. رؤوس T الموجودة على أي سطح فرعي k- الأبعاد من المجسم البسيط الكبير

${\displaystyle A_{i_{1}}A_{i_{2}}\ldots A_{i_{k+1}}}$

يتم تلوينها فقط بالألوان

${\displaystyle i_{1},i_{2},\ldots ,i_{k+1}.}$

إذن، يحتوي كل تلوين سبيرنر لكل تثليث للمجسم البسيط ذي الأبعاد n على عدد فردي من حالات المجسم البسيط قوس قزح ، أي المجسم البسيط الذي تُلوَّن رؤوسه بجميع الألوان n + 1. وبالتحديد، يجب أن يكون هناك مجسم بسيط قوس قزح واحد على الأقل.

سنتناول أولاً الحالة ثنائية الأبعاد. لنفترض وجود رسم بياني G مبني من التثليث T كما يلي:

رؤوس الشكل G هي عناصر المثلث T بالإضافة إلى المساحة خارج المثلث. يتصل رأسان بضلع إذا كانت مساحتاهما المتناظرتان تشتركان في حدود مشتركة، أحد طرفيها ملون باللون 1 والآخر باللون 2.

لاحظ أنه في الفترة AB يوجد عدد فردي من الحدود الملونة باللونين 1 و2 (ببساطة لأن A ملون باللون 1، وB ملون باللون 2؛ وأثناء تحركنا على طول AB ، يجب أن يكون هناك عدد فردي من تغييرات الألوان للحصول على ألوان مختلفة في البداية والنهاية). في الفترتين BC وCA، لا توجد حدود ملونة باللونين 1 و2 على الإطلاق. لذلك، فإن رأس G المقابل للمنطقة الخارجية له درجة فردية. وبحسب نظرية المصافحة ، فإن G يحتوي على عدد زوجي من الرؤوس ذات الدرجة الفردية. وبالتالي، فإن الرسم البياني المتبقي، باستثناء المنطقة الخارجية، يحتوي على عدد فردي من الرؤوس ذات الدرجة الفردية المقابلة لعناصر T.

يمكن ملاحظة بسهولة أن الدرجة الوحيدة الممكنة للمثلث من T هي 0 أو 1 أو 2، وأن الدرجة 1 تتوافق مع مثلث ملون بالألوان الثلاثة 1 و2 و3.

وهكذا توصلنا إلى استنتاج أقوى قليلاً، والذي يقول إنه في عملية التثليث T يوجد عدد فردي (وواحد على الأقل) من المثلثات الملونة بالكامل.

يمكن إثبات الحالة متعددة الأبعاد بالاستقراء على بُعد المُجَسَّم البسيط. نُطبِّق نفس المنطق، كما في الحالة ثنائية الأبعاد، لنستنتج أنه في عملية تثليث ذات بُعد n، يوجد عدد فردي من المُجَسَّمات البسيطة كاملة الألوان.

فيما يلي شرح مفصل للبرهان المقدم سابقًا، للقارئ الجديد في نظرية الرسم البياني .

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

كما ذُكر سابقًا، تُربط العقد التي تشترك في حافة طرفاها مرقمان 1 و2 في الرسم البياني المُشتق. على سبيل المثال، تشترك العقدة d في حافة مع المنطقة الخارجية i ، ورؤوسها جميعها تحمل أرقامًا مختلفة، لذا فهي مُظللة أيضًا. أما العقدة b فلا تُظلل لأن رأسين منها يحملان الرقم نفسه، ولكنها مُرتبطة بالمنطقة الخارجية.

يمكن إضافة مثلث جديد مرقم بالكامل، على سبيل المثال عن طريق إدخال عقدة مرقمة برقم 3 في الحافة بين 1 و1 من العقدة a ، وربط تلك العقدة بالرأس الآخر من a . سيؤدي القيام بذلك إلى إنشاء زوج من العقد الجديدة، كما هو الحال مع العقدتين f و g .

قدّم أندرو ماكلينان ورابي توركي برهانًا مختلفًا، باستخدام حجم المجسم البسيط . ويتم هذا البرهان في خطوة واحدة، دون استخدام الاستقراء الرياضي. ^{[ 2 ] [ 3 ]}

لنفترض أن كل رأس من رؤوس التثليث يمكن تسميته بألوان متعددة، بحيث تكون دالة التلوين هي F  : S → 2 ^{[ n +1]} .

لكل مُجسّم فرعي، تُشكّل مجموعة التسميات على رؤوسه عائلةً من المجموعات على مجموعة الألوان [ n + 1] . ويمكن اعتبار هذه العائلة من المجموعات بمثابة رسم بياني فائق .

إذا كانت ألوان كل رأس v على وجه من أوجه المجسم البسيط، في f ( v )، مجموعة جزئية من مجموعة الألوان على نهايات ذلك الوجه، فإنه يوجد مجسم بسيط فرعي ذو تسمية متوازنة - وهي تسمية تسمح فيها الرسمة الفائقة المقابلة بمطابقة كسرية مثالية . وللتوضيح، إليك بعض الأمثلة على التسمية المتوازنة عندما n = 2 :

• ({1}, {2}, {3}) - متوازنة بالأوزان (1, 1, 1) .
• ({1,2}, {2,3}, {3,1}) - متوازنة بالأوزان (1/2, 1/2, 1/2) .
• ({1,2}, {2,3}, {1}) - متوازنة بالأوزان (0, 1, 1) .

وقد أثبت شابلي ذلك في عام 1973. ^{[ 5 ]} وهو نظير توافقي لـ KKMS lemma .

لنفترض أن لدينا متعدد سطوح P ذو بُعد d وله n رأسًا. P مُثلّث، وكل رأس من رؤوس التثليث مُصنَّف برقم من المجموعة {1، ...، n }. كل رأس رئيسي i مُصنَّف بالرقم i . يُسمى المُجسم الفرعي مُصنَّفًا بالكامل إذا كان ذا بُعد d ، وكان لكل رأس من رؤوسه الـ d + 1 رقم مختلف. إذا كان كل رأس في وجه F من P مُصنَّفًا بأحد الأرقام الموجودة على طرفي F ، فسيكون هناك على الأقل n – d مُجسمات مُصنَّفة بالكامل. بعض الحالات الخاصة هي:

• d = n – 1. في هذه الحالة، P عبارة عن مُجَسَّم بسيط. تضمن مبرهنة سبيرنر متعددة الأوجه وجود مُجَسَّم بسيط واحد على الأقل مُعَلَّم بالكامل. أي أنها تُختزل إلى مبرهنة سبيرنر.
• لنفترض أن لدينا مضلعًا ثنائي الأبعادله n رأسًا، تم تقسيمه إلى مثلثات وتسميته بالأرقام من 1 إلى n ، بحيثالرقمان i و i + 1 فقط على كل وجه بين الرأس i والرأس i + 1 (mod n ) . عندئذٍ، يوجد على الأقل n - 2 مثلثًا فرعيًا تُستخدم فيها ثلاثة أرقام مختلفة.

تم افتراض العبارة العامة من قبل أتاناسوف في عام 1996، والذي أثبتها في حالة d = 2. [ ^{6 ] تم} تقديم برهان الحالة العامة لأول مرة من قبل دي لويرا وبيترسون وسو في عام 2002. ^{[ 7 ]} يقدمون برهانين: الأول غير بنائي ويستخدم مفهوم مجموعات الحصى ؛ والثاني بنائي ويستند إلى حجج تتبع المسارات في الرسوم البيانية .

قام مونييه ^{[ 8 ]} بتوسيع النظرية من متعددات الوجوه إلى الأجسام متعددة الوجوه، والتي لا يشترط أن تكون محدبة أو بسيطة الاتصال. على وجه الخصوص، إذا كان P متعدد وجوه، فإن مجموعة وجوهه تشكل جسمًا متعدد الوجوه. في كل تسمية سبيرنر لجسم متعدد الوجوه ذي رؤوس _v1 ، ...، vn _، يوجد على الأقل:

${\displaystyle nd-1+\left\lceil {\frac {\min _{i=1}^{n}\deg _{B(P)}(v_{i})}{d}}\right\rceil }$

المجسمات البسيطة ذات التسميات الكاملة بحيث يحصل أي زوج منها على تسميتين مختلفتين. درجة المجسم البسيط _{B ( P )} ( vi ₎ هي عدد حواف المجسم البسيط B ( P ) التي ينتمي إليها _vi . بما أن الدرجة لا تقل عن d ، فإن الحد الأدنى لا يقل عن n – d . ولكن يمكن أن يكون أكبر. على سبيل المثال، بالنسبة للمجسم الدائري في 4 أبعاد ذي n رأس، يكون الحد الأدنى هو:

${\displaystyle n-4-1+\left\lceil {\frac {n-1}{4}}\right\rceil \approx {\frac {5}{4}}n.}$

قام موسين ^{[ 9 ]} بتوسيع النظرية لتشمل المشعبات الخطية القطعية ذات الأبعاد d ، مع أو بدون حدود.

قام كل من Asada و Frick و Pisharody و Polevy و Stoner و Tsang و Wellner ^{[ 10 ]} بتوسيع النظرية لتشمل pseudomanifolds ذات الحدود، وقاموا بتحسين الحد الأدنى لعدد الأوجه ذات العلامات المتباينة الزوجية.

لنفترض أنه بدلاً من وجود مكعب بسيط مقسم إلى مكعبات فرعية بسيطة، لدينا مكعب ذو أبعاد n مقسم إلى مكعبات أصغر ذات أبعاد n .

أثبت هارولد دبليو كون ^{[ 11 ]} اللمة التالية. لنفترض أن المكعب [0, M ] ^ⁿ ، حيث M عدد صحيح ، مُقسّم إلى Mⁿ مكعب وحدة. ولنفترض أن كل رأس من رؤوس التقسيم مُرقّم برقم من المجموعة {1، ...، n + 1}، بحيث ^يكون لكل رأس v : (1) إذا كان vᵢ = 0، _فإن الرقم المُرقّم على v هو على الأكثر i ؛ (2) إذا كان _vᵢ = M ، فإن الرقم المُرقّم على v ليس i . عندئذٍ، يوجد مكعب وحدة يحمل جميع الأرقام {1، ...، n + 1} (بعضها مُكرر أكثر من مرة). الحالة الخاصة n = 2 هي: لنفترض أن مربعًا مُقسّم إلى مربعات فرعية، وأن كل رأس مُرقّم برقم من المجموعة {1، 2، 3}. الحافة اليسرى مُرقّمة بـ 1 (أي على الأكثر 1)؛ والحافة السفلية مُرقّمة بـ 1 أو 2 (أي على الأكثر 2). الحافة العلوية مُرقّمة بالرقم 1 أو 3 (أي ليست 2)؛ والحافة اليمنى مُرقّمة بالرقم 2 أو 3 (أي ليست 1). ثم يوجد مربع مُرقّم بالأرقام 1 و2 و3.

هناك صيغة أخرى، مرتبطة بنظرية بوانكاريه-ميراندا ، ^{[ 12 ]} وهي كالتالي: لنفترض أن المكعب [0, M ] ^ⁿ مُقسّم إلى Mⁿ ^مكعبًا أحاديًا. ولنفترض أن كل رأس مُعَلَّم بمتجه ثنائي طوله n ، بحيث يكون لكل رأس v : (1) إذا كان vᵢ = 0، فإن الإحداثي i للتسمية على v هو 0؛ (2) إذا كان vᵢ _{= M} ، فإن الإحداثي i للتسمية على v هو 1؛ (3) إذا كان رأسان متجاورين، فإن تسمياتهما تختلف بإحداثي واحد على الأكثر. عندئذٍ ، يوجد مكعب أحادي تكون فيه جميع التسميات ^{الـ 2ⁿ} مختلفة . في بعدين، هناك طريقة أخرى لصياغة هذه النظرية وهي: ^{[ 13 ]} في أي تسمية تحقق الشروط (1) و(2)، توجد خلية واحدة على الأقل يكون فيها مجموع التسميات 0 [خلية أحادية البعد مع التسميات (1،1) و (-1،-1) ، أو خلايا ثنائية الأبعاد مع جميع التسميات الأربعة المختلفة].

قام وولسي ^{[ 14 ]} بتعزيز هاتين النتيجتين من خلال إثبات أن عدد المكعبات المصنفة بالكامل هو عدد فردي.

قام موسين ^{[ 13 ]} بتوسيع هذه النتائج لتشمل التربيعات العامة .

لنفترض أنه بدلاً من تسمية واحدة، لدينا n من تسميات سبيرنر المختلفة. نعتبر أزواجًا (مُجَسَّم بسيط، تبديل) بحيث تُختار تسمية كل رأس من رؤوس المُجَسَّم البسيط من تسمية مختلفة (أي لكل مُجَسَّم بسيط، يوجد n ! زوجًا مختلفًا). عندئذٍ، يوجد على الأقل n ! زوجًا مُصنَّفًا بالكامل. وقد أثبت رافيندرا بات ^{[ 15 ] هذا لأي تثليث. وقدّم سو [ 16 ]} لاحقًا برهانًا أبسط، لا يصلح إلا لتثليثات مُحدَّدة.

يمكن صياغة هذه اللمة بطريقة أخرى كما يلي: لنفترض وجود n شخصًا، كل منهم يُنتج تصنيفًا مختلفًا لسبيرنر لنفس التثليث. عندئذٍ، يوجد مُجَسَّم بسيط، وتطابق بين الأشخاص ورؤوسه، بحيث يُصنِّف كل رأس من قِبَل صاحبه بشكل مختلف (شخص يُصنِّف رأسه بالرقم 1، وآخر بالرقم 2، وهكذا). علاوة على ذلك، يوجد على الأقل n ! من هذه التطابقات. يمكن استخدام هذا لإيجاد طريقة لتقطيع الكعكة خالية من الحسد مع قطع متصلة.

قام كل من Asada و Frick و Pisharody و Polevy و Stoner و Tsang و Wellner ^{[ 10 ]} بتوسيع هذه النظرية لتشمل pseudomanifolds ذات الحدود.

بشكل أعم، لنفترض أن لدينا m من تصنيفات سبيرنر المختلفة، حيث قد يختلف m عن n . عندئذٍ: ^{[ 17 ] : نظرية 2.1}

1. لأي عددين صحيحين موجبين k _{∈ 1} , …, k _m مجموعهما يساوي m + n – 1 ، يوجد مُعَقَّدٌ صغيرٌ (baby-simplex) عليه، لكل i ∈ {1, …, m }، يستخدم رقم التسمية i ما لا يقل عن k _i (من أصل n ) تسميةً مختلفة. علاوة على ذلك، تُستخدم كل تسمية بواسطة تسمية واحدة على الأقل (من أصل m ) تسمية.
2. لأي أعداد صحيحة موجبة I ₁ ، … ، I _m التي مجموعها m + n – 1 ، يوجد مصفوفة بسيطة صغيرة عليها ، لكل j ∈ {1 ، … ، n } ، ، يتم استخدام التسمية j بواسطة l _j على الأقل (من أصل m ) من التسميات المختلفة.

يختزل كلا الإصدارين إلى مبرهنة سبيرنر عندما يكون m = 1 ، أو عندما تكون جميع التسميات m متطابقة.

انظر ^{[ 18 ]} للحصول على تعميمات مماثلة.

عزز براون وكيرنز ^{[ 19 ]} مبرهنة سبيرنر بدراسة اتجاه المُجَسَّمات. لكل مُجَسَّم فرعي اتجاهٌ يمكن أن يكون إما +1 أو -1 (إذا كان مُعَلَّمًا بالكامل)، أو 0 (إذا لم يكن مُعَلَّمًا بالكامل). وقد أثبتا أن مجموع اتجاهات جميع المُجَسَّمات يساوي +1. وهذا يعني، على وجه الخصوص، أن عدد المُجَسَّمات المُعَلَّمة بالكامل فردي.

كمثال، عندما يكون n = 3 ، لنفترض أن مثلثًا مُقسّم إلى مثلث ومُرقّم بالأرقام {1، 2، 3}. لننظر إلى التسلسل الدوري للأرقام على حدود المثلث. نُعرّف درجة الترقيم بأنها عدد الانتقالات من 1 إلى 2 مطروحًا منه عدد الانتقالات من 2 إلى 1. انظر الأمثلة في الجدول على اليمين. لاحظ أن الدرجة تبقى نفسها سواءً حسبنا الانتقالات من 2 إلى 3 مطروحًا منها الانتقالات من 3 إلى 2، أو من 3 إلى 1 مطروحًا منها الانتقالات من 1 إلى 3.

أثبت موسين أن عدد المثلثات المصنفة بالكامل هو على الأقل درجة التصنيف . ^{[ 20 ]} على وجه الخصوص، إذا كانت الدرجة غير صفرية، فإنه يوجد على الأقل مثلث واحد مصنف بالكامل.

إذا حقق تصنيفٌ ما شرط سبيرنر، فإن درجته تساوي 1 بالضبط: إذ لا توجد تبديلات 1-2 و2-1 إلا في الجانب الواقع بين الرأسين 1 و2، ويجب أن يزيد عدد تبديلات 1-2 بمقدار واحد عن عدد تبديلات 2-1 (عند الانتقال من الرأس 1 إلى الرأس 2). لذلك، فإن مبرهنة سبيرنر الأصلية تُستنتج من مبرهنة موسين.

توجد لِمّة مماثلة حول ^{الأشجار} والدورات المحدودة وغير المحدودة . [ ^{21 ]}