Classical questions in graph theory ask about ex(G,F), the maximum number of edges in an F-free subgraph of G, for some ﬁxed family F of graphs. For example, the Turán and Zarankiewicz problems ask about ex(Kn,F) and ex(Kn,n,F) respectively. Specifically, these study the corresponding asymptotics when n → ∞. Or, when F = C is the family of cycles, this becomes the graphic matroid rank, and is considered as a function of G for various diﬀerent G. The second example inspires the inverted problem of optimising some monotone graph parameter over all host graphs G for which ex(G,F) = k, where now both k and F are ﬁxed. We will explore the most natural question: what is the largest possible number of edges among all G with ex(G,F) = k? This is joint work with Christopher Cox.
Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.
Back to the ACO home page