#17540: Poset.dimension
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers:
combinatorics | Work issues:
Keywords: | Commit:
Authors: | 216d59efca2e03ebce6e9fd76f150abb32e369d5
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/17540 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by ncohen):
> Hmm, why do you need to rebuild the hypergraph? The latter is fixed.
What is not fixed is the number of colours you need, and you don't want to
rebuild the ILP from scratch for this. Why is this poset-specific?
On the paper, the hypergraph is very well defined and you have to compute
its chromatic number. In practice, you cannot build the hypergraph because
the list of its edges is too huge (I would not know how to do that
anyway). So what we do is start with *some* of the edges in the
hypergraph, and find a coloring.
When we have a coloring, we can check that it is valid by building the
corresponding graphs --> if all are acyclic that's fine and we are done.
If one is not acyclic, however, we have found a cycle --> a new set to add
to our hypergraph. And so we re-color this thing again.
This being said, when you find a new set in your hypergraph, you only have
to add one constraint and then you can call `.solve` again. If we called
`.coloring()` each time, we would in fact be building a new LP and solve
it from scratch every time we add a constraint, and that's a waste of
computations that this branch avoids.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17540#comment:12>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
