Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 5/23 -- Nitya Mani

Weiyun Ma wyma at
Mon May 20 13:23:51 PDT 2019

Hi everyone,

This Thursday at theory lunch, Nitya will tell us about "Max-k-Cuts in H-Free Graphs." (See abstract below.)

As always, please join us from noon to 1pm at 463A.


Max-k-Cuts in H-Free Graphs

Speaker: Nitya Mani

We study the following question: how few edges can we delete from any H-free graph on n vertices in order to make the resulting graph k-colorable? It turns out that various classical problems in extremal combinatorics are special cases of this problem, and this quantity yields bounds on the Max-k-Cut of an H-free graph. For H any fixed odd cycle, we determine the answer up to a constant factor when n is sufficiently large. We also prove upper bounds when H is a clique or lies in some other families of graphs.



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list