Up-down Posets #19383

kevindilks · 2015-10-09T19:06:54Z

Add additional examples for up-down posets ( https://en.wikipedia.org/wiki/Fence_(mathematics) ).

CC: @jm58660 @fchapoton

Component: combinatorics

Keywords: poset

Author: Kevin Dilks, Jori Mäntysalo

Branch/Commit: 890f5f2

Reviewer: Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/19383

The text was updated successfully, but these errors were encountered:

jm58660 · 2015-10-09T19:22:15Z

comment:1

From another ticket: "Maybe implement up-down posets generally, and then have zigzag_poset(n) as an alias for updown_poset(1,n) ? Zig-zag poset is something that people might be interested in without necessarily knowing the generalized notion of up-down posets."

At least the docstring must mention "zigzag" and "fence" so that they will be found by search. (Compare to my addition about "weak order" etc. to is_incomparable_chain_free.

Also nothing prevents the index to have

UpdownPoset - The poset...
PentagonPoset - 5-element poset...
Zigzag - see (link)UpdownPoset(/link)

kevindilks · 2015-10-09T21:13:07Z

Branch: u/kdilks/updowndimension19383

jm58660 · 2015-10-10T05:34:22Z

comment:3

This was not marked as needs_review, but I'll comment anyway.

Parameter checking is missing. Compare to DiamondPoset. Might be easier to test like if not n in NN or n<....
UpDownPoset(m,n) should be UpDownPoset(m, n).
"fence" should be said in the documentation for googlers.
UpDownPoset has unnecessary empty lines.
Standard example should be explained, i.e. to tell what it is.

Should it be said that for n >= 4 the standard example is only poset with dimension n and n elements? Maybe no. (It is not true for n=3.) Cases n=1 and n=2 are special - should them just be rejected as a parameter?

What is best way to give parameters to UpDownPoset? To give the number of elements or to give the number of minimal elements, or number of maximal elements? I suppose that most users don't want UpDownPoset(50, 6) or similar, where the fence is kind of uncomplete.

Should every function have a facade-argument? Does not bother me, and I'm not going to use non-facade posets, but it is kind on inconsistent that some have it.

New commits:

`b2617ad`	`Initial implementation of updown posets and standard example`

jm58660 · 2015-10-10T05:34:22Z

Commit: b2617ad

nathanncohen · 2015-10-10T06:54:26Z

comment:4

If you want to name a Poset as "StandardPoset", and if it is really known under this name, please provide in the documentation a reference toward a textbook or paper that coins it so.

Also, please make the starting sentence of your docstring short and independent. You can then be as verbose as you want in a second paragraph.

http://doc.sagemath.org/html/en/developer/coding_basics.html#the-docstring-of-a-function-content

Nathann

jm58660 · 2015-10-10T14:30:30Z

comment:5

Replying to @nathanncohen:

If you want to name a Poset as "StandardPoset", and if it is really known under this name, please provide in the documentation a reference toward a textbook or paper that coins it so.

Just google for "poset standard example". It founds this, and only this, poset.

sagetrac-git · 2015-10-10T17:39:14Z

Branch pushed to git repo; I updated commit sha1. New commits:

`4248b4c`	`eliminated extraneous lines and changed a doc string`

sagetrac-git · 2015-10-10T17:39:14Z

Changed commit from b2617ad to 4248b4c

kevindilks · 2015-10-10T17:43:34Z

comment:7

I don't think we should reject n=1,2 for the standard example. Just because they're simple and can more easily be described in other ways doesn't mean the definition doesn't make sense and should raise an error.

Sadly, "standard example" is the accepted terminology. I don't know what the original source would be, but there are tons of papers that use the term, and it's also mentioned on the Wikipedia page for Order-Dimension. Suggestions for what to use?

For UpDownPoset, I just followed the convention that Wikipedia had (although I think I reversed up steps and down steps...there's a reason I didn't mark this for review yet). I don't see any real reason to exclude "kind of incomplete" fences. It just makes the code more complicated, and limits what kind of posets the user can create. Plus I'm not even sure exactly how one would define an "incomplete" fence.

The more I think about it, the more I realize the code should be a little more general to allow more cases. For example, we always start with an up step...but what if we want a fence starting with a down step? What if instead of wanting one down-step after every m up-steps, we want k down-steps after every m up-steps?

I think what I really want is a method where you put in n and a subset D of [n-1], and it creates the poset on where i>i+1 if i in D and i<i+1 otherwise. The motivation being linear extensions of these posets are in bijection with permutations that have descent set D (and the fence example corresponds to alternating permutations). We could still have an UpDownPoset method that does roughly what the code currently does to match what Wikipedia has as the definition of those posets, but it would really just construct an appropriate D based on the input and use the more general method.

Since all of poset examples isn't consistent with including facade options, I'll make another ticket that focuses just on making poset_examples.py consistent.

New commits:

`4248b4c`	`eliminated extraneous lines and changed a doc string`

jm58660 · 2015-10-12T07:03:08Z

comment:8

Replying to @kevindilks:

I don't think we should reject n=1,2 for the standard example. Just because they're simple and can more easily be described in other ways doesn't mean the definition doesn't make sense and should raise an error.

Hmm... OK. How about n=0? I guess that usually the user has made a mistake if he or she ask for Standar example of '2*2' elements. But it is easily seen error.

The more I think about it, the more I realize the code should be a little more general to allow more cases. For example, we always start with an up step...but what if we want a fence starting with a down step? What if instead of wanting one down-step after every m up-steps, we want k down-steps after every m up-steps?

Hmmm number two... Will interface be too complicated? There are tons of different posets that the user could want to get easily. Some of them are trivial to make by hand, like DiamondPoset, other not so easy like TamariLattice. But I wait to see the code.

(I'll be mostly offline for some time. Looking reindeers from kitchen's window...)

sagetrac-git · 2015-10-19T03:57:19Z

Branch pushed to git repo; I updated commit sha1. New commits:

`a73d54f`	`Merge branch 'u/chapoton/18937' of git://trac.sagemath.org/sage into develop`
`958110f`	`Merge branch 'develop' of git://trac.sagemath.org/sage into develop`
`6993f66`	`Merge branch 'u/kdilks/updowndimension19383' of git://trac.sagemath.org/sage into updown19383`
`3cc8e5a`	`Broke into three functions, added to doc`

sagetrac-git · 2015-10-19T03:57:19Z

Changed commit from 4248b4c to 3cc8e5a

kevindilks · 2015-10-19T04:04:17Z

comment:10

Great, now I have git things tomorrow. I think I had the patchbot ticket pulled into develop on this machine.

jm58660 · 2015-10-19T04:08:32Z

comment:11

Computing dimension of StandardExample(6) will take about forever, if the user has no MILP solver. Hence it is not good test, at least without # optional tag.

"Returns" should be "Return" in one-line description.

(Back from Lapland. Reindeers eat bits, as network is slower when there is more reindeers outside. :=))

jm58660 · 2015-11-18T19:49:08Z

comment:12

Just pinging this one... Are you doing this, or should someone (me?) take this to todo list?

jm58660 · 2015-12-11T09:08:47Z

comment:13

I splitted this to #19690, as the branch of this one does not merge.

jm58660 · 2016-04-25T05:54:35Z

Changed branch from u/kdilks/updowndimension19383 to u/jmantysalo/updowndimension19383

sagetrac-git · 2016-04-25T07:11:15Z

Changed commit from 3cc8e5a to a2e7ea3

sagetrac-git · 2016-04-25T07:11:15Z

Branch pushed to git repo; I updated commit sha1. New commits:

`a2e7ea3`	`Some fixes.`

jm58660 · 2016-04-25T07:15:37Z

comment:17

One-line code is from Kevin, I just rephrased docstring and added error detection.

I also turned the order of parameters. IMO it is more logical to have number of elements as a first parameter.

jm58660 · 2016-04-25T07:15:37Z

Author: Kevin Dilks, Jori Mäntysalo

jm58660 · 2016-04-25T07:15:37Z

Changed keywords from none to poset

jm58660 · 2016-05-10T18:42:24Z

comment:18

Frédéric maybe...? This is an easy one.

fchapoton · 2016-05-10T18:53:26Z

comment:19

ok, I take

fchapoton · 2016-05-10T19:04:25Z

Changed branch from u/jmantysalo/updowndimension19383 to public/19383

fchapoton · 2016-05-10T19:04:25Z

comment:20

I have made a small cleanup. If you agree with my changes, you can set a positive review.

And if you could have a look at #20505, that would be great.

New commits:

`0a95c04`	`Merge branch 'u/jmantysalo/updowndimension19383' into 7.2.rc1`
`890f5f2`	`trac 19383 details, pep8`

fchapoton · 2016-05-10T19:04:25Z

Changed commit from a2e7ea3 to 890f5f2

jm58660 · 2016-05-11T06:07:25Z

Reviewer: Frédéric Chapoton

jm58660 · 2016-05-11T06:07:25Z

comment:21

Replying to @fchapoton:

I have made a small cleanup. If you agree with my changes, you can set a positive review.

Thanks!

vbraun · 2016-05-17T07:16:36Z

Changed branch from public/19383 to 890f5f2

kevindilks mannequin added this to the sage-6.9 milestone Oct 9, 2015

kevindilks mannequin added c: combinatorics labels Oct 9, 2015

jm58660 mannequin modified the milestones: sage-6.9, sage-6.10 Oct 9, 2015

This comment has been minimized.

Sign in to view

jm58660 mannequin modified the milestones: sage-6.10, sage-7.0 Dec 11, 2015

jm58660 mannequin modified the milestones: sage-7.0, sage-7.1 Jan 24, 2016

jm58660 mannequin changed the title ~~Up-down Posets, and Dimenson Poset~~ Up-down Posets Jan 24, 2016

jm58660 mannequin added the s: needs review label Apr 25, 2016

jm58660 mannequin modified the milestones: sage-7.1, sage-7.2 Apr 25, 2016

jm58660 mannequin added s: positive review and removed s: needs review labels May 11, 2016

vbraun removed the s: positive review label May 17, 2016

vbraun closed this as completed in 73b55e1 May 17, 2016

jm58660 mannequin mentioned this issue Jan 28, 2016

Add "Standard example" poset #19690

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Up-down Posets #19383

Up-down Posets #19383

kevindilks mannequin commented Oct 9, 2015

jm58660 mannequin commented Oct 9, 2015

kevindilks mannequin commented Oct 9, 2015

jm58660 mannequin commented Oct 10, 2015

jm58660 mannequin commented Oct 10, 2015

nathanncohen mannequin commented Oct 10, 2015

jm58660 mannequin commented Oct 10, 2015

sagetrac-git mannequin commented Oct 10, 2015

sagetrac-git mannequin commented Oct 10, 2015

kevindilks mannequin commented Oct 10, 2015

jm58660 mannequin commented Oct 12, 2015

sagetrac-git mannequin commented Oct 19, 2015

sagetrac-git mannequin commented Oct 19, 2015

kevindilks mannequin commented Oct 19, 2015

jm58660 mannequin commented Oct 19, 2015

jm58660 mannequin commented Nov 18, 2015

This comment has been minimized.

jm58660 mannequin commented Dec 11, 2015

jm58660 mannequin commented Apr 25, 2016

sagetrac-git mannequin commented Apr 25, 2016

sagetrac-git mannequin commented Apr 25, 2016

jm58660 mannequin commented Apr 25, 2016

jm58660 mannequin commented Apr 25, 2016

jm58660 mannequin commented Apr 25, 2016

jm58660 mannequin commented May 10, 2016

fchapoton commented May 10, 2016

fchapoton commented May 10, 2016

fchapoton commented May 10, 2016

fchapoton commented May 10, 2016

jm58660 mannequin commented May 11, 2016

jm58660 mannequin commented May 11, 2016

vbraun commented May 17, 2016

Up-down Posets #19383

Up-down Posets #19383

Comments

kevindilks mannequin commented Oct 9, 2015

jm58660 mannequin commented Oct 9, 2015

kevindilks mannequin commented Oct 9, 2015

jm58660 mannequin commented Oct 10, 2015

jm58660 mannequin commented Oct 10, 2015

nathanncohen mannequin commented Oct 10, 2015

jm58660 mannequin commented Oct 10, 2015

sagetrac-git mannequin commented Oct 10, 2015

sagetrac-git mannequin commented Oct 10, 2015

kevindilks mannequin commented Oct 10, 2015

jm58660 mannequin commented Oct 12, 2015

sagetrac-git mannequin commented Oct 19, 2015

sagetrac-git mannequin commented Oct 19, 2015

kevindilks mannequin commented Oct 19, 2015

jm58660 mannequin commented Oct 19, 2015

jm58660 mannequin commented Nov 18, 2015

This comment has been minimized.

jm58660 mannequin commented Dec 11, 2015

jm58660 mannequin commented Apr 25, 2016

sagetrac-git mannequin commented Apr 25, 2016

sagetrac-git mannequin commented Apr 25, 2016

jm58660 mannequin commented Apr 25, 2016

jm58660 mannequin commented Apr 25, 2016

jm58660 mannequin commented Apr 25, 2016

jm58660 mannequin commented May 10, 2016

fchapoton commented May 10, 2016

fchapoton commented May 10, 2016

fchapoton commented May 10, 2016

fchapoton commented May 10, 2016

jm58660 mannequin commented May 11, 2016

jm58660 mannequin commented May 11, 2016

vbraun commented May 17, 2016