On the information ratio of graphs with many leaves

Abstract

In a secret sharing scheme a piece of information – the secret – is
distributed among a finite set of participants, such that only some predefined coalitions can recover it. This set of subsets is called access structure, which is supposed to be monotone, hence the system can be characterized by its minimal
elements. Within this paper we consider graph based schemes access structures,
i.e. systems with minimal subsets of size two.
The efficiency of a scheme is measured by the amount of information the
most heavily loaded participant must remember. For a given system, one of the
most interesting problem of this topic is the exact determination or at least the
estimation of this amount, called information ratio.
We examine the information ratio of several systems based on graphs with
many leaves, by proving non-trivial lower and upper bounds for the ratio. On one
hand, we apply the so-called entropy method for proving lower bounds. On the
other hand, some symmetric and recursive constructions are given for yielding
upper bounds.