Almost-Fisher families

DOI10.1016/J.JCTA.2015.10.003MaRDI QIDQ5899503zbMATH OpenOpenAlexFDO

Authors

Publication date 17 November 2015

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.3496

zbMATH Keywords

extremal combinatoricsHadamard matricesextremal set theorydesign theoryFisher's inequality

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Other designs, configurations (05B30) Extremal set theory (05D05)

Abstract: A classic theorem in combinatorial design theory is Fisher's inequality, which states that a family $mathcalF$ of subsets of $[n]$ with all pairwise intersections of size $lambda$ can have at most $n$ non-empty sets. One may weaken the condition by requiring that for every set in $mathcalF$, all but at most $k$ of its pairwise intersections have size $lambda$. We call such families $k$-almost $lambda$-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 $lambda$. In particular we prove that for small $lambda$ 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$.

Recommendations

• Almost-Fisher families
• A generalization of Fisher's inequality
• On the nonuniform Fisher inequality
• Almost intersecting families
• Generalising Fisher's inequality to coverings and packings

Cites work

• scientific article; zbMATH DE number 3561362 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• scientific article; zbMATH DE number 3104192 (Why is no real title available?)
• A Note on Fisher's Inequality for Balanced Incomplete Block Designs
• Almost Intersecting Families of Sets
• An Inequality for Incidence Matrices
• Exact \(k\)-wise intersection theorems
• Extremal set systems with restricted \(k\)-wise intersections.
• Extremal set systems with weakly restricted intersections
• Forbidden Intersections
• Hypergraphs of Bounded Disjointness
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersection theorems with geometric consequences
• On \(k\)-wise set-intersections and \(k\)-wise Hamming-distances
• On finite set-systems whose every intersection is a kernel of a star
• On some Theorems in Combinatorics Relating to Incomplete Block Designs
• On t-designs
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints

Cited in

(3)

• scientific article; zbMATH DE number 1552345 (Why is no real title available?)
• scientific article; zbMATH DE number 1441755 (Why is no real title available?)
• Almost-Fisher families

This page was built for publication: Almost-Fisher families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5899503)