Biclique decompositions from Welzl orders
Abstract
A biclique decomposition of a graph is a partition of its edges into complete bipartite subgraphs. We consider graphs whose vertices can be ordered such that the neighborhood of every vertex is the union of a sublinear number of intervals. We observe that these graphs admit compact representations in the form of biclique decompositions of small size. Here, the size of a decomposition is measured as the sum of the number of vertices of its bicliques. Combining this result with the existence of suitable vertex orderings for graphs of low neighborhood complexity, as proven by Welzl in 1988, we recover and extend several known results up to logarithmic factors. These results include upper bounds on the Zarankiewicz problem, matrix multiplication, quantum circuit complexity, and shortest path algorithms in "well-structured" instances.
Related
- A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem: Rearrangement, Extremal Construction, and Biclique Realizability
- Induced packing treewidth II. Excluding a clique or a biclique
- Mostow-Type Decompositions and Geometric Means for Symmetric Cones
- Decompositions of CSBPs via Poissonian Intertwining
- Decompositions of birational toric morphism between threefolds
BibTeX
@misc{cardinal2026biclique,
title = {{Biclique decompositions from Welzl orders}},
author = {Jean Cardinal and Rose McCarty and Yelena Yuditsky},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.09785},
eprint = {2606.09785},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.09785},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Biclique decompositions from Welzl orders
AU - Jean Cardinal
AU - Rose McCarty
AU - Yelena Yuditsky
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2606.09785
UR - https://arxiv.org/abs/2606.09785
AB - A biclique decomposition of a graph is a partition of its edges into complete bipartite subgraphs. We consider graphs whose vertices can be ordered such that the neighborhood of every vertex is the union of a sublinear number of intervals. We observe that these graphs admit compact representations in the form of biclique decompositions of small size. Here, the size of a decomposition is measured as the sum of the number of vertices of its bicliques. Combining this result with the existence of suitable vertex orderings for graphs of low neighborhood complexity, as proven by Welzl in 1988, we recover and extend several known results up to logarithmic factors. These results include upper bounds on the Zarankiewicz problem, matrix multiplication, quantum circuit complexity, and shortest path algorithms in "well-structured" instances.
ER -