کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6424183 1632784 2014 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The maximum sum and the maximum product of sizes of cross-intersecting families
ترجمه فارسی عنوان
حداکثر مقدار و حداکثر محصول اندازه خانواده های متقاطع
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We say that a set A   t-intersects a set B if A and B have at least t common elements. A family A of sets is said to be t-intersecting if each set in A   t-intersects all the other sets in A. Families A1,A2,…,Ak are said to be cross-t-intersecting if for any i and j in {1,2,…,k} with i≠j, every set in Ai   t-intersects every set in Aj. We prove that for any finite family F that has at least one set of size at least t, there exists an integer κ≤|F| such that for any k≥κ, both the sum and the product of sizes of k cross-t-intersecting subfamilies A1,…,Ak (not necessarily distinct or non-empty) of F are maxima if A1=⋯=Ak=L for some largest t-intersecting subfamily L of F. We then study the smallest possible value of κ and investigate the case k<κ; this includes a cross-intersection result for straight lines that demonstrates that it is possible to have F and κ such that for any k<κ, the configuration A1=⋯=Ak=L is neither optimal for the sum nor optimal for the product. We also outline solutions for various important families F, and we provide solutions for the case when F is a power set.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 35, January 2014, Pages 117-130
نویسندگان
,