On the frequency of the most frequently occurring variable in dual monotone DNFs

AbstractLet f(Xl,…,XN)=⋁I∈F⋀i∈IXi and g(Xl,…,XN)=⋁I∈G⋀i∈IXi be a pair of dual monotone irredundant disjunctive normal forms, where F and G are the sets of the prime implicants of tf and g, respectively. For a variable xi, i = 1, …, n, let μi = # {I ∈ F|i ∈ I}/|F| and vi = # {I ∈ G|i ∈ I}/|G| be the frequencies with which xi occurs in f and g. It is easily seen that max {μ1, v1, …, μn, vn} ⩾ 1/log(|F| + |G|). We give examples of arbitrarily large F and G for which the above bound is tight up to a factor of 2