CS Paper Radar

Tight Asymptotic Bounds on the Size of Order Graphs

Ruben Becker, Adrián Gómez-Brandón, Gonzalo Navarro, Nicola Prezza

cs.DS ·submitted 2026-10-29 03:57 UTC · v2
theoryhot direction

Abstract

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 few columns: 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 $Ω(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 optimal 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$ (hence tight) for $d=6$. We then settle the asymptotic question: the minimum size is $Θ(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. Finally, we cast the problem as a set cover with connectivity constraints, which yields an exact ILP formulation and a greedy heuristic. With them we find optimal order graphs for $d\le 6$ in the bidirectional and for $d \le 7$ in the unidirectional model, showing that our lower bounds are tight there, and improve the best known order graphs for $d=7$ and $8$.

Closest papers

Nearest neighbours by meaning across the whole index.

Improved bounds for the smallest 4-chromatic graph of girth six

cs.DM math.CO ·2026-08-24 ·Glauco Rampone
theorycode/data similarity 0.64
Abstract · 12 pages, 1 figure. Ancillary files: independent verification scripts, SAT certificates, and a self-contained Lean 4 formal proof. Code and …

For integers $k,g \ge 3$ let $n_g(k)$ denote the minimum order of a graph with chromatic number $k$ and girth at least $g$. Exoo and Goedgebeur (DMTCS 2019) proved $26 \le n_6(4) \le 66$; their 66-vertex witness has remained the smallest known 4-chromatic graph of girth 6. We improve both bounds to $29 \le n_6(4) \le 64$. The upper bound is witnessed by an explicit 4-chromatic graph of girth 6 on 64 vertices with 152 edges; it is vertex- and edge-critical, and its automorphism group is cyclic of order 8 and acts semiregularly. The lower bound is an exhaustive isomorph-free computation in the SAT modulo symmetries framework with co-certificate learning, driven by the Liu-Postle edge-density bound for 4-critical graphs of girth five; it re-derives $n_6(4) \ge 26$ by a disjoint method and is validated on the known values $n_4(4)=11$ and $n_5(4)=21$. We complement the bounds with structural obstructions: no smaller witness arises from either known witness by local modifications; no 4-chromatic Cayley graph of girth 6 exists on 54-63 vertices (for orders 59 and 61 no vertex-transitive witness exists at all); and no witness on at most 63 vertices admits a semiregular automorphism group with two or three vertex orbits, for any finite group. Since every known witness of an $n_g(4)$ record with $g \ge 6$ is a lift of a small base graph along a semiregular action, these results close the most symmetric part of that regime below 64 vertices. All properties of the new graph are verified by independent programs and formally certified in the Lean 4 proof assistant: the non-3-colourability is established inside Lean by a formally verified checker that re-validates a 219,532-node refutation certificate, with a machine-checked soundness theorem.

0.39

Generalized Sorting via Four-Cycles

cs.DS ·2026-11-04 ·Soheil Behnezhad, Shane Ferrante
similarity 0.62
Abstract · 22 pages, 2 figures

We study the generalized sorting problem where only a subset of the pairs can be compared. Equivalently, we are given an $n$-vertex $m$-edge graph $G=(V, E)$ where the vertex set $V$ is to be sorted, and the edge set $E$ indicates possible comparisons. The goal is to sort $V$ with as few (adaptive) queries to $E$ as possible. When $G$ is the complete graph, the problem is equivalent to standard sorting for which $Θ(n \log n)$ queries are sufficient and necessary. All classical sorting algorithms crucially rely on the ability to compare any pair and do not imply an $o(n^2)$-query algorithm in the general case. This was improved 15 years ago by Huang, Kannan, and Khanna [FOCS'11] who achieved a bound of $\widetilde{O}(n\sqrt{n})$. Kuszmaul and Narayanan [FOCS'21] later gave a bound of $\widetilde{O}(\sqrt{m n})$, which is more efficient for sparse graphs, but matches the $\widetilde{O}(n\sqrt{n})$ barrier for dense graphs. In this paper, we present an algorithm for generalized sorting that makes at most $\widetilde{O}(n^{4/3})$ queries, therefore breaking the longstanding $\widetilde{O}(n\sqrt{n})$ barrier for all graphs. The key to our result is to query edges that belong to many (specific types of) four-cycles. We show that querying such edges allows the algorithm to verify the direction of many other edges (specifically, their opposing edges in the four-cycles) and thus achieve a much better amortized query cost.

0.30

A Near-Optimal Generalized Sorting Algorithm

cs.DS ·2026-11-05 ·Sanjeev Khanna, Aaron Putterman, Junkai Song
theory similarity 0.61
Abstract

We continue the study of the classic \emph{generalized sorting problem}, a basic variant of ordinary sorting. There are $n$ elements and an (initially hidden) total ordering $π$ over them. Unlike in ordinary sorting, however, only \emph{some} comparisons are allowed: those given by the edges of an undirected graph $G = (V, E)$ on the elements. How many comparisons are needed to find the total ordering? In ordinary sorting, $Θ(n \log n)$ comparisons are necessary and sufficient. For generalized sorting, however, the best known upper bound has been $\tilde{O}(n^{3/2})$ since the work of Huang, Kannan, and Khanna (FOCS 2011), who even asked whether the problem might in fact require $n^{1+Ω(1)}$ comparisons. We show that it does not: we give a randomized algorithm that uses $O(n \log^4 n)$ comparisons in expectation. Thus, up to logarithmic factors, generalized sorting is no harder than ordinary sorting.

0.05

Near-Optimal Distributed Domination in Planar Graphs

cs.DS cs.DC ·2026-09-26 ·Wojciech Wawrzyniak
theoryhighly cited similarity 0.61
Abstract · 19 pages, 7 figures

We give a deterministic $(8+\varepsilon)$-approximation for minimum dominating set on planar graphs in a constant number of rounds of the LOCAL model, for every $\varepsilon>0$. This improves the previous ratio $11+\varepsilon$ obtained by Heydt et al. The ratio is near-optimal in this model: its leading constant is only one above the known lower bound of $7$. Our result closes three quarters of the previous gap, reducing it from $4$ to $1$. Our main contribution is a sharp structural bound. For any dominating set $D$, assigning each vertex outside $D$ to a neighboring center gives disjoint owner blocks. If $k_x$ counts the other blocks containing a neighbor of $x$, then $\sum_{x\notin D}(k_x-2)^+\le(4|D|-12)^+$, where $z^+=\max\{z,0\}$. The bound holds for every such assignment, and equality holds for arbitrarily large minimum dominating sets. We use this bound in their three-phase framework, with new parameters and the same final linear-programming procedure. The algorithm requires neither a planar embedding nor the graph size, and its round bound depends only on $\varepsilon$. The transfer theorem of Bonamy et al. also gives a deterministic $(25+\varepsilon)$-approximation on graphs of bounded Euler genus, with a round bound depending only on $\varepsilon$ and the genus.

0.36

Lower Bounds for the Distributed Computation of Degeneracy and k-Core

cs.DC ·2026-11-16 ·Lélia Blin, Yan S. Couto, Cristina G. Fernandes, Pierre Fraigniaud, Marcos Kiwi +2 more
theory similarity 0.60
Abstract

The degeneracy of a graph $G$ is the maximum integer $k$ such that $G$ has a non-empty $k$-core, where the $k$-core is the largest induced subgraph with minimum degree $k$. Computing the $k$-core of a graph $G$ is P-complete. In the decentralized setting, the sequential peeling algorithm can be distributed so that the core value of every node, i.e., the largest integer $k$ for which the node belongs to the $k$-core, is computed in $O(n)$ rounds in $n$-node networks, where adjacent nodes exchange only $O(\log n)$ bits at each round, i.e., in the standard CONGEST model. However, while $Ω(D)$ rounds is a trivial lower bound for these problems in networks of diameter $D$, this does not rule out the existence of an algorithm running in $O(D)+o(n)$ rounds in CONGEST, as it is the case for many very important graph problems, including MST. We show that it is unlikely that such an algorithm exists, or, if it does exist, then it requires $\tildeΩ(\sqrt{n})$ rounds. Specifically, our first main result states that, for any $ε>0$, approximating the degeneracy up to a multiplicative factor $2-ε$ requires $\tildeΩ(\sqrt{n})$ rounds in CONGEST even in networks of diameter $O(\log n)$, and still $\tildeΩ(n^{1/3})$ rounds in networks of constant diameter. We also show that improving this lower bound seems challenging, as we demonstrate that the newer frameworks cannot be used as black boxes to obtain a better lower bound for degeneracy. Our second main result provides a better bound, albeit conditional. It states that, unless the well-known circuit value problem (CVP) admits a parallel polynomial speedup -- an outcome considered unlikely -- it holds that, for every $ε>δ>0$, deciding whether a graph is 2-degenerate cannot be solved in $O(D+ n^{1-ε})$ rounds with $O(n^δ)$-time parallel local computation per round at each node.

0.12

An Improved Bound for Smith's Longest Cycles Conjecture via a Forbidden Subdivision

cs.DM math.CO ·2026-08-31 ·Douglas M. Chen
hot direction similarity 0.60
Abstract · 9 pages, 2 figures. Comments welcome!

Smith's conjecture asserts that in every $k$-connected graph with $k\geq 2$, any two longest cycles intersect in at least $k$ vertices. In this work, we establish an $Ω(k^{8/11})$ bound for this conjecture, improving upon the $Ω(k^{2/3})$ bound of Ma and Zhao. Our proof combines a Ramsey theoretic refinement of the traditional Turán-type approach with computer search.

0.50

Clique counts under degree and matching constraints

cs.DM math.CO ·2026-10-31 ·Rajat Adak
theory similarity 0.60
Abstract

We study the maximum number of $t$-cliques in graphs with maximum degree at most $D$ and matching number at most $M$, with no restriction on the number of vertices. For $t\ge 3$, we determine this maximum whenever $D\ge 2M-1$ and characterize all extremal graphs when the maximum is positive. Up to isolated vertices, these are complete or complete split graphs for $D\ge 2M$, while $K_{2M}$ is uniquely extremal when $D=2M-1$. We also derive a general upper bound from the Chvátal-Hanson edge theorem and refine it for even $D$. For fixed even $D$ and $3\le t\le D+1$, every extremal graph consists, apart from isolated vertices, of copies of $K_{D+1}$ together with a remainder whose order is bounded independently of $M$. When $D/2$ divides $M$, this remainder is empty and the extremal graph is unique. This structure yields an eventual recurrence, reducing the determination of all extremal values and graphs to finitely many matching bounds.

0.28

Decomposing Directed Graphs into Partial Orders is Hard

cs.CC ·2026-10-27 ·Grzegorz Gutowski, Dominik Jilg, Antonio Lauerbach, Mikołaj Rams
theory similarity 0.59
Abstract

Comparability graphs represent partial orders and provide natural building blocks for representing a graph as a union of simpler graphs. The analogous task in the directed setting is to represent a digraph as a union of partial orders. Aboulker et al. [arXiv, 2026] recently introduced the partial order decomposition number as a useful structural parameter in their study of tournaments. Formally, a partial order decomposition of a digraph $D$ is a cover of its arc set by transitive acyclic subdigraphs, each representing a strict partial order on the vertex set of $D$. The partial order decomposition number is the minimum number of such subdigraphs needed. We also consider the partitioning variant, in which every arc belongs to exactly one of the partial orders in the decomposition. We prove that, for every fixed $k\geq 2$, deciding whether a digraph admits a decomposition into at most $k$ partial orders is NP-complete, even for directed acyclic graphs (DAGs). For $k=2$, we reduce from NAE-3-SAT. For $k\geq 3$, we reduce from $k$-Coloring, and the reduction yields DAGs with triangle-free underlying graphs. Both reductions establish hardness for both variants. We further show that the minimum cover size and the minimum partition size can differ even on DAGs.

0.25