REVIEW 2 major objections 4 minor 1 cited by
Boolean combinations of graphs
T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read Boolean combinations of equivalence graphs exactly capture subexponential, subfactorial, and structurally bounded-degree hereditary graph classes, and these combinations are polynomially χ-bounded in key cases.
desk verdict A genuinely useful framework with a real, repairable proof error in Theorem 4.10; the second flagged concern about Lemma 5.31 is a false alarm. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the boolean function of graphs: for graphs $H_1,\dots,H_k$ on the same vertex set and a propositional formula $f$, the result $G=f(H_1,\dots,H_k)$ has $G(a,b)=f(H_1(a,b),\dots,H_k(a,b))$ for every pair of distinct vertices. The workhorse is the Algebraic Normal Form (Zhegalkin) theorem, which rewrites every such function as an XOR of conjunctions; since the base classes considered are intersection-closed, this reduces arbitrary boolean combinations to XORs of base graphs. Around this reduction the paper organizes a hierarchy of equivalence graphs, graphs whose connected components are cliques, distinguished by how many non-clique components or exceptional vertices they allow, and matches each level to a structural parameter: twin-class size for subexponential speed, twin number for subfactorial speed, near-twins for structural bounded degree, and partition complementation number for general equivalence graphs. The lower-bound examples $H(n,k)$, where adjacency means agreement on an odd number of coordinates, are what force high-degree χ-binding polynomials.
What would settle it
Take a four-vertex graph whose twin class $Q$ has two vertices and whose two exceptional vertices lie in $P_2$, then build $C_U$ exactly as defined in the paper, with $V\setminus U$ a clique and $U$ isolated. The text's construction predicts $P_2$ complete to $Q$ and $Q$ independent, while the definition gives $P_2$ anticomplete to $Q$ and $Q$ a clique; checking these two adjacencies settles whether the first step of the construction can stand.
Extended reading notes
Core claim
On its own terms, the paper claims that the Boolean algebra of graph classes has the following collapse. Hereditary classes grow at subexponential speed exactly when they are bounded boolean functions of the class $\mathcal{L}$, made of complete graphs and graphs consisting of one clique plus one isolated vertex; they grow at subfactorial speed exactly when they are bounded boolean functions of $\mathcal{C}$, made of one clique together with isolated vertices; and they have structurally bounded degree exactly when they are bounded boolean functions of $\mathcal{C}\cup\mathcal{D}_1$, equivalently of some proper hereditary subclass of equivalence graphs. The same framework characterizes functions of $\mathcal{D}_1$ (bounded degree or co-degree), functions of $\mathcal{E}_1$ (bounded number of edges or non-edges), and functions of all equivalence graphs (bounded partition-complementation number). For χ-boundedness, the paper proves that every boolean function of split graphs and every boolean function of permutation graphs admits a polynomial χ-binding function, and it constructs functions of equivalence graphs whose smallest χ-binding function is $\Omega(x^s)$ for each $s$, with linear χ-binding functions for proper subclasses, monotone functions, and bounded unions.
Load-bearing premise
In the proof of Theorem 4.10, the construction of the intermediate graph $G' = C_{P_1} \wedge C_{P_2}$ is said to make $P_2$ complete to the twin class $Q$ and $Q$ independent, but with the paper's definition of $C_U$ the opposite holds: $P_2$ is anticomplete to $Q$ and $Q$ is a clique; the proof of the subexponential characterization depends on that step.
Editorial extensions
If this is right
- Every hereditary class with speed $2^{o(n)}$ is a bounded boolean function of $\mathcal{L}$, so adjacency-labelling schemes, the Erdős–Hajnal property, edge-stability, and bounded VC dimension transfer from $\mathcal{L}$ to the whole class.
- Subfactorial hereditary classes are exactly bounded functions of $\mathcal{C}$, so bounded twin number classes are built from clique-plus-isolated-vertices graphs by a bounded number of boolean operations.
- Every function of split graphs and every function of permutation graphs is polynomially χ-bounded; consequently cographs and equivalence graphs, being permutation graphs, inherit polynomial χ-boundedness.
- For each degree $s$, some function of equivalence graphs has smallest χ-binding function at least $\Omega(x^s)$, so the polynomial bound for equivalence graphs cannot be replaced by a fixed low-degree universal polynomial.
- Functions of proper subclasses of equivalence graphs are linearly χ-bounded, so these classes cannot force superlinear chromatic growth.
Reading between the lines
- Viewing boolean dimension with respect to equivalence graphs as a graph parameter, the hierarchy suggests that this dimension is comparable to the partition complementation number; measuring it could quantify how far a class is from being built from equivalence graphs.
- The equivalence-graph corner of set-defined classes forbids comparisons between different coordinates of the defining tuples, and the polynomial χ-boundedness proved here points to that prohibition as the reason this corner remains χ-bounded.
- The structural characterizations also give uniform adjacency-labelling bounds for the corresponding classes, which is a consequence the paper introduces but does not develop into algorithmic applications.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper initiates a systematic study of Boolean combinations of graphs, where the adjacency of a target graph is obtained by applying a fixed Boolean function to the adjacency indicators of several graphs from a base class. It proves preservation results for speed, adjacency labeling, the Erdős–Hajnal property, edge-stability, neighborhood complexity, and VC dimension, and gives structural characterizations of Boolean functions of several classes of equivalence graphs. In particular, it claims that functions of the class L characterize subexponential hereditary classes, that functions of C characterize subfactorial classes, that functions of C ∪ D1 characterize classes of structurally bounded degree, and it studies χ-boundedness of functions of split graphs, permutation graphs, and equivalence graphs, including polynomial lower bounds and preservation of perfectness for functions of two or three equivalence graphs.
Significance. If the main structural and χ-boundedness results are correct, the paper provides a valuable unifying framework that connects Boolean combinations to known hierarchies of hereditary graph classes and to χ-boundedness. The paper is careful in deriving many results from standard external theorems (ANF, Ramsey theory, Ray–Chaudhuri–Wilson, Gyárfás's theorems, the strong perfect graph theorem), and it explicitly acknowledges model-theoretic connections. The proposed characterizations of subexponential and subfactorial classes as functions of simple equivalence-graph classes are conceptually appealing and would be of independent interest. However, two of the paper's central or highlighted claims are not established as written, which currently limits the reliability of the overall picture.
major comments (2)
- [§4.3.3, Theorem 4.10] The proof of the forward direction contains a concrete error in the construction of G'. With C_U defined as the equivalence graph in which V\U is a clique and U is isolated, the graph G' = C_{P1} ∧ C_{P2} does not have the stated properties: in C_{P1} the set Q ∪ P2 is a clique and P1 is isolated, while in C_{P2} the set Q ∪ P1 is a clique and P2 is isolated. The intersection therefore has Q as a clique and both P1 and P2 anticomplete to Q, which is the opposite of the claim that 'every vertex in P2 is complete to Q, and Q is an independent set'. Moreover, the asserted identity H_{a,b} = C_a ∧ C_b is incorrect: C_a ∧ C_b is K_{n-2} plus two isolated vertices, not the graph with unique edge (a,b). Since this proof underpins Theorem 4.11 and the hierarchy in Figure 1, the characterization of subexponential classes as functions of L is not established by the manuscript as written. The error appears local and likely repairable, but the argument must be corrected.
- [§5.4.3, Lemma 5.31] Lemma 5.31 is false as stated. If Q is the 3-union of the class of perfect graphs, then for every G = G1 ∨ G2 ∨ G3 with each Gi perfect, we have χ(G) ≤ χ(G1) + χ(G2) + χ(G3) = ω(G1) + ω(G2) + ω(G3) ≤ 3ω(G), since each Gi is perfect. Hence the smallest χ-binding function for Q is O(x), not Ω(x²). The proof's algebraic identity is also incorrect: for x=1, y=1, z=0, the left side x⊕y⊕z equals 0, while the right side evaluates to 1. This false lemma should be removed or replaced with a correct statement; it is not used elsewhere in the paper, but its presence as a stated result is misleading.
minor comments (4)
- [§4.3.3, Theorem 4.10] In the converse direction, the sentence 'We will show that every graph in L has a twin class containing all but at most k vertices' should read 'every graph in X', since the subsequent argument considers an arbitrary graph G in X, not in L.
- [§4.3.3, proof of Theorem 4.10] The phrase 'adjacent in G″ if and if they are adjacent in G' contains a typo; it should be 'if and only if'.
- [References] The names 'Micha/suppress l' in [DEM+23] and [GKN+20] appear to be LaTeX artifacts; these should be typeset as 'Michał'.
- [Throughout] The abstract contains minor typographical issues, such as 's tudy' and 'e.g.,' in running text; a careful proofreading pass is recommended.
Circularity Check
No circularity found: the main equivalences are proved by direct constructions plus external, independently established theorems; the Theorem 4.10 proof error is a correctness issue, not a circular dependency.
full rationale
The paper contains no circular derivation. The central equivalences (Theorems 4.10–4.11, 4.16–4.17, 4.20–4.22, and 4.23) are proved by direct Boolean-formula constructions over the relevant base classes and by invoking external, independently established classification theorems: the hereditary speed dichotomies of Scheinerman–Zito, Alekseev, and Balogh–Bollobás–Weinreich; the Gajarský–Hliněný–Obdržálek–Lokshtanov–Ramanujan characterization of structurally bounded degree; and standard combinatorial tools such as Algebraic Normal Form, Ramsey theory, the Ray-Chaudhuri–Wilson theorem, Oddtown theorems, Gyárfás's χ-boundedness results, the Strong Perfect Graph Theorem, and Vizing's theorem. No parameter is fitted to data and then renamed a prediction; no graph class is defined in terms of the class it is claimed to characterize. The self-citations that appear (for example [HZ24], [BDSZ24], [BNdMS22], [BL22a], [BL22b]) are contextual or illustrative and are not load-bearing premises for the main theorems. The proof of Theorem 4.10 does contain a factual error: for G' = C_{P1} ∧ C_{P2}, the set Q is a clique and both P1 and P2 are anticomplete to Q, whereas the proof asserts that Q is independent and P2 is complete to Q. This invalidates the proof as written, but it is a correctness gap in an otherwise direct construction; it does not make the argument circular, because the claimed characterization does not reduce to its own input by definition. Hence the circularity score is 0.
Assumptions & free parameters
assumptions (8)
- standard math Every Boolean function has a unique Algebraic Normal Form as an XOR of conjunctions (Theorem 2.2).
- standard math Meyniel's theorem: graphs in which every odd cycle of length at least five has at least two chords are perfect.
- standard math Strong Perfect Graph Theorem: a graph is perfect if and only if it has no odd holes or odd antiholes.
- standard math Oddtown and Ray-Chaudhuri-Wilson bounds for set systems with restricted intersections.
- domain assumption Gyárfás's results on chi-boundedness of unions of chi-bounded classes and of intersections of comparability graphs.
- domain assumption Classification of structurally bounded degree classes via near-uniform twins, due to Gajarsky, Hlineny, Obdrzalek, Lokshtanov and Ramanujan.
- domain assumption Linear chi-boundedness of classes of structurally bounded expansion.
- domain assumption Alon's lower bound on expressing complement of rK2 as a union of equivalence graphs.
Cite this review
Pith. "Pith review of Boolean combinations of graphs." pith.science (2026). https://pith.science/paper/HAO6J7ZK
@misc{pith2026241219551,
author = {Pith},
title = {Pith review of: Boolean combinations of graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/HAO6J7ZK}},
note = {Machine review of arXiv:2412.19551}
}
abstract
Boolean combinations allow combining given combinatorial objects to obtain new, potentially more complicated, objects. In this paper, we initiate a systematic study of this idea applied to graphs. In order to understand expressive power and limitations of boolean combinations in this context, we investigate how they affect different combinatorial and structural properties of graphs, in particular $\chi$-boundedness, as well as characterize the structure of boolean combinations of graphs from various classes.
Figures
Forward citations
Cited by 1 Pith paper
-
Set-defined graph classes: $\chi$-boundedness meets tropical algebra
Full set-defined classes are polynomially χ-bounded iff they avoid high-chromatic shift graphs, decidable via tropical feasibility dual to mean-payoff games.
Reference graph
Works this paper leans on
-
[5]
On the first-order transduction quasiorder of her editary classes of graphs
[BNdMS22] Samuel Braunfeld, Jaroslav Neˇ setˇ ril, Patrice Ossona de Mendez, and Sebastian Siebertz. On the first-order transduction quasiorder of her editary classes of graphs. arXiv preprint arXiv:2208.14412 ,
-
[9]
Randomized com munication and implicit representations for matrices and graphs of small sign-rank
[HZ24] Nathaniel Harms and Viktor Zamaraev. Randomized com munication and implicit representations for matrices and graphs of small sign-rank. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1810–1833. SIAM,
work page 2024
-
[12]
[NSS23] Tung Nguyen, Alex Scott, and Paul Seymour. Induced s ubgraph density. VI. Bounded VC-dimension. arXiv preprint arXiv:2312.15572 ,
-
[1972]
Cover numbers by certain graph families
[Mar24] M´ arton Marits. Cover numbers by certain graph fami lies. arXiv preprint arXiv:2412.08980,
-
[1979]
45 [EGK+17] Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kre utzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebert z. Neighborhood com- plexity and kernelization for nowhere dense classes of grap hs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 , volume 80 of LIPIcs, pages 63:1–63:14,
work page 2017
-
[1989]
Closure properties for pri- vate classification and online prediction
[ABMS20] Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer . Closure properties for pri- vate classification and online prediction. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020 , volume 125 of Proceedings of Machine Learning Research, pages 119–152. PMLR,
work page 2020
-
[1993]
[NdMP+21] Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pil ipczuk, Roman Rabinovich, and Sebastian Siebertz. Rankwidth meets stability. In D´ aniel Marx, editor, Proceed- ings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SO DA 2021, pages 2014–2033. SIAM,
work page 2021
-
[2006]
First-Order Model Checking on Monadically Stable Graph Classes
[DEM+23] Jan Dreier, Ioannis Eleftheriadis, Nikolas M¨ ahlmann, Rose McCarty, Micha/suppress l Pilipczuk, and Szymon Toru´ nczyk. First-order model checking on monadically stable graph classes. arXiv preprint arXiv:2311.18740 ,
Show all 12 references
-
[2017]
Partitioning perfect graphs into comparability graphs
[GMT24] Andr´ as Gy´ arf´ as, M´ arton Marits, and G´ eza T´ oth. Partitioning perfect graphs into comparability graphs. arXiv preprint arXiv:2408.13523 ,
-
[2020]
Adjacency labeling schemes for small classes
[BDSZ24] ´Edouard Bonnet, Julien Duron, John Sylvester, and Viktor Za maraev. Adjacency labeling schemes for small classes. arXiv preprint arXiv:2409.04821 ,
-
[2022]
Laskowski
[BL22a] Samuel Braunfeld and Michael C. Laskowski. Existen tial characterizations of monadic nip. arXiv preprint arXiv:2209.05120 ,
-
[2024]
Path odd-covers of graphs.arXiv preprint arXiv:2306.06487,
[BBC+23] Steffen Borgwardt, Calum Buchanan, Eric Culver, Bryce Fre derickson, Puck Rom- bach, and Youngho Yoo. Path odd-covers of graphs.arXiv preprint arXiv:2306.06487,
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.