Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 PosetQ

Source Notebook

Determine if a set of coordinates is partially ordered

Contributed by: Ed Pegg Jr

ResourceFunction["PosetQ"][poset]

determines if the coordinates in poset are partially ordered.

Details

A poset is a partially ordered set of integer coordinates.

Examples

Basic Examples (3) 

Test various posets:

In[1]:=
posets = {{{1, 1}, {2, 1}, {3, 1}, {4, 1}, {1, 2}, {2, 2}}, {{1, 1}, {2, 1}, {3, 1}, {1, 2}, {4, 1}, {2, 2}}, {{1, 1}, {2, 1}, {3, 1}, {1, 2}, {2, 2}, {4, 1}}, {{1, 1}, {2, 1}, {1, 2}, {3, 1}, {4, 1}, {2, 2}}, {{1, 1}, {2, 1}, {1, 2}, {3, 1}, {2, 2}, {4, 1}}, {{1, 1}, {2, 1}, {1, 2}, {2, 2}, {3, 1}, {4, 1}}, {{1, 1}, {1, 2}, {2, 1}, {3, 1}, {4, 1}, {2, 2}}, {{1, 1}, {1, 2}, {2, 1}, {3, 1}, {2, 2}, {4, 1}}, {{1, 1}, {1, 2}, {2, 1}, {2, 2}, {3, 1}, {4, 1}}};
In[2]:=
ResourceFunction["PosetQ"] /@ posets
Out[3]=

Test various non-posets:

In[4]:=
ResourceFunction["PosetQ"] /@ Complement[RandomSample[Permutations[posets[[1]]], 10], posets]
Out[4]=

For PosetQ, posets must be comprised of integers:

In[5]:=
ResourceFunction["PosetQ"] /@ N[posets]
Out[5]=

Scope (4) 

For PosetQ, posets represent locations of values in a Young tableau:

In[6]:=
young = ResourceFunction["StandardYoungTableaux"][{3, 2}]; Column[young]
Out[7]=

Here are the corresponding posets:

In[8]:=
poset2 = ResourceFunction["TableauToPoset"] /@ young; Column[poset2]
Out[9]=

Happily, they are identified as posets:

In[10]:=
ResourceFunction["PosetQ"] /@ poset2
Out[10]=

Discounting n! problems, PosetQ can be used to find posets:

In[11]:=
Column[Select[Permutations[{{1, 1}, {2, 1}, {3, 1}, {1, 2}, {2, 2}}], ResourceFunction["PosetQ"]]]
Out[11]=

Possible Issues (2) 

This function does not work with the posets used in HasseDiagram:

In[12]:=
ResourceFunction[ "HasseDiagram"][{{1, 1}, {2, 1}, {1, 2}, {3, 1}, {2, 2}}]
Out[12]=

This is a valid partial ordering, but it is not coordinate based:

In[13]:=
ResourceFunction["HasseDiagram"][SubsetQ, Subsets[{"x", "y", "z"}], VertexShapeFunction -> "Name"]
Out[13]=

Version History

  • 1.0.0 – 28 February 2022

Related Resources

License Information