nLab graphic category

Redirected from "graphic monoid".
Contents

Contents

Idea

A simple class of monoids and categories that permit an effective graphic display via their presheaf categories.

Graphic monoids arise in the study of hyperplane arrangements and are often called left regular band monoids in this context.

Definition

A monoid MM is called graphic if all x,yMx,y\in M satisfy the so called graphic identity xyx=xyx y x=x y . A category 𝒢\mathcal{G} is called graphic if the endomorphism monoid End(x)End(x) is a graphic monoid for each object xx.

Remark

The terminology originates with Lawvere (1989b) where graphic monoids and categories 𝒢\mathcal{G} are demanded to be finite. This restriction is supported by the fact that finitely generated graphic monoids are necessarily finite (see below).

Graphic toposes are defined then as FinSet 𝒢 opFinSet^{\mathcal{G}^{op}} resulting in presheaf categories of finite graph-like ‘displays’ that come with a well-behaved lattice of subtoposes permitting the kind of ‘Hegelian analysis’ that were a primary concern for Lawvere in (Law89b, Law91, Law02).

In particular, the graphic monoid Δ 1\Delta_1 in the example and the eight-element Hegelian taco monoid of (Lawvere 1989b) express diagrammatically configurations of essential subtoposes occuring in Lawvere’s mathematical rendering of basic concepts of Hegel’s dialectic logic.1

This bears some resemblance to the other context, namely hyperplane arrangements, in which such monoids mainly arise.

In the literature that approaches graphic monoids as special class of semigroups, they are called unital left regular bands or left regular band monoids (cf. Brown (2000), Aguiar-Mahajan (2006), Margolis-Saliola-Steinberg (2015)).

Example

The principal example of a graphic category is Δ 1\Delta_1 the three element monoid {δ 1,δ 2,1}\{\delta_1,\delta_2,1\} with δ iδ j=δ i\delta_i\delta_j=\delta_i. The presheaf topos Set Δ 1 opSet^{\Delta_1^{op}} is the topos of reflexive graphs.

To see this, recall that a reflexive graph consists of a set of vertices VV, a set of edges EE, source and target maps s,t:EVs, t : E \to V, and a map i:VEi : V \to E assigning to each vertex an ‘identity edge’ from that vertex to itself, so that s(i(v))=t(i(v))=vs(i(v)) = t(i(v)) = v.

We can describe a reflexive graph without ever mentioning its vertices by using the identity edge i(v)i(v) as a stand-in for vv. To do this, we define operations δ 1,δ 2:EE\delta_1, \delta_2 : E \to E by

δ 1(e)=i(s(e)),δ 2(e)=i(t(e)) \delta_1(e) = i(s(e)), \qquad \delta_2(e) = i(t(e))

and note that

δ 1(δ 1(e))=δ 2(δ 1(e))=δ 1(e) \delta_1(\delta_1(e)) = \delta_2(\delta_1(e)) = \delta_1(e)
δ 1(δ 2(e))=δ 2(δ 2(e))=δ 2(e) \delta_1(\delta_2(e)) = \delta_2(\delta_2(e)) = \delta_2(e)

Thus, the reflexive graph determines a functor F:Δ 1 opSetF : \Delta_1^{op} \to \Set, where we think of the monoid Δ 1\Delta_1 as a one-object category. In other words, it gives a presheaf on Δ 1\Delta_1. Conversely, any presheaf on Δ 1\Delta_1 determines a reflexive graph.

The more familiar two-sorted ‘signature’ for reflexive graphs can be obtained from the Cauchy completion Δ¯ 1\overline\Delta_1 by identifying the isomorphic descendents of δ 1,δ 2\delta_1,\delta_2: the resulting Δ˜ 1\tilde\Delta_1 has two objects and is basically an augmentation with reflexivity data of the familiar diagram VEV\rightrightarrows E that underlies the topos of (“irreflexive”) directed graphs, or quivers. All three of Δ 1,Δ¯ 1,Δ˜ 1\Delta_1,\overline\Delta_1,\tilde\Delta_1 are graphic categories and the resulting presheaf toposes are, of course, equivalent.

Properties

  • Lawvere calls the graphic identity ‘the least common generalization of constant (x=c) and identity (x=1)’ (1989b, p.53). By a constant cc is meant here a cMc\in M such that cy=cc y=c for all yMy\in M. In the context of monoids arising from hyperplane arrangements constants are also called ‘chambers’ (cf. Aguiar-Mahajan 2006).

  • In a graphic monoid every element is idempotent as can be directly seen from the graphic identity with y=1y=1.

  • It follows that a commutative graphic monoid is the same as a semilattice, or equivalently, a commutative monoid where every element is idempotent.

  • More generally, one can define a partial order on MM by xyx\leq y iff xy=yx y=y (’xx is a face of yy‘). In fact, the graphic identity is precisely the condition needed for the anti-symmetry of this relation on monoids whose elements are all idempotent - the reflexivity being a direct consequence of the idempotency.2

  • The free graphic monoid on a set XX is the set of totally ordered finite subsets of XX, where the product of finite subsets SS and TT is the union STS \cup T ordered in such a way that the inclusion SSTS \hookrightarrow S\cup T is order-preserving, the inclusion TSTT \hookrightarrow S\cup T is order-preserving for all elements of TT not in SS, and all the elements of TT not in SS are greater than all elements of SS. This is easy to understand from an example. Consider the free graphic monoid on X={a,b}X = \{a,b\}. This contains:

    1 (corresponding to the empty subset of XX),

    aa (corresponding to the subset {a}\{a\}),

    bb (corresponding to {b}\{b\}),

    aba b (corresponding to {a,b}\{a,b\} ordered so that a<ba \lt b),

    bab a (corresponding to {a,b}\{a,b\} ordered so that b<ab \lt a),

    and nothing else, since for example abb=aba b b = a b and bab=bab a b = b a (since the union of ordered subsets {a,b}{b}={a,b}\{a,b\} \cup \{b\} = \{a, b\} inherits the same ordering that {a,b}\{a,b\} had).

  • In particular, for a finite set of generators the free graphic monoid is finite and consists of all words without repetitions of which there are exactly n! i=0 n1i!n!\sum_{i=0}^n \frac{1}{i!} over an alphabet with nn letters.3

  • The variety (in the sense of universal algebra) of graphic monoids is generated by Δ 1\Delta_1 (cf. Lawvere (1991)).

Graphic monoids as shelves

There is a relation between graphic monoids and shelves:

Theorem

A graphic monoid is the same as a unital left shelf, meaning a set equipped with a binary operation that obeys the left self-distributive law

a(bc)=(ab)(ac) a (b c) = (a b)(a c)

and has an element 11 serving as a left and right unit:

1a=a=a1 1 a = a = a 1
Proof

First start with a unital left shelf. Note that the graphic identity holds:

ab=a(b1)=(ab)(a1)=(ab)a a b = a (b 1) = (a b) (a 1) = (a b) a

and also

ab=a(1b)=(a1)(ab)=a(ab) a b = a (1 b) = (a 1) (a b) = a (a b)

Using these and self-distributivity we can deduce the associative law as follows:

a(bc) =(ab)(ac) =((ab)a)((ab)c) =(ab)((ab)c) =(ab)c\begin{aligned} a (b c) &= (a b) (a c) \\ &= ((a b) a) ((a b) c) \\ &= (a b) ((a b) c) \\ &= (a b) c \end{aligned}

So, we have a graphic monoid.

Conversely, suppose we start with a graphic monoid. Then we can prove the left self-distributive law as follows:

a(bc)=(ab)c=(aba)c=(ab)(ac) a (b c) = (a b) c = (a b a) c = (a b)(a c)

Note in particular that, somewhat surprisingly, the associativity in a unital left shelf comes for free! For more background see the comments on:

References

  • M. Aguiar, S. Mahajan, Coxeter Groups and Hopf Algebras , AMS Providence 2006. (draft)

  • K. S. Brown, Semigroups, Semirings, and Markov Chains , J. Theor. Prob. 13 no.3 (2000) pp.871-938.

  • R. Guitart, Autocategories: II. Autographic algebras , Cah. Top. Géom. Diff. Cat. LV (2014) pp.151-160.

  • N. Kimura, The structure of idempotent semigroups I , Pacific Journal of Mathematics 8 no.2 (1958) pp.257-275. (pdf)

  • F. Klein-Barmen, Über eine weitere Verallgemeinerung des Verbandsbegriffs , Math. Z. 46 (1940) pp.472-480.(gdz)

  • F. W. Lawvere, Qualitative distinctions between some toposes of generalized graphs, Contemp. Math. 92 (1989) pp. 261-299.

  • F. W. Lawvere, Display of graphics and their applications, as exemplified by 2-categories and the Hegelian “taco” Proceedings of the first international conference on algebraic methodology and software technology University of Iowa, May 22-24 1989, Iowa City, pp. 51-74.

  • F. W. Lawvere, More on graphic toposes, Cah. Top. Géom. Diff. Cat. XXXII no. 1 (1991) pp.5-10. (pdf)

  • F. W. Lawvere, Linearization of graphic toposes via Coxeter groups, JPAA 168 (2002) pp. 425-436. (pdf)

  • S. Margolis, F. Saliola, B. Steinberg, Cell Complexes, Poset Topology and the Representation Theory of Algebras Arising in Algebraic Combinatorics and Discrete Geometry , arXiv:1508.05446 (2015). (abstract)

  • M.-P. Schützenberger, Sur certains treillis gauches, C. R. Acad. Sci. Paris 225 (1947) pp.277–278. (pdf)


  1. For more on Lawvere’s approach to Hegelian dialectics see Aufhebung, adjoint cylinder, or Science of Logic.

  2. Semigroup theorists typically order a graphic monoid by xyx\leq y if yx=xy x=x because this is equivalent to xMyMx M\subseteq y M.

  3. The finiteness was basically already observed in Schützenberger (1947). See also Lawvere (1989b).

Last revised on May 21, 2021 at 22:32:28. See the history of this page for a list of all contributions to it.