کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4653201 1632758 2017 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The union-closed sets conjecture almost holds for almost all random bipartite graphs
ترجمه فارسی عنوان
حدس مجموعه اتحاد بسته تقریبا نگه داشته شده برای گراف های دوبخشی تقریبا همه تصادفی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Frankl’s union-closed sets conjecture states that in every finite union-closed family of sets, not all empty, there is an element in the ground set contained in at least half of the sets. The conjecture has an equivalent formulation in terms of graphs: In every bipartite graph with least one edge, both colour classes contain a vertex belonging to at most half of the maximal stable sets.We prove that, for every fixed edge-probability, almost every random bipartite graph almost satisfies Frankl’s conjecture.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 59, January 2017, Pages 129–149
نویسندگان
, ,