2009/07/15 by Craig Weidert, Weidert, Craig
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2 #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.0907.2479
openalex publication_date 2009/07/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.