کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656741 1632978 2015 22 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Comparable pairs in families of sets
ترجمه فارسی عنوان
جفت های قابل مقایسه در خانواده مجموعه
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Given a family FF of subsets of [n][n], we say two sets A,B∈FA,B∈F are comparable   if A⊂BA⊂B or B⊂AB⊂A. Sperner's celebrated theorem gives the size of the largest family without any comparable pairs. This result was later generalised by Kleitman, who gave the minimum number of comparable pairs appearing in families of a given size.In this paper we study a complementary problem posed by Erdős, Daykin and Frankl in the early '80s. They asked for the maximum number of comparable pairs that can appear in a family of m   subsets of [n][n], a quantity we denote by c(n,m)c(n,m). We first resolve an old conjecture of Alon and Frankl, showing that c(n,m)=o(m2)c(n,m)=o(m2) when m=nω(1)2n/2m=nω(1)2n/2. We also obtain more accurate bounds for c(n,m)c(n,m) for sparse and dense families, characterise the extremal constructions for certain values of m, and sharpen some other known results.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 115, November 2015, Pages 164–185
نویسندگان
, , , ,