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