   Next:ImplementaciónUp:Computational experiments on thePrevious:Basic definitions

# Main facts

Proposition 3.1 (Necessity )   If an AS is m-ideal for some m, then there is connected matroid appropriate for .

The reciprocal requires an extra assumption:

Proposition 3.2 (Sufficiency )   Let q=pm be a prime power and let be an AS. Suppose there is connected matroid appropriate for .

If is representable, then is q-ideal.

Indeed, there is a beautiful characterization of universal-ideality:

Proposition 3.3 ()   An AS is universally-ideal if and only if is 2-ideal and 3-ideal.

Open problem

If there is a connected matroid appropriate for an AS which is not representable over the field , decide whether the AS is q-ideal.

Regarding graphs, G=(V,E) let be the collection of sets that include at least one edge: Then the following conditions are pairwise equivalent:

1.
G=(V,E) is a multipartite graph, i.e. there is a partition of V such that 2. is I-ideal.
3. .
4. has an appropriate representable matroid.

Inmediately a procedure to build a SSS follows:

1.
Given a set of participants V and a collection ,
2.
decide whether has an appropriate matroid ,
3.
if is representable, then construct the corresponding SSS according to Shamir's procedure.

We are building an experimentation computational system to deal with the following problems:

1.
Representation of matroids.
2.
Random selection of a matroid over the whole possibilities to pick a matroid over a ground set of n participants.
3.
Given a collection whose elements are of the same cardinality, say k, decide whether there is a matroid of rank k whose bases are the elements in .
4.
Decide whether a matroid is representable over a finite field.
5.
Specify a general procedure to build an ideal SSS provided a representable matroid.   Next:ImplementaciónUp:Computational experiments on thePrevious:Basic definitions
Guillermo Morales-Luna

2000-11-28