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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Tight Cumulative Bounds for Maximal Induced Bicliques Under Edge Insertions

Mohamed Jiddou
Preprints.org
Advanced Graph Theory Research
preprint

Tight Cumulative Bounds for Maximal Induced Bicliques Under Edge Insertions

Mohamed Jiddou
preprint en

Abstract

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.

Preprints.org
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon