Biclique decompositions from Welzl orders
2026-06-08 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a way to break down graphs into simpler parts called bicliques, which are fully connected bipartite subgraphs. They focus on graphs where each vertex's neighbors can be described using a small number of intervals in a certain order. The authors show these graphs can be represented efficiently using biclique decompositions with a small total size. By using earlier work on ordering vertices in such graphs, they generalize known mathematical results related to graph theory, matrix multiplication, quantum circuits, and shortest path algorithms in well-structured cases.
biclique decompositioncomplete bipartite graphinterval neighborhoodgraph vertex orderingneighborhood complexityZarankiewicz problemmatrix multiplicationquantum circuit complexityshortest path algorithms
Authors
Jean Cardinal, Rose McCarty, Yelena Yuditsky
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.