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 let G_n be the complement of H_n. Then G_n has binom(n,2) − n > floor(n²/4) edges, its flag complex is homotopy equivalent to a wedge of two circles, 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 independence complexes of graphs with average degree two and uses a leaf reduction and the homotopy types of cycle independence complexes. Complete exact censuses at (7,14) and (8,20), including independent labeled implementations, verify the Betti-number distributions and identify the violating maximizers by exact permutation-orbit equality. This record contains the venue-neutral preprint and LaTeX source, exact graph6 witnesses, independent Python and C censuses, permutation-orbit validation, integral and unlabeled audits, captured verification outputs, and a pinned Lean 4 structural companion. The Lean companion checks the all-order graph family, connectedness, leaf-to-triangle certificate, exact degree and edge formulas, the connected-complement obstruction, finite witnesses, and the strict post-Turán inequality. AI disclosure: OpenAI Codex assisted with computational exploration, literature and novelty searches, code and Lean development, proof development, and drafting. Anthropic Claude was used for independent adversarial review. Neither system is an author.