Chow ring ideals of matroids

AUTHORS:

  • Shriya M

class sage.matroids.chow_ring_ideal.AugmentedChowRingIdeal_atom_free(M, R)[source]

Bases: ChowRingIdeal

The augmented Chow ring ideal for a matroid \(M\) over ring \(R\) in the atom-free presentation.

The augmented Chow ring ideal in the atom-free presentation for a matroid \(M\) is defined as the ideal \(I_{af}(M)\) of the polynomial ring:

\[R[x_{F_1}, \ldots, x_{F_k}],\]

where \(F_1, \ldots, F_k\) are the non-empty flats of \(M\) and \(I_{af}(M)\) is the ideal generated by

  • all quadratic monomials \(x_{F} x_{F'}\) for all incomparable elements \(F\) and \(F'\) in the lattice of flats,

  • for all flats \(F\) and \(i \in E \setminus F\)

    \[x_F \sum_{i \in F'} x_{F'}\]
  • and for all \(i \in E\)

    \[\sum_{i \in F'} (x_{F'})^2.\]

REFERENCES:

INPUT:

  • M – matroid

  • R – commutative ring

EXAMPLES:

Augmented Chow ring ideal of Wheel matroid of rank 3:

sage: ch = matroids.Wheel(3).chow_ring(QQ, True, 'atom-free')
sage: ch.defining_ideal()
Augmented Chow ring ideal of Wheel(3): Regular matroid of rank 3 on 6
elements with 16 bases in the atom-free presentation
>>> from sage.all import *
>>> ch = matroids.Wheel(Integer(3)).chow_ring(QQ, True, 'atom-free')
>>> ch.defining_ideal()
Augmented Chow ring ideal of Wheel(3): Regular matroid of rank 3 on 6
elements with 16 bases in the atom-free presentation
groebner_basis(algorithm='', *args, **kwargs)[source]

Return the Groebner basis of self.

EXAMPLES:

sage: M1 = matroids.Uniform(3,6)
sage: ch = M1.chow_ring(QQ, True, 'atom-free')
sage: ch.defining_ideal().groebner_basis(algorithm='')
Polynomial Sequence with 253 Polynomials in 22 Variables
sage: ch.defining_ideal().groebner_basis(algorithm='').is_groebner()
True
sage: ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series()
True
>>> from sage.all import *
>>> M1 = matroids.Uniform(Integer(3),Integer(6))
>>> ch = M1.chow_ring(QQ, True, 'atom-free')
>>> ch.defining_ideal().groebner_basis(algorithm='')
Polynomial Sequence with 253 Polynomials in 22 Variables
>>> ch.defining_ideal().groebner_basis(algorithm='').is_groebner()
True
>>> ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series()
True
normal_basis(algorithm='', *args, **kwargs)[source]

Return the monomial basis of the quotient ring of this ideal.

EXAMPLES:

sage: ch = Matroid(graphs.CycleGraph(3)).chow_ring(QQ, True, 'atom-free')
sage: I = ch.defining_ideal()
sage: I.normal_basis()
[1, A0, A1, A2, A3, A3^2]
sage: set(I.gens().ideal().normal_basis()) == set(I.normal_basis())
True
sage: ch = matroids.Wheel(3).chow_ring(QQ, True, 'atom-free')
sage: I = ch.defining_ideal()
sage: I.normal_basis()
Polynomial Sequence with 30 Polynomials in 14 Variables
sage: set(I.gens().ideal().normal_basis()) == set(I.normal_basis())
True
>>> from sage.all import *
>>> ch = Matroid(graphs.CycleGraph(Integer(3))).chow_ring(QQ, True, 'atom-free')
>>> I = ch.defining_ideal()
>>> I.normal_basis()
[1, A0, A1, A2, A3, A3^2]
>>> set(I.gens().ideal().normal_basis()) == set(I.normal_basis())
True
>>> ch = matroids.Wheel(Integer(3)).chow_ring(QQ, True, 'atom-free')
>>> I = ch.defining_ideal()
>>> I.normal_basis()
Polynomial Sequence with 30 Polynomials in 14 Variables
>>> set(I.gens().ideal().normal_basis()) == set(I.normal_basis())
True
class sage.matroids.chow_ring_ideal.AugmentedChowRingIdeal_fy(M, R)[source]

Bases: ChowRingIdeal

The augmented Chow ring ideal of matroid \(M\) over ring \(R\) in the Feitchner-Yuzvinsky presentation.

The augmented Chow ring ideal for a matroid \(M\) is defined as the ideal \((I_M + J_M)\) of the following polynomial ring

\[R[y_{e_1}, \ldots, y_{e_n}, x_{F_1}, \ldots, x_{F_k}],\]

where

  • \(F_1, \ldots, F_k\) are the proper flats of \(M\),

  • \(e_1, \ldots, e_n\) are \(n\) elements of groundset of \(M\),

  • \(J_M\) is the ideal generated by all quadratic monomials \(x_{F} x_{F'}\), where \(F\) and \(F'\) are incomparable elements in the lattice of flats and \(y_{i} x_F\) for all flats \(F\) and \(i \in E \setminus F\) and

  • \(I_M\) is the ideal generated by all linear forms

    \[y_i - \sum_{i \notin F} x_F\]

    for all \(i \in E\).

The augmented Chow ring ideal in the Feitchner-Yuzvinsky presentation for a simple matroid \(M\) is defined as the ideal \(I_{FY}(M)\) of the following polynomial ring

\[R[y_{e_1}, \ldots, y_{e_n}, y_{F_1 \cup e}, \ldots, y_{F_k \cup e}],\]

where \(F_1, \ldots, F_k\) are the flats of \(M\), \(e_1, \ldots, e_n\) are \(n\) elements of groundset of \(M\), and \(I_{FY}(M)\) is the ideal generated by

  • all quadratic monomials \(y_{F \cup e} y_{F' \cup e}\), for incomparable elements \(F\) and \(F'\) in the lattice of flats,

  • \(y_{i} y_{F \cup e}\) for all flats \(F\) and all \(i \in E \setminus F\)

  • for all \(i \in E\)

    \[y_i + \sum_{i \in F} y_{F \cup e}\]
  • and

    \[\sum_{F} y_{F \cup e}.\]

Setting \(x_F = y_{F \cup e}\) and using the last linear form to eliminate \(x_E\) recovers the usual presentation of augmented Chow ring of \(M\).

REFERENCES:

INPUT:

  • M – matroid

  • R – commutative ring

EXAMPLES:

Augmented Chow ring ideal of Wheel matroid of rank 3:

sage: ch = matroids.Wheel(3).chow_ring(QQ, True, 'fy')
sage: ch.defining_ideal()
Augmented Chow ring ideal of Wheel(3): Regular matroid of rank 3 on 6
elements with 16 bases of Feitchner-Yuzvinsky presentation
>>> from sage.all import *
>>> ch = matroids.Wheel(Integer(3)).chow_ring(QQ, True, 'fy')
>>> ch.defining_ideal()
Augmented Chow ring ideal of Wheel(3): Regular matroid of rank 3 on 6
elements with 16 bases of Feitchner-Yuzvinsky presentation
groebner_basis(algorithm='', *args, **kwargs)[source]

Return the Groebner basis of self.

EXAMPLES:

sage: ch = matroids.catalog.NonFano().chow_ring(QQ, True, 'fy')
sage: ch.defining_ideal().groebner_basis(algorithm='')
Polynomial Sequence with 178 Polynomials in 25 Variables
sage: ch.defining_ideal().groebner_basis(algorithm='').is_groebner()
True
sage: ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series()
True
>>> from sage.all import *
>>> ch = matroids.catalog.NonFano().chow_ring(QQ, True, 'fy')
>>> ch.defining_ideal().groebner_basis(algorithm='')
Polynomial Sequence with 178 Polynomials in 25 Variables
>>> ch.defining_ideal().groebner_basis(algorithm='').is_groebner()
True
>>> ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series()
True
normal_basis(algorithm='', *args, **kwargs)[source]

Return the monomial basis of the quotient ring of this ideal.

EXAMPLES:

sage: ch = matroids.Uniform(2,5).chow_ring(QQ, True, 'fy')
sage: I = ch.defining_ideal()
sage: I.normal_basis()
[1, B0, B1, B2, B3, B4, B01234, B01234^2]
sage: set(I.gens().ideal().normal_basis()) == set(I.normal_basis())
True
sage: ch = matroids.catalog.Fano().chow_ring(QQ, True, 'fy')
sage: I = ch.defining_ideal()
sage: I.normal_basis()
Polynomial Sequence with 32 Polynomials in 15 Variables
sage: set(I.gens().ideal().normal_basis()) == set(I.normal_basis())
True
>>> from sage.all import *
>>> ch = matroids.Uniform(Integer(2),Integer(5)).chow_ring(QQ, True, 'fy')
>>> I = ch.defining_ideal()
>>> I.normal_basis()
[1, B0, B1, B2, B3, B4, B01234, B01234^2]
>>> set(I.gens().ideal().normal_basis()) == set(I.normal_basis())
True
>>> ch = matroids.catalog.Fano().chow_ring(QQ, True, 'fy')
>>> I = ch.defining_ideal()
>>> I.normal_basis()
Polynomial Sequence with 32 Polynomials in 15 Variables
>>> set(I.gens().ideal().normal_basis()) == set(I.normal_basis())
True
class sage.matroids.chow_ring_ideal.ChowRingIdeal(ring, gens, coerce=True)[source]

Bases: MPolynomialIdeal

matroid()[source]

Return the matroid of the given Chow ring ideal.

EXAMPLES:

sage: ch = matroids.Uniform(3,6).chow_ring(QQ, False)
sage: ch.defining_ideal().matroid()
U(3, 6): Matroid of rank 3 on 6 elements with circuit-closures
{3: {{0, 1, 2, 3, 4, 5}}}
>>> from sage.all import *
>>> ch = matroids.Uniform(Integer(3),Integer(6)).chow_ring(QQ, False)
>>> ch.defining_ideal().matroid()
U(3, 6): Matroid of rank 3 on 6 elements with circuit-closures
{3: {{0, 1, 2, 3, 4, 5}}}
class sage.matroids.chow_ring_ideal.ChowRingIdeal_nonaug(M, R)[source]

Bases: ChowRingIdeal

The Chow ring ideal of a matroid \(M\).

The Chow ring ideal for a matroid \(M\) is defined as the ideal \((I_M + J_M)\) of the polynomial ring

\[R[x_{F_1}, \ldots, x_{F_k}],\]

where

  • \(F_1, \ldots, F_k\) are the non-empty flats of \(M\),

  • \(I_M\) is the Stanley-Reisner ideal, i.e., it is generated by products \(x_{F_1}, \ldots, x_{F_t}\) for subsets \(\{F_1, \ldots, F_t\}\) of flats that are not chains, and

  • \(J_M\) is the ideal generated by all linear forms

    \[\sum_{a \in F} x_F\]

    for all atoms \(a\) in the lattice of flats.

INPUT:

  • M – matroid

  • R – commutative ring

REFERENCES:

EXAMPLES:

Chow ring ideal of uniform matroid of rank 3 on 6 elements:

sage: ch = matroids.Uniform(3,6).chow_ring(QQ, False)
sage: ch.defining_ideal()
Chow ring ideal of U(3, 6): Matroid of rank 3 on 6 elements with
 circuit-closures {3: {{0, 1, 2, 3, 4, 5}}} - non augmented
sage: ch = matroids.catalog.Fano().chow_ring(QQ, False)
sage: ch.defining_ideal()
Chow ring ideal of Fano: Binary matroid of rank 3 on 7 elements,
 type (3, 0) - non augmented
>>> from sage.all import *
>>> ch = matroids.Uniform(Integer(3),Integer(6)).chow_ring(QQ, False)
>>> ch.defining_ideal()
Chow ring ideal of U(3, 6): Matroid of rank 3 on 6 elements with
 circuit-closures {3: {{0, 1, 2, 3, 4, 5}}} - non augmented
>>> ch = matroids.catalog.Fano().chow_ring(QQ, False)
>>> ch.defining_ideal()
Chow ring ideal of Fano: Binary matroid of rank 3 on 7 elements,
 type (3, 0) - non augmented
groebner_basis(algorithm='', *args, **kwargs)[source]

Return a Groebner basis of self.

EXAMPLES:

sage: ch = Matroid(groundset='abc', bases=['ab', 'ac']).chow_ring(QQ, False)
sage: ch.defining_ideal().groebner_basis()
[Aa*Abc, Aa + Aabc, Abc + Aabc, Aa*Aabc, Abc*Aabc, Aabc^2]
sage: ch.defining_ideal().groebner_basis().is_groebner()
True
sage: ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series()
True
>>> from sage.all import *
>>> ch = Matroid(groundset='abc', bases=['ab', 'ac']).chow_ring(QQ, False)
>>> ch.defining_ideal().groebner_basis()
[Aa*Abc, Aa + Aabc, Abc + Aabc, Aa*Aabc, Abc*Aabc, Aabc^2]
>>> ch.defining_ideal().groebner_basis().is_groebner()
True
>>> ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series()
True

Another example would be the Groebner basis of the Chow ring ideal of the matroid of the length 3 cycle graph:

sage: ch = Matroid(graphs.CycleGraph(3)).chow_ring(QQ, False)
sage: ch.defining_ideal().groebner_basis()
[A0*A1, A0*A2, A1*A2, A0 + A3, A1 + A3, A2 + A3, A0*A3, A1*A3, A2*A3, A3^2]
sage: ch.defining_ideal().groebner_basis().is_groebner()
True
sage: ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series()
True
>>> from sage.all import *
>>> ch = Matroid(graphs.CycleGraph(Integer(3))).chow_ring(QQ, False)
>>> ch.defining_ideal().groebner_basis()
[A0*A1, A0*A2, A1*A2, A0 + A3, A1 + A3, A2 + A3, A0*A3, A1*A3, A2*A3, A3^2]
>>> ch.defining_ideal().groebner_basis().is_groebner()
True
>>> ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series()
True
normal_basis(algorithm='', *args, **kwargs)[source]

Return the monomial basis of the quotient ring of this ideal.

EXAMPLES:

sage: ch = matroids.Z(3).chow_ring(QQ, False)
sage: I = ch.defining_ideal()
sage: I.normal_basis()
[1, Ax2x3y1, Ax1x3y2, Ax1x2y3, Ay1y2y3, Atx1y1, Atx2y2, Atx3y3, Atx1x2x3y1y2y3, Atx1x2x3y1y2y3^2]
sage: set(I.gens().ideal().normal_basis()) == set(I.normal_basis())
True
sage: ch = matroids.AG(2,3).chow_ring(QQ, False)
sage: I = ch.defining_ideal()
sage: I.normal_basis()
[1, A012, A236, A046, A156, A345, A247, A057, A137, A258, A678,
A038, A148, A012345678, A012345678^2]
sage: set(I.gens().ideal().normal_basis()) == set(I.normal_basis())
True
>>> from sage.all import *
>>> ch = matroids.Z(Integer(3)).chow_ring(QQ, False)
>>> I = ch.defining_ideal()
>>> I.normal_basis()
[1, Ax2x3y1, Ax1x3y2, Ax1x2y3, Ay1y2y3, Atx1y1, Atx2y2, Atx3y3, Atx1x2x3y1y2y3, Atx1x2x3y1y2y3^2]
>>> set(I.gens().ideal().normal_basis()) == set(I.normal_basis())
True
>>> ch = matroids.AG(Integer(2),Integer(3)).chow_ring(QQ, False)
>>> I = ch.defining_ideal()
>>> I.normal_basis()
[1, A012, A236, A046, A156, A345, A247, A057, A137, A258, A678,
A038, A148, A012345678, A012345678^2]
>>> set(I.gens().ideal().normal_basis()) == set(I.normal_basis())
True