Macaulay2 » Documentation
Packages » PolyominoIdeals :: PolyominoIdeals
next | previous | forward | backward | up | index | toc

# PolyominoIdeals -- a package to work with collections of cells, polyominoes and associated binomial ideals

## Description

PolyominoIdeals is a package for making several computations with collections of cells, polyominoes and binomial ideals attached to them.
Collections of cells, and in particular polyominoes, are plane figures formed by joining unit squares edge to edge. The systematic study of polyominoes was initiated by Solomon W. Golomb in 1953 and further developed in his seminal monograph [G1994]. Beyond their combinatorial interest in problems such as tiling the plane, polyominoes also connect to several other fields, including theoretical computer science, statistical physics, and discrete geometry.
More recently, since 2012, polyominoes and, more generally, collections of cells have been investigated from an algebraic–combinatorial perspective. In [AAQ2012], Ayesha Asloob Qureshi established a link between combinatorial commutative algebra and collections of cells by associating to each collection the binomial ideal generated by its inner $2$-minors.
Consider the natural partial order on $\NN^2$ and let $a,b \in \N^2$ with $a\leq b$. The set $[a, b] = \{c \in \NN^2 : a \leq c \leq b\}$ is called an interval of $\NN^2$; moreover, if $b=a+(1,1)$, then $[a,b]$ is called a cell of $\NN^2$. An interval $C=[a, b]$, where $a = (i, j)$ and $b = (k, l)$, is said to be a proper interval if $i < k$ and $j < l$. The elements $a, b$ are said the diagonal corners of $C$ and $c = (k, j)$ and $d = (i, l)$ the anti-diagonal ones. If $C$ is a cell, then $V(C)=\{a,a+(1,1),a+(0,1),a+(1,0)\}$ is the set of the corners of $C$.
To a collection of cells $\mathcal{P}$ we associate the ideal $I_{\mathcal{P}}$ as follows. Let $K$ be a field and set $S = K[x_a : a\in V(\mathcal{P})]$, where $V(\mathcal{P})$ is the union of the vertex sets of the cells in $\mathcal{P}$. A proper interval $[a,b]$ is called an inner interval of $\mathcal{P}$ if every cell contained in $[a,b]$ belongs to $\mathcal{P}$. If $c$ and $d$ are the anti-diagonal corners of an inner interval $[a,b]$, then the binomial $f = x_a x_b - x_c x_d$ is called an inner $2$-minor of $\mathcal{P}$. If we restrict the generators to those corresponding only to the cells, we obtain the so-called adjacent $2$-minor ideals, introduced in [HH2012].
A collection $\mathcal{P}$ is a polyomino if for every two cells $A,B\in\mathcal{P}$ there exists a sequence $A=C_1,\dots,C_m=B$ of cells in $\mathcal{P}$ such that $C_i$ and $C_{i+1}$ share a common edge for all $i$. In this case $I_{\mathcal{P}}$ is called the polyomino ideal of $\mathcal{P}$.
The aim of this package is to provide several tools to help mathematicians in the study of collections of cells, polyominoes and the related binomial ideals. Every contribution is very welcome.
Literature

- [G1994] Polyominoes, Puzzles, Patterns, Problems, and Packagings(S.W. Golomb, 1994, Second edition, Princeton University Press).
- [HH2012] Ideals generated by adjacent 2-minors(J. Herzog, T. Hibi, 2012, J. Commut. Algebra).
- [AAQ2012] Ideals generated by 2-minors, collections of cells and stack polyominoes (A. A. Qureshi, 2012, J. Algebra).

### Menu

- CollectionOfCells -- Type representing a collection of cells
- cellCollection -- Create a collection of cells
- polyoVertices -- Vertices of a collection of cells
- polyoMatrix -- Matrix attached to a collection of cells
- polyoMatrixReduced -- Reduced form of the polyomino matrix
- innerInterval -- Inner interval of a collection of cells
- polyoIdeal -- Ideal of inner 2-minors of a collection of cells
- polyoToric -- Toric ideal of a polyomino
- polyoLattice -- Lattice associated with a collection of cells
- adjacent2MinorIdeal -- Ideal generated by adjacent 2-minors
- isNonAttackingRooks -- Check if a rook configuration is non-attacking
- allNonAttackingRookConfigurations -- All non-attacking rook configurations in Q
- rookPolynomial -- Rook polynomial of a collection of cells
- rookNumber -- Rook number of a collection of cells
- equivalenceClassesSwitchingRook -- Equivalence classes of rook configurations under switching
- switchingRookPolynomial -- Switching rook polynomial of a collection of cells
- standardRookNumber -- Standard rook number of a collection of cells
- standardNonAttackingRookConfigurations -- Standard non-attacking rook configurations
- standardRookPolynomial -- Standard rook polynomial of a collection of cells
- isPalindromic -- Check if a polynomial is palindromic
- randomCollectionWithFixedRank -- Random collection of cells with fixed rank
- randomCollectionOfCells -- Random collection of cells up to a given size
- randomPolyominoWithFixedRank -- Random polyomino with fixed rank
- randomPolyomino -- Random polyomino with random size up to a given bound
- cellGraph -- Graph associated with a collection of cells
- collectionIsConnected -- Check if a collection of cells is connected
- connectedComponentsCells -- Connected components of a collection of cells
- isRowConvex -- Row convexity of a collection of cells
- isColumnConvex -- Column convexity of a collection of cells
- isConvex -- Convexity of a collection of cells
- collectionIsSimple -- Simplicity of a collection of cells
- rankCollection -- Rank of a collection of cells
- Field -- optional argument for polyoIdeal and adjacent2MinorIdeal
- TermOrder -- optional argument for polyoIdeal and adjacent2MinorIdeal
- RingChoice -- optional argument for polyoIdeal

## Authors

- Carmelo Cisto <ccisto@unime.it>
- Francesco Navarra <francesco.navarra@sabanciuniv.edu>
- Rizwan Jahangir <rizwan@sabanciuniv.edurizwan.jahangir@nbs.nust.edu.pk>

## Version

This documentation describes version 2.0 of PolyominoIdeals, released November, 2025.

## Citation

If you have used this package in your research, please cite it as follows:

    @misc{PolyominoIdealsSource,
      title = {{PolyominoIdeals: Collections of cells and binomial ideals. Version~2.0}},
      author = {Carmelo Cisto and Francesco Navarra and Rizwan Jahangir},
      howpublished = {A \emph{Macaulay2} package available at
        \url{https://github.com/Macaulay2/M2/tree/stable/M2/Macaulay2/packages}}
    }

## Exports

- Types
  - CollectionOfCells -- Type representing a collection of cells
- Functions and commands
  - adjacent2MinorIdeal -- Ideal generated by adjacent 2-minors
  - allNonAttackingRookConfigurations -- All non-attacking rook configurations in Q
  - cellCollection -- Create a collection of cells
  - cellGraph -- Graph associated with a collection of cells
  - collectionIsConnected -- Check if a collection of cells is connected
  - collectionIsSimple -- Simplicity of a collection of cells
  - connectedComponentsCells -- Connected components of a collection of cells
  - equivalenceClassesSwitchingRook -- Equivalence classes of rook configurations under switching
  - innerInterval -- Inner interval of a collection of cells
  - isColumnConvex -- Column convexity of a collection of cells
  - isConvex -- Convexity of a collection of cells
  - isNonAttackingRooks -- Check if a rook configuration is non-attacking
  - isPalindromic -- Check if a polynomial is palindromic
  - isRowConvex -- Row convexity of a collection of cells
  - polyoIdeal -- Ideal of inner 2-minors of a collection of cells
  - polyoLattice -- Lattice associated with a collection of cells
  - polyoMatrix -- Matrix attached to a collection of cells
  - polyoMatrixReduced -- Reduced form of the polyomino matrix
  - polyoToric -- Toric ideal of a polyomino
  - polyoVertices -- Vertices of a collection of cells
  - randomCollectionOfCells -- Random collection of cells up to a given size
  - randomCollectionWithFixedRank -- Random collection of cells with fixed rank
  - randomPolyomino -- Random polyomino with random size up to a given bound
  - randomPolyominoWithFixedRank -- Random polyomino with fixed rank
  - rankCollection -- Rank of a collection of cells
  - rookNumber -- Rook number of a collection of cells
  - rookPolynomial -- Rook polynomial of a collection of cells
  - standardNonAttackingRookConfigurations -- Standard non-attacking rook configurations
  - standardRookNumber -- Standard rook number of a collection of cells
  - standardRookPolynomial -- Standard rook polynomial of a collection of cells
  - switchingRookPolynomial -- Switching rook polynomial of a collection of cells
- Methods
  - `adjacent2MinorIdeal(CollectionOfCells)` -- see adjacent2MinorIdeal -- Ideal generated by adjacent 2-minors
  - `allNonAttackingRookConfigurations(CollectionOfCells)` -- see allNonAttackingRookConfigurations -- All non-attacking rook configurations in Q
  - `cellCollection(List)` -- see cellCollection -- Create a collection of cells
  - `cellGraph(CollectionOfCells)` -- see cellGraph -- Graph associated with a collection of cells
  - `collectionIsConnected(CollectionOfCells)` -- see collectionIsConnected -- Check if a collection of cells is connected
  - `collectionIsSimple(CollectionOfCells)` -- see collectionIsSimple -- Simplicity of a collection of cells
  - `connectedComponentsCells(CollectionOfCells)` -- see connectedComponentsCells -- Connected components of a collection of cells
  - `equivalenceClassesSwitchingRook(CollectionOfCells)` -- see equivalenceClassesSwitchingRook -- Equivalence classes of rook configurations under switching
  - `innerInterval(List,List,CollectionOfCells)` -- see innerInterval -- Inner interval of a collection of cells
  - `isColumnConvex(CollectionOfCells)` -- see isColumnConvex -- Column convexity of a collection of cells
  - `isConvex(CollectionOfCells)` -- see isConvex -- Convexity of a collection of cells
  - `isNonAttackingRooks(List,List,CollectionOfCells)` -- see isNonAttackingRooks -- Check if a rook configuration is non-attacking
  - `isPalindromic(RingElement)` -- see isPalindromic -- Check if a polynomial is palindromic
  - `isRowConvex(CollectionOfCells)` -- see isRowConvex -- Row convexity of a collection of cells
  - `polyoIdeal(CollectionOfCells)` -- see polyoIdeal -- Ideal of inner 2-minors of a collection of cells
  - `polyoLattice(CollectionOfCells)` -- see polyoLattice -- Lattice associated with a collection of cells
  - `polyoMatrix(CollectionOfCells)` -- see polyoMatrix -- Matrix attached to a collection of cells
  - `polyoMatrixReduced(CollectionOfCells)` -- see polyoMatrixReduced -- Reduced form of the polyomino matrix
  - `polyoToric(CollectionOfCells,List)` -- see polyoToric -- Toric ideal of a polyomino
  - `polyoVertices(CollectionOfCells)` -- see polyoVertices -- Vertices of a collection of cells
  - `randomCollectionOfCells(ZZ)` -- see randomCollectionOfCells -- Random collection of cells up to a given size
  - `randomCollectionWithFixedRank(ZZ)` -- see randomCollectionWithFixedRank -- Random collection of cells with fixed rank
  - `randomPolyomino(ZZ)` -- see randomPolyomino -- Random polyomino with random size up to a given bound
  - `randomPolyominoWithFixedRank(ZZ)` -- see randomPolyominoWithFixedRank -- Random polyomino with fixed rank
  - `rankCollection(CollectionOfCells)` -- see rankCollection -- Rank of a collection of cells
  - `rookNumber(CollectionOfCells)` -- see rookNumber -- Rook number of a collection of cells
  - `rookPolynomial(CollectionOfCells)` -- see rookPolynomial -- Rook polynomial of a collection of cells
  - `standardNonAttackingRookConfigurations(CollectionOfCells)` -- see standardNonAttackingRookConfigurations -- Standard non-attacking rook configurations
  - `standardRookNumber(CollectionOfCells)` -- see standardRookNumber -- Standard rook number of a collection of cells
  - `standardRookPolynomial(CollectionOfCells)` -- see standardRookPolynomial -- Standard rook polynomial of a collection of cells
  - `switchingRookPolynomial(CollectionOfCells)` -- see switchingRookPolynomial -- Switching rook polynomial of a collection of cells
- Symbols
  - Field -- optional argument for polyoIdeal and adjacent2MinorIdeal
  - RingChoice -- optional argument for polyoIdeal
  - TermOrder -- optional argument for polyoIdeal and adjacent2MinorIdeal

## For the programmer

The object PolyominoIdeals is a package, defined in PolyominoIdeals.m2.

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/PolyominoIdeals.m2:1002:0.