CMU Campus
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(Kn,F) and ex(Kn,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, 2017
Time: 3:30 pm
Location: Wean Hall 8220
Submitted by:  Bukh
Note: 3:10 pm, cookies and tea, Wean Hall 6220.