Biclique decompositions from Welzl orders

13^th October 2026, 13:00 Ashton Lecture Theatre
Yelena Yuditsky
University of Leeds

Abstract

A biclique decomposition of a graph is a partition of its edges into complete bipartite subgraphs. We are interested in biclique decompositions of small size, where the size of a decomposition is defined as the sum of the numbers of vertices in its bicliques.

We consider graphs whose vertices admit an ordering such that the neighborhood of every vertex is the union of a sublinear number of intervals. For this class of graphs, we establish bounds on the size of biclique decompositions and provide an algorithm for constructing such decompositions.

Our results have several applications, including upper bounds for the Zarankiewicz problem, as well as applications to matrix multiplication, quantum circuit complexity, and shortest-path algorithms.

This is a joint work with Jean Cardinal and Rose McCarty.

Additional Materials

• https://arxiv.org/pdf/2606.09785