Extensions of Extremal Graph Theory to Grids

Authors

Bret Thacher, Williams CollegeFollow

Abstract

We consider extensions of Turán's original theorem of 1941 to planar grids. For a complete kxm array of vertices, we establish in Proposition 4.3 an exact formula for the maximal number of edges possible without any square regions. We establish with Theorem 4.12 an upper bound and with Theorem 4.15 an asymptotic lower bound for the maximal number of edges on a general grid graph with n vertices and no rectangles.

Author Bio

I graduated from Williams College with a degree in mathematics in June 2009. This paper was fueled by thoughts that arose from a colloquium talk I gave in October 2008, and was completed from February through May 2009 with the help of my faculty advisor, Dr. Frank Morgan.

Faculty Sponsor

Frank Morgan

Recommended Citation

Thacher, Bret (2009) "Extensions of Extremal Graph Theory to Grids," Rose-Hulman Undergraduate Mathematics Journal: Vol. 10: Iss. 2, Article 10.
Available at: https://scholar.rose-hulman.edu/rhumj/vol10/iss2/10