Yes, this is a cute bound. And you can improve it by 1 by including the empty set, so a(n)+1 <= M(n). -Veit On Nov 19, 2012, at 10:46 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
As a matter of curiosity a rather poor (but cute) lower bound can be obtained for the unique union code size by restricting oneself to two element subsets of the given n-set. One gets a classical graph theory problem, namely:
If a(n) is the maximum number of edges in an n-vertex graph of girth 5. Then a(n) <= M(n).
If G is a (simple) graph on n vertices with girth 5 then G has no 3-cycles or 4-cycles. This implies that the set of edges is a unique union code on n symbols. [Here an edge is a 2 element set of vertices.] Thus a(n) <= M(n). In particular, the value a(10) = 15 is given by the Petersen graph<http://en.wikipedia.org/wiki/Petersen_graph>.
Values of a(n) for n to 30 are given in http://oeis.org/A006856. The extremal graphs can be found in the paper Extremal graphs without three-cycles or four-cycles<http://www.math.udel.edu/%7Elazebnik/papers/ex34a_v2.pdf>by Garnick, et al.
--Edwin