论文标题
平均程度较大的小子图
Small subgraphs with large average degree
论文作者
论文摘要
在本文中，我们研究了在给定图中找到小密集子图的基本问题。对于实际数字$ s> 2 $，我们证明，$ n $顶点上的每个图表至少$ d $都包含一个平均度的子图，至少包含$ nd^{ - \ frac { - \ frac {s} {s-2}} {s-2}}}}}}（\ log d）^{\ d）这是最佳的，直到多毛体因子，并解决了Feige和Wagner的猜想。此外，我们还表明，每个图表具有$ n $顶点和平均程度至少$ n^{1- \ frac {2} {s}+\ varepsilon} $包含平均水平的子图，至少$ s $ on $ _ {\ o _ {\ varepsilon，s}（s}（1）$ vertices $ o o o o _ o _ {\ varepsilon，s $ vertices $ not ocation and o o o o o o o o o o o o o o o o o o（o o（猜想的Verstraëte。
In this paper 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^{-\frac{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-\frac{2}{s}+\varepsilon}$ contains a subgraph of average degree at least $s$ on $O_{\varepsilon,s}(1)$ vertices, which is also optimal up to the constant hidden in the $O(.)$ notation, and resolves a conjecture of Verstraëte.
