Judicious partitions of directed graphs1. Issue 1 (31st December 2014)

• Record Type: Journal Article
• Authors: Lee, Choongbum; Loh, Po‐Shen; Sudakov, Benny
• Is Part Of: Random structures & algorithms. Volume 48:Issue 1(2016)
• Page Start: 147
• Page End: 170
• Publication Date: 2014-12-31
• Subjects: Judicious partitioning -- directed graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20579
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: The area of judicious partitioning considers the general family of partitioning problems in which one seeks to optimize several parameters simultaneously, and these problems have been widely studied in various combinatorial contexts. In this paper, we study essentially the most fundamental judicious partitioning problem for directed graphs, which naturally extends the classical Max Cut problem to this setting: we seek bipartitions in which many edges cross in each direction. It is easy to see that a minimum outdegree condition is required in order for the problem to be nontrivial, and we prove that every directed graph with m edges and minimum outdegree at least two admits a bipartition in which at least ( 1 6 + o ( 1 ) ) m edges cross in each direction. We also prove that if the minimum outdegree is at least three, then the constant can be increased to 1 5 . If the minimum outdegree tends to infinity with n, then the constant increases to 1 4 . All of these constants are best‐possible, and provide asymptotic answers to a question of Alex Scott. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 147–170, 2016