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

It is easily seen that max { μ 1, v 1, …, μ n , v n } ⩾ 1/log(| F | + | G |) is tight up to a factor of 2.

Abstract

Let f ( X l ,…, X N )=⋁ I ∈ F ⋀ i ∈ I X i and g ( X l ,…, X N )=⋁ I ∈ G ⋀ i ∈ I X i 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 x i , i = 1, …, n , let μ i = # { I ∈ F | i ∈ I }/| F | and v i = # { I ∈ G | i ∈ I }/| G | be the frequencies with which x i occurs in f and g . It is easily seen that max { μ 1 , v 1 , …, μ n , v n } ⩾ 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.