Almost-Fisher families

DOI10.1016/J.JCTA.2015.10.003zbMATH Open1326.05161arXiv1408.3496OpenAlexW1490365176MaRDI QIDQ5899503FDOQ5899503

Authors:

Publication date: 17 November 2015

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

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$.

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

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

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)

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)