Average Degree in the Interval Graph of a Random Boolean Function

keywords: Random Boolean function, interval graph
We consider an n-ary random Boolean function f such that Pr[f( tilde alpha)=1] allowbreak=p for tilde alphain 0,1 n and study its geometric model, the so called interval graph. The interval graph of a Boolean function was introduced by Sapozhenko and has been used in construction of schemes realizing Boolean functions. Using this model, we estimate the number of maximal intervals intersecting a given maximal interval of a random Boolean function and prove that the asymptotic bound on the logarithm of the number is (1+arphi(n))łog_2łog_1/pn cdotłog_2 n, where arphi(n) rightarrow 0 as n rightarrow infty.
reference: Vol. 27, 2008, No. 4, pp. 627–638