Combinatorial triangles for posets and fans

This provides several classes and methods to convert between them. Elements of the classes are polynomials in two variables $x$ and $y$, possibly with other parameters. The conversion methods amount to specific invertible rational change-of-variables involving $x$ and $y$.

These polynomial are called triangles because their supports, the sets of exponents where their coefficients can be nonzero, have a triangular shape.

The M-triangle class is motivated by the generating series of Möbius numbers for graded posets. A typical example is:

Sage

sage: W = SymmetricGroup(4)                                                         # needs sage.groups
sage: posets.NoncrossingPartitions(W).M_triangle()                                  # needs sage.graphs sage.groups
M: x^3*y^3 - 6*x^2*y^3 + 6*x^2*y^2 + 10*x*y^3 - 16*x*y^2
- 5*y^3 + 6*x*y + 10*y^2 - 6*y + 1
sage: unicode_art(_)                                                                # needs sage.graphs sage.groups sage.modules
⎛ -5  10  -6   1⎞
⎜ 10 -16   6   0⎟
⎜ -6   6   0   0⎟
⎝  1   0   0   0⎠

Python

>>> from sage.all import *
>>> W = SymmetricGroup(Integer(4))                                                         # needs sage.groups
>>> posets.NoncrossingPartitions(W).M_triangle()                                  # needs sage.graphs sage.groups
M: x^3*y^3 - 6*x^2*y^3 + 6*x^2*y^2 + 10*x*y^3 - 16*x*y^2
- 5*y^3 + 6*x*y + 10*y^2 - 6*y + 1
>>> unicode_art(_)                                                                # needs sage.graphs sage.groups sage.modules
⎛ -5  10  -6   1⎞
⎜ 10 -16   6   0⎟
⎜ -6   6   0   0⎟
⎝  1   0   0   0⎠

The F-triangle class is motivated by the generating series of pure simplicial complexes endowed with a distinguished facet. One can also think about complete fans endowed with a distinguished maximal cone. A typical example is:

Sage

sage: # needs sage.graphs sage.modules
sage: C = ClusterComplex(['A',3])
sage: f = C.greedy_facet()
sage: C.F_triangle(f)
F: 5*x^3 + 5*x^2*y + 3*x*y^2 + y^3 + 10*x^2 + 8*x*y + 3*y^2 + 6*x + 3*y + 1
sage: unicode_art(_)
⎛ 1  0  0  0⎞
⎜ 3  3  0  0⎟
⎜ 3  8  5  0⎟
⎝ 1  6 10  5⎠

Python

>>> from sage.all import *
>>> # needs sage.graphs sage.modules
>>> C = ClusterComplex(['A',Integer(3)])
>>> f = C.greedy_facet()
>>> C.F_triangle(f)
F: 5*x^3 + 5*x^2*y + 3*x*y^2 + y^3 + 10*x^2 + 8*x*y + 3*y^2 + 6*x + 3*y + 1
>>> unicode_art(_)
⎛ 1  0  0  0⎞
⎜ 3  3  0  0⎟
⎜ 3  8  5  0⎟
⎝ 1  6 10  5⎠

The H-triangles are related to the F-triangles by a relationship similar to the classical link between the f-vector and the h-vector of a simplicial complex.

The Gamma-triangles are related to the H-triangles by an analog of the relationship between gamma-vectors and h-vectors of flag simplicial complexes.

class sage.combinat.triangles_FHM.F_triangle(poly, variables=None)

Bases: Triangle

Class for the F-triangles.

h()

Return the associated H-triangle.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import F_triangle
sage: x,y = polygens(ZZ,'x,y')
sage: ft = F_triangle(1+x+y)
sage: ft.h()
H: x*y + 1

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import F_triangle
>>> x,y = polygens(ZZ,'x,y')
>>> ft = F_triangle(Integer(1)+x+y)
>>> ft.h()
H: x*y + 1

m()

Return the associated M-triangle.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygens(ZZ,'x,y')
sage: H_triangle(1+x*y).f()
F: x + y + 1
sage: _.m()
M: x*y - y + 1

sage: H_triangle(x^2*y^2 + 2*x*y + x + 1).f()
F: 2*x^2 + 2*x*y + y^2 + 3*x + 2*y + 1
sage: _.m()
M: x^2*y^2 - 3*x*y^2 + 3*x*y + 2*y^2 - 3*y + 1

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygens(ZZ,'x,y')
>>> H_triangle(Integer(1)+x*y).f()
F: x + y + 1
>>> _.m()
M: x*y - y + 1

>>> H_triangle(x**Integer(2)*y**Integer(2) + Integer(2)*x*y + x + Integer(1)).f()
F: 2*x^2 + 2*x*y + y^2 + 3*x + 2*y + 1
>>> _.m()
M: x^2*y^2 - 3*x*y^2 + 3*x*y + 2*y^2 - 3*y + 1

parabolic()

Return a parabolic version of the F-triangle.

This is obtained by replacing the variable $y$ by $y-1$.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygens(ZZ,'x,y')
sage: H_triangle(1+x*y).f()
F: x + y + 1
sage: _.parabolic()
F: x + y

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygens(ZZ,'x,y')
>>> H_triangle(Integer(1)+x*y).f()
F: x + y + 1
>>> _.parabolic()
F: x + y

vector()

Return the f-vector as a polynomial in one variable.

This is obtained by letting $y=x$.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import F_triangle
sage: x, y = polygen(ZZ,'x,y')
sage: ft = 2*x^2 + 2*x*y + y^2 + 3*x + 2*y + 1
sage: F_triangle(ft).vector()
5*x^2 + 5*x + 1

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import F_triangle
>>> x, y = polygen(ZZ,'x,y')
>>> ft = Integer(2)*x**Integer(2) + Integer(2)*x*y + y**Integer(2) + Integer(3)*x + Integer(2)*y + Integer(1)
>>> F_triangle(ft).vector()
5*x^2 + 5*x + 1

class sage.combinat.triangles_FHM.Gamma_triangle(poly, variables=None)

Bases: Triangle

Class for the Gamma-triangles.

h()

Return the associated H-triangle.

The transition between Gamma-triangles and H-triangles is defined by

$$H(x,y)=(1+x{)}^d\sum _{0\le i;0\le j\le d-2i}{\gamma }_{i,j}{\left(\frac{x}{(1+x{)}^2}\right)}^i{\left(\frac{1+xy}{1+x}\right)}^j$$

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import Gamma_triangle
sage: x, y = polygen(ZZ,'x,y')
sage: g = y**2 + x
sage: Gamma_triangle(g).h()
H: x^2*y^2 + 2*x*y + x + 1

sage: a, b = polygen(ZZ, 'a, b')
sage: x, y = polygens(a.parent(),'x,y')
sage: g = Gamma_triangle(y**3+a*x*y+b*x,(x,y))
sage: hh = g.h()
sage: hh.gamma() == g
True

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import Gamma_triangle
>>> x, y = polygen(ZZ,'x,y')
>>> g = y**Integer(2) + x
>>> Gamma_triangle(g).h()
H: x^2*y^2 + 2*x*y + x + 1

>>> a, b = polygen(ZZ, 'a, b')
>>> x, y = polygens(a.parent(),'x,y')
>>> g = Gamma_triangle(y**Integer(3)+a*x*y+b*x,(x,y))
>>> hh = g.h()
>>> hh.gamma() == g
True

vector()

Return the gamma-vector as a polynomial in one variable.

This is obtained by letting $y=1$.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import Gamma_triangle
sage: x, y = polygen(ZZ,'x,y')
sage: gt = y**2 + x
sage: Gamma_triangle(gt).vector()
x + 1

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import Gamma_triangle
>>> x, y = polygen(ZZ,'x,y')
>>> gt = y**Integer(2) + x
>>> Gamma_triangle(gt).vector()
x + 1

class sage.combinat.triangles_FHM.H_triangle(poly, variables=None)

Bases: Triangle

Class for the H-triangles.

f()

Return the associated F-triangle.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygens(ZZ,'x,y')
sage: H_triangle(1+x*y).f()
F: x + y + 1
sage: H_triangle(x^2*y^2 + 2*x*y + x + 1).f()
F: 2*x^2 + 2*x*y + y^2 + 3*x + 2*y + 1
sage: flo = H_triangle(1+4*x+2*x**2+x*y*(4+8*x)+
....:   x**2*y**2*(6+4*x)+4*(x*y)**3+(x*y)**4).f(); flo
F: 7*x^4 + 12*x^3*y + 10*x^2*y^2 + 4*x*y^3 + y^4 + 20*x^3
+ 28*x^2*y + 16*x*y^2 + 4*y^3 + 20*x^2 + 20*x*y
+ 6*y^2 + 8*x + 4*y + 1
sage: flo(-1-x,-1-y) == flo
True

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygens(ZZ,'x,y')
>>> H_triangle(Integer(1)+x*y).f()
F: x + y + 1
>>> H_triangle(x**Integer(2)*y**Integer(2) + Integer(2)*x*y + x + Integer(1)).f()
F: 2*x^2 + 2*x*y + y^2 + 3*x + 2*y + 1
>>> flo = H_triangle(Integer(1)+Integer(4)*x+Integer(2)*x**Integer(2)+x*y*(Integer(4)+Integer(8)*x)+
...   x**Integer(2)*y**Integer(2)*(Integer(6)+Integer(4)*x)+Integer(4)*(x*y)**Integer(3)+(x*y)**Integer(4)).f(); flo
F: 7*x^4 + 12*x^3*y + 10*x^2*y^2 + 4*x*y^3 + y^4 + 20*x^3
+ 28*x^2*y + 16*x*y^2 + 4*y^3 + 20*x^2 + 20*x*y
+ 6*y^2 + 8*x + 4*y + 1
>>> flo(-Integer(1)-x,-Integer(1)-y) == flo
True

gamma()

Return the associated Gamma-triangle.

In some cases, this is a more condensed way to encode the same amount of information.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygen(ZZ,'x,y')
sage: ht = x**2*y**2 + 2*x*y + x + 1
sage: H_triangle(ht).gamma()
Γ: y^2 + x

sage: W = SymmetricGroup(5)                                                 # needs sage.groups
sage: P = posets.NoncrossingPartitions(W)                                   # needs sage.graphs sage.groups
sage: P.M_triangle().h().gamma()                                            # needs sage.graphs sage.groups
Γ: y^4 + 3*x*y^2 + 2*x^2 + 2*x*y + x

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygen(ZZ,'x,y')
>>> ht = x**Integer(2)*y**Integer(2) + Integer(2)*x*y + x + Integer(1)
>>> H_triangle(ht).gamma()
Γ: y^2 + x

>>> W = SymmetricGroup(Integer(5))                                                 # needs sage.groups
>>> P = posets.NoncrossingPartitions(W)                                   # needs sage.graphs sage.groups
>>> P.M_triangle().h().gamma()                                            # needs sage.graphs sage.groups
Γ: y^4 + 3*x*y^2 + 2*x^2 + 2*x*y + x

m()

Return the associated M-triangle.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import H_triangle
sage: h = polygen(ZZ, 'h')
sage: x, y = polygens(h.parent(),'x,y')
sage: ht = H_triangle(x^2*y^2 + 2*x*y + 2*x*h - 4*x + 1, variables=[x,y])
sage: ht.m()
M: x^2*y^2 + (-2*h + 2)*x*y^2 + (2*h - 2)*x*y
+ (2*h - 3)*y^2 + (-2*h + 2)*y + 1

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> h = polygen(ZZ, 'h')
>>> x, y = polygens(h.parent(),'x,y')
>>> ht = H_triangle(x**Integer(2)*y**Integer(2) + Integer(2)*x*y + Integer(2)*x*h - Integer(4)*x + Integer(1), variables=[x,y])
>>> ht.m()
M: x^2*y^2 + (-2*h + 2)*x*y^2 + (2*h - 2)*x*y
+ (2*h - 3)*y^2 + (-2*h + 2)*y + 1

transpose()

Return the transposed H-triangle.

OUTPUT: another H-triangle

This operation is an involution. When seen as a matrix, it performs a symmetry with respect to the northwest-southeast diagonal.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygens(ZZ,'x,y')
sage: H_triangle(1+x*y).transpose()
H: x*y + 1
sage: H_triangle(x^2*y^2 + 2*x*y + x + 1).transpose()
H: x^2*y^2 + x^2*y + 2*x*y + 1

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygens(ZZ,'x,y')
>>> H_triangle(Integer(1)+x*y).transpose()
H: x*y + 1
>>> H_triangle(x**Integer(2)*y**Integer(2) + Integer(2)*x*y + x + Integer(1)).transpose()
H: x^2*y^2 + x^2*y + 2*x*y + 1

vector()

Return the h-vector as a polynomial in one variable.

This is obtained by letting $y=1$.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygen(ZZ,'x,y')
sage: ht = x**2*y**2 + 2*x*y + x + 1
sage: H_triangle(ht).vector()
x^2 + 3*x + 1

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygen(ZZ,'x,y')
>>> ht = x**Integer(2)*y**Integer(2) + Integer(2)*x*y + x + Integer(1)
>>> H_triangle(ht).vector()
x^2 + 3*x + 1

class sage.combinat.triangles_FHM.M_triangle(poly, variables=None)

Bases: Triangle

Class for the M-triangles.

This is motivated by generating series of Möbius numbers of graded posets.

EXAMPLES:

Sage

sage: x, y = polygens(ZZ, 'x,y')
sage: P = Poset({2: [1]})                                                       # needs sage.graphs
sage: P.M_triangle()                                                            # needs sage.graphs
M: x*y - y + 1

Python

>>> from sage.all import *
>>> x, y = polygens(ZZ, 'x,y')
>>> P = Poset({Integer(2): [Integer(1)]})                                                       # needs sage.graphs
>>> P.M_triangle()                                                            # needs sage.graphs
M: x*y - y + 1

dual()

Return the dual M-triangle.

This is the M-triangle of the dual poset, hence an involution.

When seen as a matrix, this performs a symmetry with respect to the northwest-southeast diagonal.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import  M_triangle
sage: x, y = polygens(ZZ, 'x,y')
sage: mt = M_triangle(x*y - y + 1)
sage: mt.dual() == mt
True

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import  M_triangle
>>> x, y = polygens(ZZ, 'x,y')
>>> mt = M_triangle(x*y - y + Integer(1))
>>> mt.dual() == mt
True

f()

Return the associated F-triangle.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import M_triangle
sage: x, y = polygens(ZZ,'x,y')
sage: M_triangle(1-y+x*y).f()
F: x + y + 1

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import M_triangle
>>> x, y = polygens(ZZ,'x,y')
>>> M_triangle(Integer(1)-y+x*y).f()
F: x + y + 1

h()

Return the associated H-triangle.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import M_triangle
sage: x, y = polygens(ZZ,'x,y')
sage: M_triangle(1-y+x*y).h()
H: x*y + 1

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import M_triangle
>>> x, y = polygens(ZZ,'x,y')
>>> M_triangle(Integer(1)-y+x*y).h()
H: x*y + 1

transmute()

Return the image of self by an involution.

OUTPUT: another M-triangle

The involution is defined by converting to an H-triangle, transposing the matrix, and then converting back to an M-triangle.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import  M_triangle
sage: x, y = polygens(ZZ, 'x,y')
sage: nc3 = x^2*y^2 - 3*x*y^2 + 3*x*y + 2*y^2 - 3*y + 1
sage: m = M_triangle(nc3)
sage: m2 = m.transmute(); m2                                                # needs sage.libs.flint
M: 2*x^2*y^2 - 3*x*y^2 + 2*x*y + y^2 - 2*y + 1
sage: m2.transmute() == m                                                   # needs sage.libs.flint
True

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import  M_triangle
>>> x, y = polygens(ZZ, 'x,y')
>>> nc3 = x**Integer(2)*y**Integer(2) - Integer(3)*x*y**Integer(2) + Integer(3)*x*y + Integer(2)*y**Integer(2) - Integer(3)*y + Integer(1)
>>> m = M_triangle(nc3)
>>> m2 = m.transmute(); m2                                                # needs sage.libs.flint
M: 2*x^2*y^2 - 3*x*y^2 + 2*x*y + y^2 - 2*y + 1
>>> m2.transmute() == m                                                   # needs sage.libs.flint
True

class sage.combinat.triangles_FHM.Triangle(poly, variables=None)

Bases: SageObject

Common class for different kinds of triangles.

This serves as a base class for F-triangles, H-triangles, M-triangles and Gamma-triangles.

The user should use these subclasses directly.

The input is a polynomial in two variables. One can also give a polynomial with more variables and specify two chosen variables.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import Triangle
sage: x, y = polygens(ZZ, 'x,y')
sage: ht = Triangle(1+4*x+2*x*y)
sage: unicode_art(ht)                                                           # needs sage.modules
⎛0 2⎞
⎝1 4⎠

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import Triangle
>>> x, y = polygens(ZZ, 'x,y')
>>> ht = Triangle(Integer(1)+Integer(4)*x+Integer(2)*x*y)
>>> unicode_art(ht)                                                           # needs sage.modules
⎛0 2⎞
⎝1 4⎠

matrix()

Return the associated matrix for display.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygens(ZZ, 'x,y')
sage: h = H_triangle(1+2*x*y)
sage: h.matrix()                                                            # needs sage.modules
[0 2]
[1 0]

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygens(ZZ, 'x,y')
>>> h = H_triangle(Integer(1)+Integer(2)*x*y)
>>> h.matrix()                                                            # needs sage.modules
[0 2]
[1 0]

polynomial()

Return the triangle as a bare polynomial.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygens(ZZ, 'x,y')
sage: h = H_triangle(1+2*x*y)
sage: h.polynomial()
2*x*y + 1

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygens(ZZ, 'x,y')
>>> h = H_triangle(Integer(1)+Integer(2)*x*y)
>>> h.polynomial()
2*x*y + 1

truncate(d)

Return the truncated triangle.

INPUT:

• d – integer

As a polynomial, this means that all monomials with a power of either $x$ or $y$ greater than or equal to d are dismissed.

EXAMPLES:

Sage

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygens(ZZ, 'x,y')
sage: h = H_triangle(1+2*x*y)
sage: h.truncate(2)
H: 2*x*y + 1

Python

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygens(ZZ, 'x,y')
>>> h = H_triangle(Integer(1)+Integer(2)*x*y)
>>> h.truncate(Integer(2))
H: 2*x*y + 1