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

G. Agnarsson
University of Iceland
Dunhaga 3, IS-107 Reykjavik, Iceland

William T. Trotter
Department of Mathematics
Arizona State University
Tempe, Arizona 85287, U.S.A.

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: 
File:   pub/reports/