2025/05/30 by Francesco Barioli, Barioli, Francesco, Shaun Fallat +5
Engineering · Mathematics · #05C35 #05C50 #15A03 #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2505.24577
openalex publication_date 2025/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Since the transformative workshop by the American Institute of Mathematics on the minimum rank of a graph, two longstanding open problems have captivated the community interested in the minimum rank of graphs: the graph complement conjecture and the δ-conjecture. In this paper, we use a classical result of Mader (1972) to establish a weak version of the graph complement conjecture for all key minimum rank parameters. In addition, again using the same result of Mader, we present some extremal resolutions of the δ-conjecture. Furthermore, we incorporate the assumption of the δ-conjecture and extensive work on graph degeneracy to improve the bound in the weak version of the graph complement conjecture. We conclude with a list of conjectured bounds on the positive semidefinite variant of the Colin de Verdière number.