interesting methods for structured sparsity constraints

Paul Erdösa1, Frank Hararya2 and William T. Tuttea3
a1 Mathematical Institute, Budapest, Hungary.
a2 University of Michigan, Ann Arbor, U.S.A..
a3 University of Waterloo, Waterloo, Canada.
Our purpose in this note is to present a natural geometrical definition of the dimension of a graph and to explore some of its ramifications. In §1 we determine the dimension of some special graphs. We observe in §2 that several results in the literature are unified by the concept of the dimension of a graph, and state some related unsolved problems.