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

From MaRDI portal
scientific article
Language Label Description Also known as
English
A family of inequalities for intersecting antichains of subsets of an \(n\)-set
scientific article

    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
    0 references
    0 references
    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
    0 references