Let {A_1,A_2,...,A_n}" src="https://mathworld.wolfram.com/images/equations/Union-ClosedSetsConjecture/Inline1.gif" style="height:15px; width:119px" /> be a union-closed set, then the union-closed set conjecture states that an element exists which belongs to at least  of the sets in . Sarvate and Renaud (1989) showed that the conjecture is true if , where  is the smallest set in , or if . They also showed that if the conjecture fails, then , where  is the largest set of .

These results have since been improved for  up to 18 (Sarvate and Renaud 1990), 24 (Lo Faro 1994a), 27 (Poonen 1992), 32 in (Gao and Yu 1998), and the best known result of 40 (Roberts 1992).

The proof for the case where  has a 2-set can be effected as follows. Write {x,y}" src="https://mathworld.wolfram.com/images/equations/Union-ClosedSetsConjecture/Inline13.gif" style="height:15px; width:64px" />, then partition the sets of  into four disjoint families , , , and , according to whether their intersection with  is , {x}" src="https://mathworld.wolfram.com/images/equations/Union-ClosedSetsConjecture/Inline21.gif" style="height:15px; width:17px" />, {y}" src="https://mathworld.wolfram.com/images/equations/Union-ClosedSetsConjecture/Inline22.gif" style="height:15px; width:17px" />, or {x,y}" src="https://mathworld.wolfram.com/images/equations/Union-ClosedSetsConjecture/Inline23.gif" style="height:15px; width:32px" />, respectively. It follows that  by taking unions with , where  is the cardinal number of . Now compare  with . If , then , so  is in at least half the sets of . Similarly, if , then  is in at least half the sets (Hoey, pers. comm.).

Unfortunately, this method of proof does not extend to , since Sarvate and Renaud show an example of a union-closed set with {x,y,z}" src="https://mathworld.wolfram.com/images/equations/Union-ClosedSetsConjecture/Inline37.gif" style="height:15px; width:78px" /> where none of , ,  is in half the sets. However, in these cases, there are other elements which do appear in half the sets, so this is not a counterexample to the conjecture, but only a limitation to the method of proof given above (Hoey, pers. comm.).

REFERENCES:

Gao, W. and Yu, H. "Note on the Union-Closed Sets Conjecture." Ars Combin. 49, 280-288, 1998.

Lo Faro, G. "A Note on the Union-Closed Sets Conjecture." J. Austral. Math. Soc. Ser. A 57, 230-236, 1994a.

Lo Faro, G. "Union-Closed Sets Conjecture: Improved Bounds." J. Combin. Math. Combin. Comput. 16, 97-102, 1994b.

Poonen, B. "Union-Closed Families." J. Combin. Theory Ser. A 59, 253-268, 1992.

Roberts, I. Tech. Rep. No. 2/92. School Math. Stat., Curtin Univ. Tech., Perth, 1992.

Sarvate, D. G. and Renaud, J.-C. "On the Union-Closed Sets Conjecture." Ars Combin. 27, 149-153, 1989.

Sarvate, D. G. and Renaud, J.-C. "Improved Bounds for the Union-Closed Sets Conjecture." Ars Combin. 29, 181-185, 1990.

West, D. "Union-Closed Sets Conjecture (1979)." http://www.math.uiuc.edu/~west/openp/unionclos.html.

اخر الاخبار

اخبار العتبة العباسية المقدسة

جمعية كشافة الكفيل: المجالس الحسينية تعلّم الفتية قيم نهضة الإمام الحسين (عليه السلام)

عَبرَ المجالس الحسينية.. المجمَع العلمي يقدّم محاضرات دينية وتلاوات قرآنية في بغداد والنجف وميسان

برعاية العتبة العباسية المقدسة.. موكب قناديل السماء يُحيي مراسم اليوم الثالث عشر من المحرّم

بعد انتهاء مراسم ذكرى دفن الأجساد الطاهرة قسم رعاية الصحن يباشر بحملة تنظيف واسعة لصحن مرقد أبي الفضل العباس (عليه السلام)

المزيد

الآخبار الصحية

لكبح الجوع وخسارة الوزن.. "سر بسيط" في نظام جوكوفيتش ؟

هل يساعد الرجيم في علاج الأمراض العقلية؟

لحماية أسنان طفلك.. هذا الفيتامين يقلل خطر التسوس

أكل الطعام بسرعة.. طريق سريع إلى أمراض خطيرة

المزيد

الآخبار التكنلوجية

ما هي أفضل درجة حرارة لتكييف الهواء في السيارة؟

ذوبان الأنهار الجليدية يوقظ "عمالقة نائمة"!

9 يوليو يشهد أقصر يوم في التاريخ المسجل ؟!!

راتبه عشرات ملايين الدولارات.. زوكربرغ يخطف "عقل أبل"

المزيد