isProper(SimplicialComplex) -- whether an abstract simplicial complex is properly colored

Synopsis

Function: isProper
Usage:

isProper Delta
Inputs:
- Delta, an abstract simplicial complex,
Outputs:
- a Boolean value, that is true if the multigrading on its ambient ring determines a proper coloring

Description

A coloring of an abstract simplicial complex $\Delta$ is a labelling of its vertices with colors. A proper coloring of a simplicial complex $\Delta$ is a labelling of the vertices with colors such that no two vertices in the same face are the same color. In this package, a coloring of an abstract simplicial complex is determined by a multigrading of its ambient ring. This method determines whether a multigrading on the ambient ring defines a proper coloring of the abstract simplicial complex.

Giving the three vertices is the $2$-simplex distinct colors, each color set corresponds to a unique face.

i1 : S = QQ[a, b, c, DegreeRank => 3];

i2 : Δ = simplexComplex(2, S)

o2 = simplicialComplex | abc |

o2 : SimplicialComplex

i3 : isProper Δ

o3 = true

i4 : assert isProper Δ

Two vertices of $\Delta$ have the same color when the corresponding variables have the same multidegree.

i5 : Δ1 = sub(Δ, newRing(ring Δ, Degrees => {{1,0,0},{1,0,0},{0,0,1}}));

i6 : isProper Δ1

o6 = false

i7 : assert not isProper Δ1

i8 : flagfVector({1,0,0}, Δ1)

o8 = 2

Two vertices have distinct colors when the multidegrees of the corresponding variables are linearly independent.

i9 : Δ2 = sub(Δ, newRing(ring Δ, Degrees => {{1,0,0},{0,1,0},{0,2,1}}));

i10 : isProper Δ2

o10 = true

i11 : assert isProper Δ2

i12 : Δ3 = sub(Δ, newRing(ring Δ, Degrees => {{1,0,0},{0,1,0},{1,1,0}}));

i13 : isProper Δ3

o13 = false

i14 : assert not isProper Δ3

Caveat

Not every grading of the ambient polynomial ring corresponds to a coloring.

Ways to use this method: