### 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.

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.