Tight Cumulative Bounds for Maximal Induced Bicliques Under Edge Insertions
Under edge insertions, a maximal induced biclique can lose maximality and later regain it. We prove that, over all edge-insertion orders on n vertices, both the total number of births of maximal induced bicliques, counted with multiplicity, and the number of distinct maximal induced bicliques encountered are Θ(n·3n/3). This improves the bound obtained by applying the static extremal estimate to each insertion by a factor of n. The proof combines local maximal-independent-set encodings with a rigidity argument for Seidel-switching certificates. We also give a polynomial-space algorithm that reports exactly the changes caused by a single insertion in O(n4(λ+1)) time, where λ is the number of bicliques created or destroyed.
Authors
- Mohamed Jiddou
Publication Details
- Journal
- Preprints.org
- Published
- 2026-11-16
- DOI
- https://doi.org/10.20944/preprints202611.1511.v1
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint