Subsets of a finite set that almost always intersect each other in \(\lambda\) elements
type: Item
instance of: scholarly article
title: Subsets of a finite set that almost always intersect each other in \(\lambda\) elements
zbMATH Open document ID: 0883.05108
DOI: 10.1016/S0012-365X(96)00200-2
author: Renaud Palisse
published in: Discrete Mathematics
publication date: 1998-02-23T00:00:00Z
review text: The author gives some extensions of Fisher's inequality and applications to clique decompositions of certain graphs. Let \(H\) be a hypergraph with edges \(E_1, E_2, \dots, E_m\). The vertices of \(H\) are elements of \(V= \bigcup_{1 \leq i \leq m} E_i\). Assume that \(E_i \neq E_j\) whenever \(i \neq j\). \(H\) is said to be a cocktail party hypergraph if there is a positive integer \(\lambda\) such that \(|E_i \cap E_j |\neq \lambda\) for \(1 \leq i \leq m\) and all but at most one \(j \neq i\). If \(|E_i \cap E_j |\neq \lambda\) for \(j\neq i\), then the pair \({E_i, E_j}\) is said to be a discordant pair of edges. Put \(n= |V |\), \(e_i= |E_i |\), \(e_{ij}= |E_i \cap E_j |\) and \(\Delta_{ij}= (e_i- \lambda)(e_j- \lambda)- (e_{ij}- \lambda)^2\). The following extensions of Fisher's inequality are given: If \(\Delta_{ij} \neq 0\) for every discordant pair, then \(m \leq n+1\). If \(\Delta_{ij} \neq 0\) for all but exactly one discordant pair, then \(m \leq n\). If \(\Delta_{ij} > 0\) for every discordant pair, then \(m \leq n\).
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1019122
zbMATH Keywords: hypergraph
zbMATH Keywords: Fisher's inequality
zbMATH Keywords: cocktail party hypergraph
zbMATH Keywords: clique partition
reviewed by: Toru Ishihara
MaRDI profile type: Publication
cites work: Multicolored forests in bipartite decompositions of graphs
cites work: A short proof of the nonuniform Ray-Chaudhuri-Wilson inequality
cites work: Combinatorial designs and related systems
cites work: Q3758879
cites work: Q4723764
cites work: Q5842949
cites work: A sharpening of Fisher's inequality
cites work: Q5663904
cites work: Clique partitions of the cocktail party graph
cites work: On the decomposition of Kn into complete m‐partite graphs
cites work: On some Theorems in Combinatorics Relating to Incomplete Block Designs
cites work: Q4846548
cites work: Lehman's forbidden minor characterization of ideal 0-1 matrices
cites work: A short proof of Fisher's inequality
cites work: A new proof of a theorem of Graham and Pollak
cites work: Applying a proof of tverberg to complete bipartite decompositions of digraphs and multigraphs
cites work: An extension of a theorem of the Bruijn and Erdős on combinatorial designs
cites work: Subsets of a finite set that intersect each other in at most one element
cites work: A theorem on block designs
cites work: On the decomposition ofkn into complete bipartite graphs
description: scientific article; zbMATH DE number 1019122