![Geometry of Polynomials_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Geometry%20of%20Polynomials_hi-res.png.jpg?itok=GzqUUw1q)
Description
We consider the problem of finding large cuts in graphs that contain no small cliques. We show that for any r >= 3, every k_r-free graphs with maximum degree d has a cut that cuts at least a 1/2 + Ω(1/d^{1-1/2^{r-2}}) fraction of its edges. This generalizes a result of Shearer that shows every triangle-free d-regular graph has a cut that cuts at least a 1/2 + Ω(1/\sqrt{d}) fraction of its edges. Our proof yields a randomized polynomial-time algorithm.
All scheduled dates:
Upcoming
No Upcoming activities yet