#7301: Gale Ryser theorem
-----------------------------+----------------------------------------------
Reporter: ncohen | Owner: mhansen
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.3.1
Component: combinatorics | Keywords:
Work_issues: | Author:
Upstream: N/A | Reviewer:
Merged: |
-----------------------------+----------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
> Python has a mechanism for "private" functions like slider01, so
> I renamed it _slider01. I think that is better than hiding it inside
> gale_ryser_theorem. Is that okay?
Well, do you think slider01 could be used by ither methods ?
> I think this will not work, if you want to allow trailing 0's.
> Maybe I am missing something?
The Gale-Ryser theorem tells you that given two partitions, there is a
matrix satisfying the constraints if and only if the domination criterion
is checked. Well, the point you made about trailing 0's is that you do not
necessarily want the column's sums in your final matrix to be *sorted in
decreasing order*. When you have a binary matrix, though, you can modify
it by inverting two columns without changin the rows sums, and the columns
sum still have the same set of sums. So instead of just taking care of
trailing 0, the best may be to take care of non-sorted sequences, which is
the general case of the theorem.
> I was told that by my colleague which is much much more of an expert on
> this stuff. I have not read Gale's paper and don't know of an electronic
version.
Then the best is to :
* Cite the reference to justify the names Gale's method and Ryser's
method
* Alternatively, use algorithm="LP" instead of Gale, as we can not say
more without references ( plus it gives some enlightenment as to the
algorithm used and the complexity )
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7301#comment:31>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
