  We study the recently introduced boolean-width of graphs. Our structural
results are as follows. Firstly, we show that almost surely the boolean-width
of a random graph on $n$ vertices is $O(\log^2 n)$, and it is easy to find the
corresponding decomposition tree.
  Secondly, for any constant $d$ a graph of maximum degree $d$ has
boolean-width linear in treewidth. This implies that almost surely the
boolean-width of a (sparse) random $d$-regular graph on $n$ vertices is linear
in $n$.
  Thirdly, we show that the boolean-cut value is well approximated by VC
dimension of corresponding set system. Since VC dimension is widely studied, we
hope that this structural result will prove helpful in better understanding of
boolean-width.
  Combining our first structural result with algorithms from Bui-Xuan et al
\cite{BTV09,BTV09II} we get for random graphs quasi-polynomial $O^*(2^{O(\log
^4 n)})$ time algorithms for a large class of vertex subset and vertex
partitioning problems.
