Average Degree in the Interval Graph of a Random Boolean Function
Eduard Toman ; Daniel Olejár ; Martin Stanek
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
Text on Computing and Informatics
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 .
Publié le : 2012-01-26
Classification:  Random Boolean function; interval graph 
@article{cai235,
     author = {Eduard Toman and Daniel Olej\'ar and Martin Stanek},
     title = {Average Degree in the Interval Graph of a Random Boolean Function},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai235}
}

Eduard Toman; Daniel Olejár; Martin Stanek. Average Degree in the Interval Graph of a Random Boolean Function. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai235/