Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
Joseph Briggs Carnegie Mellon Title: Inverting the Turán Problem Abstract: Classical questions in graph theory ask about ex(G,F), the maximum number of edges in an F-free subgraph of G, for some fixed family F of graphs. For example, the Turán and Zarankiewicz problems ask about ex(K,_{n}F) and ex(K_{n,n},F) respectively. Specifically, these study the corresponding asymptotics when $n \rightarrow \infty$. 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 different 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 fixed. 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.Date: Thursday, September 7, 2017Time: 3:30 pmLocation: Wean Hall 8220Submitted by: BukhNote: 3:10 pm, cookies and tea, Wean Hall 6220. |