An Infinite Dense Counterexample Family for Extremal First Betti Numbers of Flag Complexes

Abstract

Beers and Bakke Botnan conjectured that every graph maximizing the first reduced Betti number of its flag complex among graphs with fixed numbers of vertices and edges contains a complete bipartite spanning subgraph. We give an infinite family of counterexamples strictly above the Turán threshold that motivates the conjecture. For every n ≥ 7, let H_n consist of a triangle, a two-edge path attached to one triangle vertex, and n − 5 leaves at the other end of the path, and put G_n = H̄_n. Then G_n has binom(n,2) − n > ⌊n²/4⌋ edges, its flag complex is homotopy equivalent to S¹ ∨ S¹, and 2 is the maximum first reduced Betti number among all graphs with the same numbers of vertices and edges. Since H_n is connected, G_n has no complete bipartite spanning subgraph. The proof reduces the extremal upper bound to the independence complexes of graphs with average degree two and then uses a leaf reduction and the homotopy types of cycle independence complexes. Complete exact censuses at (7,14) and (8,20), including two independent labeled implementations, verify the distributions of Betti numbers and identify the violating maximizers by explicit permutation-orbit equality.