Main facts

Proposition 3.1 (Necessity [3])   If an AS ${\cal V}$ is m-ideal for some m, then there is connected matroid ${\cal M}$ appropriate for ${\cal V}$.

The reciprocal requires an extra assumption: 

Proposition 3.2 (Sufficiency [3])   Let q=p^m be a prime power and let ${\cal V}$ be an AS. Suppose there is connected matroid ${\cal M}$ appropriate for ${\cal V}$.

If ${\cal M}$ is representable, then ${\cal V}$ is q-ideal.

Indeed, there is a beautiful characterization of universal-ideality:
 
 Proposition 3.3 ([1])   An AS ${\cal V}$ is universally-ideal if and only if ${\cal V}$ is 2-ideal and 3-ideal.
 

Open problem

If there is a connected matroid ${\cal M}$ appropriate for an AS which is not representable over the field $\mbox{\it GF}(q)$, decide whether the AS is q-ideal.
 
 

Regarding graphs, G=(V,E) let ${\cal V}(G)$ be the collection of sets that include at least one edge:

$$V_0\in {\cal V}(G)\ \Leftrightarrow\ \exists \{u,v\}\in E:\ \{u,v\}\subset V_0.$$

Then the following conditions are pairwise equivalent:

1.

G=(V,E) is a multipartite graph, i.e. there is a partition $\left[V_k\right]_k$ of V such that

$$\{u,v\}\in E\ \Leftrightarrow\ \exists k_1,k_2: k_1\not= k_2\;\&\; u\in V_{k_1}\;\&\; v\in V_{k_2}.$$

2.

${\cal V}(G)$ is I-ideal.

3.

$\mathop{\rm Max}_{\cal E,p}\rho_{\cal E}(p>\frac{2}{3}$.

4.

${\cal V}(G)$ has an appropriate representable matroid.

 
 

Inmediately a procedure to build a SSS follows:

1.

Given a set of participants V and a collection ${\cal V}\subset {\cal P}(V)$,

2.

decide whether ${\cal V}$ has an appropriate matroid ${\cal M}$,

3.

if ${\cal M}$ 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 ${\cal V}\in {\cal P}({\cal P}([\![1,n]\!]))$ whose elements are of the same cardinality, say k, decide whether there is a matroid of rank k whose bases are the elements in ${\cal V}$.

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.

2000-11-28