Probabilistic Methods for Decomposition Dimension of Graphs

In a graph G, the distance from an edge e to a set FE(G) is the vertex distance from e to F in the line graph L(G). For a decomposition of E(G) into k sets, the distance vector of e is the k-tuple of distances from e to these sets. The decomposition dimension dec(G) of G is the smallest k such that G has a decomposition into k sets so that the distance vectors of the edges are distinct. For the complete graph K _n and the k-dimensional hypercube Q _k , we prove that (2–o(1))lgndec(K _n )(3.2+o(1))lgn and k/lgk dec(Q _k ) (3.17+o(1))k/lgk. The upper bounds use probabilistic methods directly or indirectly. We also prove that random graphs with edge probability p such that p n ^1– for some positive constant have decomposition dimension (lnn) with high probability. Acknowledgments.The authors thank Noga Alon for clarifying and strengthening the results in Sections 3 and 4. Thanks also go to a referee for repeated careful readings and suggestions.AMS classifications: 05C12, 05C35, 05D05, 05D40