Subsets of a finite set that almost always intersect each other in \(\lambda\) elements (Q1356776)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Subsets of a finite set that almost always intersect each other in \(\lambda\) elements
scientific article

    Statements

    Subsets of a finite set that almost always intersect each other in \(\lambda\) elements (English)
    0 references
    0 references
    23 February 1998
    0 references
    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\).
    0 references
    hypergraph
    0 references
    Fisher's inequality
    0 references
    cocktail party hypergraph
    0 references
    clique partition
    0 references
    0 references

    Identifiers