TY - JOUR
AU - Toman, Eduard
AU - Olejár, Daniel
AU - Stanek, Martin
PY - 2012/01/26
Y2 - 2024/06/17
TI - Average Degree in the Interval Graph of a Random Boolean Function
JF - COMPUTING AND INFORMATICS
JA - Comput. Inform.
VL - 27
IS - 4
SE - Articles
DO -
UR - https://www.cai.sk/ojs/index.php/cai/article/view/235
SP - 627-638
AB - 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 .
ER -