On the Diameter of Matroid Ports

  • Jaume Martí-Farré
  • Carles Padró
  • Leonor Vázquez

Abstract

A clutter or antichain on a set defines a hypergraph. Matroid ports are a special class of clutters, and this paper deals with the diameter of matroid ports, that is, the diameter of the corresponding hypergraphs. Specifically, we prove that the diameter of every matroid port is at most $2$. The main interest of our result is its application to secret sharing. Brickell and Davenport proved in 1989 that the minimal qualified subsets of every ideal secret sharing scheme form a matroid port. Therefore, our result provides a new necessary condition for an access structure to admit an ideal secret sharing scheme.

Published
2008-07-14
Article Number
N27