pith. sign in

arxiv: 2606.09785 · v1 · pith:RZBCNPL7new · submitted 2026-06-08 · 🧮 math.CO · cs.DM

Biclique decompositions from Welzl orders

Jean Cardinal , Rose McCarty , Yelena Yuditsky This is my paper

Pith reviewed 2026-06-27 15:52 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords biclique decompositionWelzl orderneighborhood complexityZarankiewicz problemmatrix multiplicationshortest pathsgraph orderinginterval unions
0
0 comments X

The pith

Graphs whose neighborhoods form unions of sublinear intervals in some vertex order admit biclique decompositions of small total size.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that when vertices can be linearly ordered so each neighborhood consists of a sublinear number of intervals, the edges can be partitioned into bicliques whose aggregate size, counted as the sum of vertices across all bicliques, remains correspondingly small. This structural fact is then combined with the existence of such orderings, already known for graphs of low neighborhood complexity, to obtain or recover upper bounds on several classical quantities up to logarithmic factors. A reader would care because the same ordering property controls the complexity of representing the graph for problems ranging from extremal set theory to algorithmic speedups in matrix operations and path finding.

Core claim

If the vertices of a graph admit an ordering in which every neighborhood is the union of a sublinear number of intervals, then the graph possesses a biclique decomposition whose size, measured by the sum of the numbers of vertices in its bicliques, is also small. Pairing this observation with Welzl's 1988 guarantee of suitable orderings for low-neighborhood-complexity graphs immediately yields improved or matching bounds, up to logarithmic factors, for the Zarankiewicz problem, fast matrix multiplication, quantum circuit complexity, and shortest-path computation on well-structured instances.

What carries the argument

Biclique decomposition constructed directly from a Welzl order, in which edges are grouped into complete bipartite subgraphs according to the interval structure of neighborhoods.

If this is right

  • Graphs with low neighborhood complexity possess biclique decompositions whose total size is subquadratic.
  • Upper bounds on the Zarankiewicz number z(m,n;s,t) follow directly from the decomposition size.
  • Matrix-multiplication time for structured matrices is governed by the same interval-union parameter.
  • Shortest-path algorithms on graphs admitting Welzl orders run in time controlled by the decomposition size.
  • Quantum circuit depth or size for certain Boolean functions is bounded by the same quantity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The interval-union property may serve as a single parameter that simultaneously explains several seemingly unrelated extremal and algorithmic bounds.
  • One could test whether common real-world graphs, such as social or citation networks, admit orderings with very few intervals per neighborhood and thereby obtain compact biclique representations in practice.
  • Similar decomposition arguments might extend to hypergraphs or to other ordered set systems whose neighborhoods have bounded interval complexity.

Load-bearing premise

The existence of suitable vertex orderings for graphs of low neighborhood complexity, as proven by Welzl in 1988.

What would settle it

Exhibit a concrete graph whose vertices can be ordered so every neighborhood is the union of o(n) intervals yet every biclique decomposition has total vertex sum Ω(n^{1+ε}) for some ε>0.

Figures

Figures reproduced from arXiv: 2606.09785 by Jean Cardinal, Rose McCarty, Yelena Yuditsky.

Figure 1
Figure 1. Figure 1: A graph with a biclique decomposition into three bicliques of total size [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The tree T and the two subtrees used to obtain the interval between v3 and v8. Observe now that every interval I in ⪯ is the union of ⌈log2 n⌉ disjoint dyadic intervals L(t). To see this, consider the maximal dyadic intervals contained in I. Since none of the corresponding nodes is an ancestor of another, these dyadic intervals are disjoint. Moreover, for each level of T, there is at most one node t on tha… view at source ↗
Figure 3
Figure 3. Figure 3: A Python code snippet implementing the algorithm described in the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A stabilizer circuit which constructs the graph with two vertices and one edge. [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A depiction of pivoting with the “switched” edges/non-edges highlighted in red. [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript claims that if a graph admits a vertex ordering in which the neighborhood of every vertex is the union of a sublinear number of intervals, then it admits a biclique decomposition whose size—measured as the sum, over all bicliques, of the number of vertices they contain—is correspondingly small. The authors then invoke Welzl’s 1988 theorem guaranteeing the existence of such orderings for graphs of low neighborhood complexity, and thereby recover (up to logarithmic factors) known upper bounds on the Zarankiewicz problem, on the complexity of matrix multiplication, on quantum circuit complexity, and on shortest-path algorithms in well-structured instances.

Significance. If the central observation holds, the paper supplies a clean, combinatorial unification of several existing bounds via a single, explicitly qualified reduction to an external 1988 result. The approach is parameter-free once the Welzl ordering is given and treats all recovered bounds with the appropriate logarithmic slack; this may prove useful for additional problems whose complexity is governed by neighborhood structure.

minor comments (3)
  1. [§2] §2, Definition 2.1: the precise measure of decomposition size (sum of vertex incidences) is introduced without an accompanying notation that is used consistently in the subsequent theorems; a single symbol would improve readability.
  2. [§4] §4, Theorem 4.3: the statement that the new bound extends the known result “up to logarithmic factors” is correct but would benefit from an explicit side-by-side comparison (even in a remark) with the best previously published constant-factor or polylog-free bound.
  3. [Introduction] The paper relies on Welzl’s theorem as a black box; while this is methodologically sound, a one-sentence reminder in the introduction of the precise neighborhood-complexity hypothesis under which the ordering exists would help readers who are not already familiar with the 1988 reference.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, the assessment of significance, and the recommendation of minor revision. The report correctly identifies the paper's core contribution as a parameter-free reduction from neighborhood-complexity orderings (via Welzl 1988) to compact biclique decompositions, with logarithmic slack on the recovered bounds. No major comments are enumerated in the report, so we address the recommendation directly below.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation consists of an observation that graphs with vertex orderings where neighborhoods are unions of sublinear intervals admit small biclique decompositions (measured by sum of vertices), combined with Welzl's independent 1988 external theorem guaranteeing such orderings for low-neighborhood-complexity graphs. No equations reduce new bounds to self-defined or fitted quantities; the Welzl result is treated as a black-box external input with no self-citation chain or ansatz smuggling. The paper qualifies recovered bounds by logarithmic factors and relies on standard definitions, making the central claim self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard definitions of graphs and bicliques together with one external theorem; no new numerical parameters or postulated entities are introduced.

axioms (2)
  • standard math Standard definitions of graphs, edges, bicliques, and interval unions on a linear order.
    Invoked throughout the combinatorial argument.
  • domain assumption Existence of Welzl orders for graphs of low neighborhood complexity (Welzl 1988).
    Explicitly cited as the bridge to the new decomposition result.

pith-pipeline@v0.9.1-grok · 5660 in / 1383 out tokens · 28201 ms · 2026-06-27T15:52:17.946604+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 2 linked inside Pith

  1. [1]

    The structural complexity of matrix-vector multiplication.CoRR, abs/2502.21240,

    [AvdBM25] Emile Anand, Jan van den Brand, and Rose McCarty . The structural complexity of matrix-vector multiplication.CoRR, abs/2502.21240,

    arXiv

  2. [2]

    A scalable pattern mining approach to web graph compression with communities

    [BC08] Gregory Buehrer and Kumar Chellapilla. A scalable pattern mining approach to web graph compression with communities. In Marc Najork, Andrei Z. Broder, and Soumen Chakrabarti, editors,Proceedings of the International Conference on Web Search and Web Data Mining, WSDM 2008, Palo Alto, California, USA, February 11- 12, 2008, pages 95–106. ACM,

    2008

  3. [3]

    16 [BG25] Marthe Bonamy and Colin Geniet.χ-boundedness and neighbourhood complexity of bounded merge-width graphs.CoRR, abs/2504.08266,

    arXiv

  4. [4]

    Fast short- est path in graphs with sparse signed tree models and applications.CoRR, abs/2602.16605,

    [BGKM26] Édouard Bonnet, Colin Geniet, Eun Jung Kim, and Sungmin Moon. Fast short- est path in graphs with sparse signed tree models and applications.CoRR, abs/2602.16605,

    arXiv

  5. [5]

    [BGOdMT23] Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé

    To appear at ICALP’26. [BGOdMT23] Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé. Twin-Width V: Linear Minors, Modular Counting, and Matrix Multiplication. In Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté, editors, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023...

    2023

  6. [6]

    Geometric matching and bottleneck problems

    [CCCK24] Sergio Cabello, Siu-Wing Cheng, Otfried Cheong, and Christian Knauer. Geometric matching and bottleneck problems. In40th International Symposium on Computa- tional Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, pages 31:1–31:15,

    2024

  7. [7]

    Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng

    [CCG+25] Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng. Truly subquadratic time algorithms for diameter and related prob- lems in graphs of bounded vc-dimension. In66th IEEE Annual Symposium on Foun- dations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025, pages 2728–2765. IEEE,

    2025

  8. [8]

    Quantum circuit optimization based on dynamic grouping and ZX-calculus for reducing 2- qubit gate count.CoRR, abs/2507.14434,

    17 [CLX+25] Kai Chen, Wen Liu, GuoSheng Xu, Yangzhi Li, Maoduo Li, and Shouli He. Quantum circuit optimization based on dynamic grouping and ZX-calculus for reducing 2- qubit gate count.CoRR, abs/2507.14434,

    arXiv

  9. [9]

    Compact representation of semilinear and terrain-like graphs

    [CY25] Jean Cardinal and Yelena Yuditsky . Compact representation of semilinear and terrain-like graphs. In Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman, editors,33rd Annual European Symposium on Algorithms, ESA 2025, War- saw, Poland, September 15-17, 2025, LIPIcs, pages 67:1–67:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    2025

  10. [10]

    Preparing graph states forbidding a vertex-minor

    [DJ25] James Davies and Andrew Jena. Preparing graph states forbidding a vertex-minor. CoRR, abs/2504.00291v2,

    arXiv

  11. [11]

    Near-linear time computation of welzl orders on graphs with linear neighborhood complexity .CoRR, abs/2602.14625,

    [DK26] Jan Dreier and Clemens Kuske. Near-linear time computation of welzl orders on graphs with linear neighborhood complexity .CoRR, abs/2602.14625,

    arXiv

  12. [12]

    Better diameter algorithms for bounded vc-dimension graphs and geometric intersection graphs

    [DKP24] Lech Duraj, Filip Konieczny , and Krzysztof Potepa. Better diameter algorithms for bounded vc-dimension graphs and geometric intersection graphs. In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors,32nd Annual European Symposium on Algorithms, ESA 2024, Royal Holloway, London, United King- dom, September 2-4, 2024, LIPI...

    2024

  13. [13]

    Merge-width and first-order model checking

    [DT25] Jan Dreier and Szymon Toru ´nczyk. Merge-width and first-order model checking. In Michal Koucký and Nikhil Bansal, editors,Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 1944–1955. ACM,

    2025

  14. [14]

    The heisenberg representation of quantum computers.CoRR, abs/quant-ph/9807006,

    [Got98a] Daniel Gottesman. The heisenberg representation of quantum computers.CoRR, abs/quant-ph/9807006,

    Pith/arXiv arXiv

  15. [15]

    To- wards efficient synthesis of quantum graph states by fusing graph motifs.CoRR, abs/2606.02880,

    [JWFL26] Tingxiang Ji, Hansika Weerasena, Demitry Farfurnik, and Jianqing Liu. To- wards efficient synthesis of quantum graph states by fusing graph motifs.CoRR, abs/2606.02880,

    Pith/arXiv arXiv

  16. [16]

    Approximate all-pairs ham- ming distances and 0-1 matrix multiplication

    [KLP26] Miroslaw Kowaluk, Andrzej Lingas, and Mia Persson. Approximate all-pairs ham- ming distances and 0-1 matrix multiplication. In Christos D. Zaroliagis, Dinabandhu Bhandari, Prosenjit Gupta, and Swagatam Das, editors,Applied Algorithms - Third International Conference, ICAA 2026, Kolkata, India, January 7-9, 2026, Proceedings, Lecture Notes in Compu...

    2026

  17. [17]

    Complexity of graph-state prepa- ration by Clifford circuits.CoRR, abs/2402.05874 v3,

    [KMY25] Soh Kumabe, Ryuhei Mori, and Yusei Yoshimura. Complexity of graph-state prepa- ration by Clifford circuits.CoRR, abs/2402.05874 v3,

    arXiv

  18. [18]

    Fast and simple multiplication of bounded twin- width matrices.CoRR, abs/2602.20023,

    19 [KO26] László Kozma and Michal Opler. Fast and simple multiplication of bounded twin- width matrices.CoRR, abs/2602.20023,

    arXiv

  19. [19]

    Optimal and efficient partite decompositions of hypergraphs.CoRR, abs/2511.11855,

    [KPSS25] Andrew Krapivin, Benjamin Przybocki, Nicolás Sanhueza-Matamala, and Bernardo Subercaseaux. Optimal and efficient partite decompositions of hypergraphs.CoRR, abs/2511.11855,

    arXiv

  20. [20]

    [MMG19] Clément Meignant, Damian Markham, and Frédéric Grosshans

    An illustrated guide, Revised paperback reprint of the 1999 original. [MMG19] Clément Meignant, Damian Markham, and Frédéric Grosshans. Distributing graph states over arbitrary quantum networks.Phys. Rev. A, 100:052333, Nov

    1999

  21. [21]

    A survey of Zarankiewicz problems in geometry .CoRR, abs/2410.03702,

    [Smo24] Shakhar Smorodinsky . A survey of Zarankiewicz problems in geometry .CoRR, abs/2410.03702,

    arXiv

  22. [22]

    Flip-width: Cops and robber on dense graphs

    [Tor23] Szymon Toru ´nczyk. Flip-width: Cops and robber on dense graphs. In64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 663–700. IEEE,

    2023

  23. [23]

    Partition trees for triangle counting and other range searching problems

    [Wel88] Emo Welzl. Partition trees for triangle counting and other range searching problems. InProceedings of the Fourth Annual Symposium on Computational Geometry (Urbana, IL, 1988), pages 23–33. ACM, New York,

    1988