Date:
Thu, 19/01/202317:15-19:00
Location:
Zoom
Zoom Link: https://ucph-ku.zoom.us/j/69937085835
Password: 123456
Title: Small subgraphs with large average degree
Abstract:
We study the fundamental problem of finding small dense subgraphs in a given graph. For a real number s>2, we prove that every graph on n vertices with average degree at least d contains a subgraph of average degree at least s on at most nd^{-s/(s-2)}(log d)^{O_s(1)} vertices. This is optimal up to the polylogarithmic factor, and resolves a conjecture of Feige and Wagner. In addition, we show that every graph with n vertices and average degree at least n^{1-2/s+eps} contains a subgraph of average degree at least s on O_{eps,s}(1) vertices, which is also optimal up to the constant hidden in the O(.) notation, and resolves a conjecture of Verstraete.
Joint work with Benny Sudakov and Istvan Tomon.
Password: 123456
Title: Small subgraphs with large average degree
Abstract:
We study the fundamental problem of finding small dense subgraphs in a given graph. For a real number s>2, we prove that every graph on n vertices with average degree at least d contains a subgraph of average degree at least s on at most nd^{-s/(s-2)}(log d)^{O_s(1)} vertices. This is optimal up to the polylogarithmic factor, and resolves a conjecture of Feige and Wagner. In addition, we show that every graph with n vertices and average degree at least n^{1-2/s+eps} contains a subgraph of average degree at least s on O_{eps,s}(1) vertices, which is also optimal up to the constant hidden in the O(.) notation, and resolves a conjecture of Verstraete.
Joint work with Benny Sudakov and Istvan Tomon.