Extremal Problems in Ordered Graphs
Author | : Craig Weidert |
Publisher | : |
Total Pages | : 58 |
Release | : 2009 |
ISBN-10 | : OCLC:1127688493 |
ISBN-13 | : |
Rating | : 4/5 (93 Downloads) |
Book excerpt: In this thesis we consider ordered graphs (that is, graphs with a fixed linear ordering on their vertices). We summarize and further investigations on the number of edges an ordered graph may have while avoiding a fixed forbidden ordered graph as a subgraph. In particular, we take a step toward confirming a conjecture of Pach and Tardos regarding the number of edges allowed when the forbidden pattern is a tree by establishing an upper bound for a particular ordered graph for which existing techniques have failed. We also generalize a theorem of Geneson by establishing an upper bound on the number of edges allowed if the forbidden graphs fit a generalized notion of a matching.