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 stanford.edu
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.

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



Best,

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


More information about the theory-seminar mailing list