Ordered spaces and frames
← Reference index
Sources and background

WB graph frame

Explore this construction
Motivation

This frame was introduced in our studies of pre-local tabularity and local tabularity, seeking a width-bounded locally tabular logic: it is not locally tabular, but all finitely generated algebras of bounded width in its variety are finite. Every finitely generated algebra in this variety is co-Hopfian.

Details of the construction

This frame is constructed layer by layer, employing specific graphs -- so called θ-graphs -- to determine the attachment of points. Specifically, one starts with an almost complete graph G0 with four vertices and 5 edges, and obtains the layer D0.

The elements of the graph G1 consist of the edges of G0. This gives the layer D1, where an edge e∈D1 is below all points which it is not connected to. The graph G1 is a pentagon, with one extra connection between v0 and v2, and we repeat the design of the layer D2. More generally:

Di+1 = E(Gi)
e < v ⇔ v ∉ e,   v ∈ Di
|Di+1| = |Di| + 1

The idea of the construction is to ensure that the width grows unboundedly, whilst the poset remains an ω-upset - every point sees finitely many points, and the downset of each point is cofinite. The construction then adds the compactification point ∞. The conditions for how this is achieved are technical, and depend on some graph-theoretic facts.

How do later graphs gain width?

These publications provide related graph transformations, crown posets, graph-packing methods and Esakia constructions; they do not identify the complete WB progression.

References

  1. Shinya Fujita and Colton Magnant (2011)
    Independence Number and Disjoint Theta Graphs.
    The Electronic Journal of Combinatorics 18(1), P150.
    DOI
  2. G. Indulal and A. Vijayakumar (2008)
    A note on energy of some graphs.
    MATCH Communications in Mathematical and in Computer Chemistry 59(2), 269–274; Definition 2.
    Journal issue
  3. Aiping Deng, Alexander Kelmans, and Juan Meng (2013)
    Laplacian spectra of regular graph transformations.
    Discrete Applied Mathematics 161(1–2), 118–133.
    DOI
  4. Rebecca E. Garcia, Pamela E. Harris, Bethany Kubik, and Shannon Talbott (2019)
    Block circulant graphs and the graphs of critical pairs of crowns.
    Electronic Journal of Graph Theory and Applications 7(2), 207–216.
    DOI
  5. Rebecca E. Garcia and Darrel A. Silva (2014)
    Order Dimension of Layered Generalized Crowns.
    Ars Combinatoria 113-A, 171–186.
    Publisher
  6. Noga Alon (2020)
    Problems and results in Extremal Combinatorics IV.
    Preprint, arXiv:2009.12692; §1, Maintaining high girth in graph packings.
    Preprint
  7. Tapani Hyttinen, Miguel Martins, Tommaso Moraschini, and Davide E. Quadrellaro (2026)
    Strictly n-finite varieties of Heyting algebras.
    The Journal of Symbolic Logic 91(1), 473–488. First published online 29 October 2024; §4 describes the related layered Esakia spaces.
    DOI
  8. Guram Bezhanishvili and Revaz Grigolia (2005)
    Locally finite varieties of Heyting algebras.
    Algebra Universalis 54(4), 465–473. Problem 2.4 asks whether every 2-finite variety of Heyting algebras is locally finite.
    DOI