Metraipolis › archive › dc_b7bbacbd8423

Tight Asymptotic Bounds on the Size of Order Graphs — arXiv:2610.39311

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.39311
License (as archived)
CC0-1.0
Archived
2026-11-01T02:47:42.862Z
SHA-256 of the archived text
de0abaa615b1c2a965406add2c3c79ac86af9f92c2bc06941fbd648c6e2bf150
Stable URL of this page
https://metraipolis.com/documento/dc_b7bbacbd8423

How to cite

Tight Asymptotic Bounds on the Size of Order Graphs — arXiv:2610.39311 — arXiv (en), https://arxiv.org/abs/2610.39311 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b7bbacbd8423 (Metraipolis archive dc_b7bbacbd8423, sha256 de0abaa615b1c2a965406add2c3c79ac86af9f92c2bc06941fbd648c6e2bf150)
BibTeX
@misc{dcb7bbacbd8423,
  title = {Tight Asymptotic Bounds on the Size of Order Graphs — arXiv:2610.39311},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.39311},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b7bbacbd8423; sha256 de0abaa615b1c2a965406add2c3c79ac86af9f92c2bc06941fbd648c6e2bf150},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.39311. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Order graphs were introduced by Arroyuelo et al.\ (TODS 2024) as a generalization of the ring index, to support worst-case optimal joins on relations of arity $d$ while storing as few columns as possible: the index stores one column per edge, so its size is proportional to the number of edges of an order graph. It was known that the minimum number of edges lies between $\Omega(2^d\sqrt d)$ and $O(2^d d)$, and the lower bound had been claimed to be $42$ for $d=6$. We first exhibit an order graph with only $40$ edges for $d=6$, and show that the proof of that lower bound holds only for unions of cycles, whereas order graphs can be smaller than the smallest set of cycles. We give a corrected statement and proof that holds for every order graph: there must be at least $\max_m\binom dm\lceil m/2\rceil$ edges. This bound is $40$ for $d=6$, so our $40$-edge graph is optimal. We then settle the asymptotic question: the minimum size is $\Theta(2^d\sqrt d)$. This is obtained via an explicit construction, based on symmetric chain decompositions of the Boolean lattice, with at most $(d-1)\binom{d}{\lfloor d/2\rfloor}+2^d$ edges. The upper bound is within a factor $4+O(d^{-1/2})$ of the lower bound, and both numerically and asymptotically better than trie switching.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.39311 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:17:58.598Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).