Average Degree in the Interval Graph of a Random Boolean Function

Year, pages: 2008, 627 - 638

We consider an n-ary random Boolean function f such that for 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 , where (n)  0 as .

Toman, E., Olejár, D., Stanek, M. 2008. Average Degree in the Interval Graph of a Random Boolean Function. In Computing and Informatics, vol. 27, no.4, pp. 627-638. 1335-9150.

Toman, E., Olejár, D., Stanek, M. (2008). Average Degree in the Interval Graph of a Random Boolean Function. Computing and Informatics, 27(4), 627-638. 1335-9150.