Peripheral \texorpdfstring{$\Theta$}{Theta}-classes and forbidden partial cube-minors of daisy cubes

Guangfu Wang

arxiv: 2606.19032 · v1 · pith:NNF7BG2Inew · submitted 2026-06-17 · 🧮 math.CO

Peripheral texorpdfstring{Theta}{Theta}-classes and forbidden partial cube-minors of daisy cubes

Guangfu Wang This is my paper

Pith reviewed 2026-06-26 20:23 UTC · model grok-4.3

classification 🧮 math.CO

keywords daisy cubespartial cubesDjoković–Winkler Θ-classesperipheral halfspacesforbidden partial cube minorsCartesian products

0 comments

The pith

A finite partial cube is a daisy cube if and only if every Djoković–Winkler Θ-class is peripheral.

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

The paper proves a characterization of daisy cubes that does not rely on their usual down-set representation in the Boolean lattice. It shows that among finite partial cubes, the daisy cubes are exactly those in which every Θ-class is peripheral. The argument orients each Θ-class toward one of its peripheral halfspaces and verifies that the induced coordinate labels form a down-set. This converts recognition into a structural condition on halfspaces and supplies an exact list of the minimal forbidden partial cube minors.

Core claim

A finite partial cube is a daisy cube if and only if every Djoković–Winkler Θ-class is peripheral. The proof orients each Θ-class toward a peripheral halfspace and shows that the resulting Θ-coordinate labels are closed downward.

What carries the argument

Peripheral Djoković–Winkler Θ-classes, whose orientation toward a peripheral halfspace yields downward-closed coordinate labels.

If this is right

Recognition of daisy cubes reduces to verifying that each Θ-class meets a peripheral halfspace.
The minimal forbidden partial cube-minors are precisely the minimal partial cubes that contain a non-peripheral Θ-class.
For every r ≥ 2 and s ≥ 1 the graph obtained from P₃^□r □ Q_s by deleting two opposite corners is a minimal forbidden partial cube-minor.

Where Pith is reading between the lines

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

The halfspace condition may yield a polynomial-time recognition algorithm if peripheral membership can be checked efficiently.
The same peripheral criterion might serve as a test for membership in other minor-closed families of partial cubes.
The infinite obstruction family suggests that the class of daisy cubes has unbounded tree-width or similar width parameters.

Load-bearing premise

Orienting each Θ-class toward a peripheral halfspace produces Θ-coordinate labels that are closed downward.

What would settle it

A daisy cube containing a non-peripheral Θ-class, or a partial cube in which every Θ-class is peripheral yet the graph is not isomorphic to a down-set in the Boolean lattice.

read the original abstract

Daisy cubes are partial cubes whose vertices can be represented by a down-set of a Boolean lattice. This paper gives a label-free characterization: a finite partial cube is a daisy cube if and only if every Djokovi\'c--Winkler $\Theta$-class is peripheral. The proof orients each $\Theta$-class toward a peripheral halfspace and shows that the resulting $\Theta$-coordinate labels are closed downward. The characterization turns recognition into a condition on the halfspace structure and gives an exact obstruction formulation: the minimal forbidden pc-minors for daisy cubes are precisely the pc-minor-minimal partial cubes containing a non-peripheral $\Theta$-class. We also give an infinite product family of such obstructions. For all $r\ge 2$ and $s\ge 1$, the graph obtained from $P_3^{\square r}\sq Q_s$ by deleting the two opposite corners is a minimal forbidden partial cube-minor for the class of daisy cubes.

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.

Desk Editor's Note private letter to a colleague

The paper gives a usable label-free characterization of finite daisy cubes via peripheral Θ-classes plus one concrete infinite family of forbidden pc-minors.

read the letter

The core contribution is the if-and-only-if statement that a finite partial cube is a daisy cube precisely when every Djoković–Winkler Θ-class is peripheral. The authors derive this by orienting each class toward a peripheral halfspace and verifying that the resulting coordinate labels form a down-set. They also exhibit an explicit infinite family of minimal forbidden partial-cube minors: for r ≥ 2 and s ≥ 1, the graph obtained from P₃^□r □ Q_s by deleting two opposite corners.

This is new relative to earlier descriptions that relied on explicit labelings or down-set representations. The obstruction set is concrete and follows directly once the peripheral condition is granted, which is a practical gain for anyone trying to recognize daisy cubes or test membership in the class.

The argument rests on standard facts about partial cubes and halfspaces, so the orientation step does not look invented. No circular definitions or free parameters appear. The main limitation is that the abstract supplies only the proof outline; the full manuscript would need to be checked to confirm that downward closure holds without hidden case distinctions. That is a normal verification step rather than a fatal gap.

The work is aimed at people already working inside partial-cube theory and isometric subgraph problems. A reader who cares about recognition algorithms or minor-closed classes in this niche will find the obstruction family directly usable. It is narrow enough that it will not reorganize broader graph theory, but the claims are precise and the evidence presented is reproducible in principle.

I would send it to peer review. The characterization is sharp enough to merit referee time even if the write-up needs tightening on the orientation details.

Referee Report

1 major / 0 minor

Summary. The paper claims that a finite partial cube is a daisy cube if and only if every Djoković–Winkler Θ-class is peripheral. The proof orients each Θ-class toward a peripheral halfspace and shows that the resulting Θ-coordinate labels form a down-set. It also gives an exact obstruction formulation: the minimal forbidden pc-minors are the pc-minor-minimal partial cubes containing a non-peripheral Θ-class, and exhibits an infinite family obtained from P_3^{□r} □ Q_s by deleting opposite corners for r≥2, s≥1.

Significance. If the result holds, the label-free characterization converts recognition of daisy cubes into a halfspace condition and supplies an explicit infinite obstruction set. This strengthens the structural theory of partial cubes and isometric subgraphs of hypercubes; the explicit product-family obstructions are a concrete strength.

major comments (1)

[proof sketch (abstract and introduction)] The central step—that orienting each Θ-class toward a peripheral halfspace yields downward-closed Θ-coordinate labels—is asserted in the proof sketch but lacks the explicit derivation or case analysis needed to verify closure under the partial-cube metric. Without this, the if-and-only-if direction cannot be checked for gaps.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for identifying the need for additional detail in the proof sketch. We address the single major comment below.

read point-by-point responses

Referee: [proof sketch (abstract and introduction)] The central step—that orienting each Θ-class toward a peripheral halfspace yields downward-closed Θ-coordinate labels—is asserted in the proof sketch but lacks the explicit derivation or case analysis needed to verify closure under the partial-cube metric. Without this, the if-and-only-if direction cannot be checked for gaps.

Authors: We agree that the sketch in the introduction would benefit from an explicit derivation of downward closure. In the revision we will insert a short paragraph after the orientation step that proceeds as follows: let the Θ-classes be oriented so each points toward its peripheral halfspace; for any vertex w with label vector x and any y ≤ x coordinatewise, the peripheral condition together with the isometric embedding into the hypercube guarantees a shortest path from the all-zero vertex that realizes each successive coordinate flip without leaving the down-set, using the fact that non-peripheral classes would violate the halfspace boundary condition. This case analysis directly confirms the labels form a down-set under the partial-cube metric. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation establishes an if-and-only-if characterization of finite daisy cubes via peripheral Θ-classes using standard properties of partial cubes, Djoković–Winkler relations, and halfspaces. The orientation of each Θ-class toward a peripheral halfspace is asserted from the halfspace structure itself, yielding downward-closed labels that align with the down-set definition without reducing the target property to a fitted parameter, self-definition, or self-citation chain. The explicit infinite family of forbidden pc-minors (P_3^{\square r} \square Q_s minus opposite corners) is constructed directly from the characterization and provides an independent obstruction set. The argument remains self-contained against external graph-theoretic benchmarks with no load-bearing reduction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard background facts about partial cubes and the given definition of daisy cubes; no free parameters, new entities, or ad-hoc axioms are introduced.

axioms (2)

standard math Djoković–Winkler Θ-classes are well-defined equivalence classes on the edges of any partial cube.
Standard definition in the theory of partial cubes.
domain assumption Daisy cubes are exactly the partial cubes whose vertices form a down-set in a Boolean lattice.
This is the definition used throughout the paper.

pith-pipeline@v0.9.1-grok · 5700 in / 1353 out tokens · 32699 ms · 2026-06-26T20:23:01.226841+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

17 extracted references · 10 canonical work pages

[1]

Brezovnik, Z

S. Brezovnik, Z. Che, N. Tratnik, P. Žigert Pleteršek, Resonance graphs of plane bipartite graphs as daisy cubes,Discrete Appl. Math.366 (2025) 75–85.https://doi.org/10.1016/j.dam.2025.01.017

work page doi:10.1016/j.dam.2025.01.017 2025
[2]

Z. Che, Z. Chen, A decomposition structure of resonance graphs that are daisy cubes,Discrete Appl. Math.377 (2025) 529–540.https://doi. org/10.1016/j.dam.2025.08.030. 11

work page doi:10.1016/j.dam.2025.08.030 2025
[3]

Z. Che, N. Tratnik, P. Žigert Pleteršek, Isomorphic daisy cubes based on theirτ-graphs, arXiv preprint arXiv:2603.25662, 2026.https://arxiv. org/abs/2603.25662

arXiv 2026
[4]

Chepoi, K

V. Chepoi, K. Knauer, T. Marc, Hypercellular graphs: partial cubes without Q− 3 as partial cube minor,Discrete Math.343 (2020) 111678. https://doi.org/10.1016/j.disc.2019.111678

work page doi:10.1016/j.disc.2019.111678 2020
[5]

D. Ž. Djoković, Distance preserving subgraphs of hypercubes,J. Com- bin. Theory Ser. B14 (1973) 263–267. https://doi.org/10.1016/ 0095-8956(73)90010-5

1973
[6]

Dravec, A

T. Dravec, A. Taranenko, Daisy Hamming graphs,Discuss. Math. Graph Theory43 (2023) 421–436.https://doi.org/10.7151/dmgt.2373

work page doi:10.7151/dmgt.2373 2023
[7]

Hammack, W

R. Hammack, W. Imrich, S. Klavžar,Handbook of Product Graphs, second ed., CRC Press, Boca Raton, 2011.https://doi.org/10.1201/b10959

work page doi:10.1201/b10959 2011
[8]

Imrich, S

W. Imrich, S. Klavžar,Product Graphs: Structure and Recognition, Wiley, New York, 2000

2000
[9]

Klavžar, Structure of Fibonacci cubes: a survey,J

S. Klavžar, Structure of Fibonacci cubes: a survey,J. Comb. Optim.25 (2013) 505–522.https://doi.org/10.1007/s10878-011-9433-z

work page doi:10.1007/s10878-011-9433-z 2013
[10]

Klavžar, M

S. Klavžar, M. Mollard, Daisy cubes and distance cube polynomial,Eur. J. Combin.80 (2019) 214–223.https://doi.org/10.1016/j.ejc.2018. 02.019

work page doi:10.1016/j.ejc.2018 2019
[11]

Marc,Cycling in Hypercubes, Ph.D

T. Marc,Cycling in Hypercubes, Ph.D. thesis, University of Ljubljana, 2018

2018
[12]

Munarini, C

E. Munarini, C. Perelli Cippo, N. Zagaglia Salvi, On the Lucas cubes,Fi- bonacci Quart.39 (2001) 12–21.https://doi.org/10.1080/00150517. 2001.12428753

work page doi:10.1080/00150517 2001
[13]

Taranenko, Daisy cubes: a characterization and a generalization,Eur

A. Taranenko, Daisy cubes: a characterization and a generalization,Eur. J. Combin.85 (2020) 103058. https://doi.org/10.1016/j.ejc.2019. 103058

work page doi:10.1016/j.ejc.2019 2020
[14]

Vesel, Efficient proper embedding of a daisy cube,Ars Math

A. Vesel, Efficient proper embedding of a daisy cube,Ars Math. Contemp. 21 (2021) 271–282.https://doi.org/10.26493/1855-3974.2454.892. 12

work page doi:10.26493/1855-3974.2454.892 2021
[15]

Winkler, Isometric embedding in products of complete graphs, Discrete Appl

P.M. Winkler, Isometric embedding in products of complete graphs, Discrete Appl. Math.7 (1984) 221–225. https://doi.org/10.1016/ 0166-218X(84)90069-6

1984
[16]

Xie, S.-J

Y.-T. Xie, S.-J. Xu, Characterizing simplex graphs, arXiv preprint arXiv:2503.17160, 2025.https://arxiv.org/abs/2503.17160

arXiv 2025
[17]

Zheng, Y.-T

X. Zheng, Y.-T. Xie, S.-J. Xu, Resolving problems on the polynomial identity characterization of daisy cubes, arXiv preprint arXiv:2603.29577, 2026.https://arxiv.org/abs/2603.29577. 13

arXiv 2026

[1] [1]

Brezovnik, Z

S. Brezovnik, Z. Che, N. Tratnik, P. Žigert Pleteršek, Resonance graphs of plane bipartite graphs as daisy cubes,Discrete Appl. Math.366 (2025) 75–85.https://doi.org/10.1016/j.dam.2025.01.017

work page doi:10.1016/j.dam.2025.01.017 2025

[2] [2]

Z. Che, Z. Chen, A decomposition structure of resonance graphs that are daisy cubes,Discrete Appl. Math.377 (2025) 529–540.https://doi. org/10.1016/j.dam.2025.08.030. 11

work page doi:10.1016/j.dam.2025.08.030 2025

[3] [3]

Z. Che, N. Tratnik, P. Žigert Pleteršek, Isomorphic daisy cubes based on theirτ-graphs, arXiv preprint arXiv:2603.25662, 2026.https://arxiv. org/abs/2603.25662

arXiv 2026

[4] [4]

Chepoi, K

V. Chepoi, K. Knauer, T. Marc, Hypercellular graphs: partial cubes without Q− 3 as partial cube minor,Discrete Math.343 (2020) 111678. https://doi.org/10.1016/j.disc.2019.111678

work page doi:10.1016/j.disc.2019.111678 2020

[5] [5]

D. Ž. Djoković, Distance preserving subgraphs of hypercubes,J. Com- bin. Theory Ser. B14 (1973) 263–267. https://doi.org/10.1016/ 0095-8956(73)90010-5

1973

[6] [6]

Dravec, A

T. Dravec, A. Taranenko, Daisy Hamming graphs,Discuss. Math. Graph Theory43 (2023) 421–436.https://doi.org/10.7151/dmgt.2373

work page doi:10.7151/dmgt.2373 2023

[7] [7]

Hammack, W

R. Hammack, W. Imrich, S. Klavžar,Handbook of Product Graphs, second ed., CRC Press, Boca Raton, 2011.https://doi.org/10.1201/b10959

work page doi:10.1201/b10959 2011

[8] [8]

Imrich, S

W. Imrich, S. Klavžar,Product Graphs: Structure and Recognition, Wiley, New York, 2000

2000

[9] [9]

Klavžar, Structure of Fibonacci cubes: a survey,J

S. Klavžar, Structure of Fibonacci cubes: a survey,J. Comb. Optim.25 (2013) 505–522.https://doi.org/10.1007/s10878-011-9433-z

work page doi:10.1007/s10878-011-9433-z 2013

[10] [10]

Klavžar, M

S. Klavžar, M. Mollard, Daisy cubes and distance cube polynomial,Eur. J. Combin.80 (2019) 214–223.https://doi.org/10.1016/j.ejc.2018. 02.019

work page doi:10.1016/j.ejc.2018 2019

[11] [11]

Marc,Cycling in Hypercubes, Ph.D

T. Marc,Cycling in Hypercubes, Ph.D. thesis, University of Ljubljana, 2018

2018

[12] [12]

Munarini, C

E. Munarini, C. Perelli Cippo, N. Zagaglia Salvi, On the Lucas cubes,Fi- bonacci Quart.39 (2001) 12–21.https://doi.org/10.1080/00150517. 2001.12428753

work page doi:10.1080/00150517 2001

[13] [13]

Taranenko, Daisy cubes: a characterization and a generalization,Eur

A. Taranenko, Daisy cubes: a characterization and a generalization,Eur. J. Combin.85 (2020) 103058. https://doi.org/10.1016/j.ejc.2019. 103058

work page doi:10.1016/j.ejc.2019 2020

[14] [14]

Vesel, Efficient proper embedding of a daisy cube,Ars Math

A. Vesel, Efficient proper embedding of a daisy cube,Ars Math. Contemp. 21 (2021) 271–282.https://doi.org/10.26493/1855-3974.2454.892. 12

work page doi:10.26493/1855-3974.2454.892 2021

[15] [15]

Winkler, Isometric embedding in products of complete graphs, Discrete Appl

P.M. Winkler, Isometric embedding in products of complete graphs, Discrete Appl. Math.7 (1984) 221–225. https://doi.org/10.1016/ 0166-218X(84)90069-6

1984

[16] [16]

Xie, S.-J

Y.-T. Xie, S.-J. Xu, Characterizing simplex graphs, arXiv preprint arXiv:2503.17160, 2025.https://arxiv.org/abs/2503.17160

arXiv 2025

[17] [17]

Zheng, Y.-T

X. Zheng, Y.-T. Xie, S.-J. Xu, Resolving problems on the polynomial identity characterization of daisy cubes, arXiv preprint arXiv:2603.29577, 2026.https://arxiv.org/abs/2603.29577. 13

arXiv 2026