# The Maximum Number of Edges in a Graph of Bounded Dimensions with Applications to Ring Theory

### Stefan Felsner Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: felsner@inf.fu-berlin.de G. Agnarsson University of Iceland Dunhaga 3, IS-107 Reykjavik, Iceland email: geira@raunvis.hi.is William T. Trotter Department of Mathematics Arizona State University Tempe, Arizona 85287, U.S.A. email: trotter@ASU.edu Report B 98-10 August 1998

With a finite graph G = (V,E), we associate a partially ordered set P = (X,P) with X = V U E and x < e in P if and only if x is an endpoint of e in G. This posets is called the incidence poset of G. In this paper, we consider the function M (p,d) defined for p,d >= 2 as the maximum number of edges a graph G can have when it has p vertices and the dimension of its incidence poset is at most d. It is easy to see that M (p,2) = p- 1 as only the subgraphs of paths have incidence posets with dimension at most 2. Also, a well known theorem of Schnyder asserts that a graph is planar if and only if its incidence poset has dimension at most 3. So M (p,3) = 3 p - 6 for all p > = 3. In this paper, we use the product ramsey theorem, Turán's theorem and the Erdös/Stone Theorem to show that $lim_{p \rightarrow \infty} M(p,4)/p^2=3/8$. We therein derive some ring theoretic consequences of this in terms of minimal first syzygies and Betti numbers for monomial ideals.

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-98-10.ps.gz