# 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