Name
Abstract | ||
|---|---|---|
In 2002, Bollobas and Scott posed the following problem: for an integer k >= 2 and a graph G of m edges, what is the smallest f(k, m) such that V(G) can be partitioned into V-1,..., V-k in which e(V-i boolean OR V-j) <= f (k, m) for all 1 <= i not equal j <= k, where e(V-i boolean OR V-j) denotes the number of edges with both ends in V-i boolean OR V-j? In this paper, we solve this problem asymptotically by showing that f (k, m) <= m/(k - 1) + o(m). We also show that V(G) can be partitioned into V-1,..., V-k such that e(V-i boolean OR V-j) <= 4m/k(2) + 4 Delta/k + o(m) for 1 <= i not equal j <= k, where Delta denotes the maximum degree of G. This confirms a conjecture of Bollobas and Scott. (C) 2016 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1002/rsa.20642 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | Field | DocType |
graph,judicious partitioning,Chernoff inequality,Azuma-Hoeffding inequality | Integer,Graph,Discrete mathematics,Combinatorics,struct,Degree (graph theory),Conjecture,Mathematics,Chernoff bound | Journal |
Volume | Issue | ISSN |
50.0 | 1.0 | 1042-9832 |
Citations | PageRank | References |
4 | 0.43 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Genghua Fan | 1 | 412 | 65.22 |
| liu | 2 | 195 | 21.38 |