کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4601274 1336882 2012 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Extremal families containing no two sets and their union
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله
Extremal families containing no two sets and their union
چکیده انگلیسی

The family F⊆2[n] of subsets of [n]={1,2,…,n} is 2-union free if it does not contain three different sets A, B, C such that A=B∪C, and F⊆2[n] is union free if it does not contain k+1⩾3 different sets A0, A1, …, Ak such that . Let cn, bn be the maximum size of a 2-union free, union free family, respectively. Simple construction shows that , which slightly improves the lower bound obtained by Kleitman if n is odd. Another more complicated construction further improves this lower bound. Union free family of m subsets of [n] naturally corresponds to an m×n (0,1) matrix with independent rows. The result is related to maximum number m of independent rows in some (0,1) matrix with n columns.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 436, Issue 4, 15 February 2012, Pages 845-849