Bounds for pairs in judicious partitioning of graphs1. Issue 1 (26th February 2016)

• Record Type: Journal Article
• Authors: Fan, Genghua; Hou, Jianfeng
• Is Part Of: Random structures & algorithms. Volume 50:Issue 1(2017)
• Page Start: 59
• Page End: 70
• Publication Date: 2016-02-26
• Subjects: graph -- judicious partitioning -- Chernoff inequality -- Azuma‐Hoeffding inequality; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20642
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: In 2002, Bollobás 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 ∪ V j ) ≤ f ( k, m ) for all 1 ≤ i ≠ j ≤ k, where e ( V i ∪ V j ) denotes the number of edges with both ends in V i ∪ 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 ∪ V j ) ≤ 4 m / k 2 + 4 Δ / k + o ( m ) for 1 ≤ i ≠ j ≤ k, where Δ denotes the maximum degree of G . This confirms a conjecture of Bollobás and Scott. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 59–70, 2017