Abstract
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.
Keywords
Cite this article
@article{cai-1632,
author = {Eduard Toman and Daniel Olejár and Martin Stanek},
title = {Average Degree in the Interval Graph of a Random Boolean Function},
journal = {Computing and Informatics},
volume = {27},
number = {4},
pages = {627--638},
year = {2008},
issn = {1335-9150},
url = {https://cai.type.sk/content/2008/4/average-degree-in-the-interval-graph-of-a-random-boolean-function/}
}
TY - JOUR AU - Eduard Toman AU - Daniel Olejár AU - Martin Stanek TI - Average Degree in the Interval Graph of a Random Boolean Function JO - Computing and Informatics VL - 27 IS - 4 SP - 627 EP - 638 PY - 2008 SN - 1335-9150 UR - https://cai.type.sk/content/2008/4/average-degree-in-the-interval-graph-of-a-random-boolean-function/ KW - Random Boolean function KW - interval graph ER -
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. https://cai.type.sk/content/2008/4/average-degree-in-the-interval-graph-of-a-random-boolean-function/