A family of inequalities for intersecting antichains of subsets of an \(n\)-set (Q1908275)

From MaRDI portal





scientific article; zbMATH DE number 847632
Language Label Description Also known as
default for all languages
No label defined
    English
    A family of inequalities for intersecting antichains of subsets of an \(n\)-set
    scientific article; zbMATH DE number 847632

      Statements

      A family of inequalities for intersecting antichains of subsets of an \(n\)-set (English)
      0 references
      18 March 1996
      0 references
      Let \(F= \{(A_1, B_1),\dots, (A_m, B_m)\}\) be a family of pairs of subsets of \(N= \{1,\dots, n\}\). This family is called pair-intersecting if for all \(i, j\in \{1,\dots, m\}\), \(A_i\cap A_j\neq \varnothing\) as well as \(A_i\cap B_j= \varnothing\) iff \(i= j\). The authors prove a theorem of the following kind: Let \(f\) be a non-negative real-valued function defined on the power set of \(N\) satisfying several technical conditions and let \(F\) be a pair-intersecting family. Then \[ \sum^m_{i= 1} {f(A_i)\over (\begin{smallmatrix} |A_i|+ |B_i|\\ |A_i|\end{smallmatrix}) (\begin{smallmatrix} n\\ |A_i|+ |B_i|\end{smallmatrix})}\leq 1. \] The proof is based on the cyclic permutation method. The authors also derive several inequalities for intersecting antichains in the Boolean lattice, but it should be mentioned that ``all'' (i.e. facet defining) inequalities are known by a result of \textit{G. O. H. Katona} and \textit{G. Schild} [Linear inequalities describing the class of intersecting Sperner families of subsets. I. Topics in combinatorics and graph theory. Essays in honour of Gerhard Ringel, 413-420 (1990; Zbl 0748.05005)].
      0 references
      0 references
      LYM-inequality
      0 references
      pair-intersecting family
      0 references
      cyclic permutation
      0 references
      intersecting antichains
      0 references
      Boolean lattice
      0 references
      intersecting Sperner families
      0 references
      0 references
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references