Optimal bisections of directed graphs

DOI10.1002/RSA.21175MaRDI QIDQ6185053zbMATH OpenOpenAlexFDO

Authors Guanwu Liu, Jie Ma, Chunlei Zu

Publication date 5 January 2024

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2302.04050

zbMATH Keywords

bisectiondigraphjudicious partitioning problemsemidegree

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In this paper, motivated by a problem of Scott and a conjecture of Lee, Loh and Sudakov we consider bisections of directed graphs. We prove that every directed graph with $m$ arcs and minimum semidegree at least $d$ admits a bisection in which at least $left(fracd2(2d+1)+o(1)ight)m$ arcs cross in each direction. This provides an optimal bound as well as a positive answer to a question of Hou and Wu in a stronger form.

Recommendations

• On bisections of directed graphs
• On judicious bipartitions of directed graphs
• On bipartitions of directed graphs with small semidegree
• Bipartitions of oriented graphs
• A bound on judicious bipartitions of directed graphs

Cites work

• A bound on judicious bipartitions of directed graphs
• Better bounds for \(k\)-partitions of graphs
• Bipartite subgraphs
• Bipartitions of oriented graphs
• Bisections of graphs
• Bisections of graphs without short cycles
• Bounds for pairs in judicious partitioning of graphs
• Exact bounds for judicious partitions of graphs
• Graph partitioning: an updated survey
• scientific article; zbMATH DE number 3510345 (Why is no real title available?)
• Judicious partitions and related problems
• Judicious partitions of 3-uniform hypergraphs
• Judicious partitions of bounded‐degree graphs
• Judicious partitions of directed graphs
• Judicious partitions of hypergraphs
• Judicious partitions of uniform hypergraphs
• Judiciously 3-partitioning 3-uniform hypergraphs
• Maximum bisections of graphs without short even cycles
• Maximum cuts and judicious partitions in graphs without short cycles
• Maximum directed cuts in acyclic digraphs
• On a bottleneck bipartition conjecture of Erdős
• On bipartitions of directed graphs with small semidegree
• On bisections of directed graphs
• On bisections of graphs without complete bipartite graphs
• On judicious bipartitions of directed graphs
• On judicious bipartitions of graphs
• On judicious bisections of graphs
• On judicious partitions of uniform hypergraphs
• On several partitioning problems of Bollobás and Scott
• Partitioning 3-uniform hypergraphs
• Partitioning digraphs with outdegree at least 4
• Probability Inequalities for Sums of Bounded Random Variables
• Problems and results on judicious partitions
• Some Extremal Properties of Bipartite Subgraphs
• The Bollobás-Thomason conjecture for \(3\)-uniform hypergraphs
• Weighted sums of certain dependent random variables

Cited in

(1)

• Bisections of directed graphs without complete bipartite subgraphs

This page was built for publication: Optimal bisections of directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6185053)