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

[Weiyun Ma]

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.

----------------------------------------------------------



Best,

Anna
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20190520/edb80e27/attachment-0001.html>