Average Degree in the Interval Graph of a Random Boolean Function

Authors

  • Eduard Toman
  • Daniel Olejár
  • Martin Stanek

Keywords:

Random Boolean function, interval graph

Abstract

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 .

Downloads

Download data is not yet available.

Downloads

Published

2012-01-26

How to Cite

Toman, E., Olejár, D., & Stanek, M. (2012). Average Degree in the Interval Graph of a Random Boolean Function. Computing and Informatics, 27(4), 627–638. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/235