کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651910 1632582 2015 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Almost-Fisher families
ترجمه فارسی عنوان
خانواده های تقریبا فیشر
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A classic theorem in combinatorial design theory is Fisher's inequality, which states that a family F of subsets of [n]={1,2,…,n} with all pairwise intersections of size λ can have at most n non-empty sets. One may weaken the condition by requiring that for every set in F, all but at most k of its pairwise intersections have size λ. We call such families k-almost λ-Fisher. Vu was the first to study the maximum size of such families, proving that for k=1 the largest family has 2n−2 sets, and characterising when equality is attained. We substantially refine his result, showing how the size of the maximum family depends on λ. In particular we prove that for small λ one essentially recovers Fisher's bound. We also solve the next open case of k=2 and obtain the first non-trivial upper bound for general k.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 293-300