The dimension of a Poset: do you know how to compute that ?

[Nathann Cohen]

Helloooooo everybody !

I wondered how one could compute the dimension of a poset, i.e. a smallest set of linear extension whose interection is the poset.

It is apparently known for being NP-Hard, but that never stopped us in the past. Plus I am curious to learn how this could be done. We need some code for that !

Tell me if you have any idea, please !

Thanks,

Nathann

[mmarco]

I didn't hear about that problem before, but I could try to give it some thinking. Do you have any reference to start with?

[mmarco]

[Nathann Cohen]

HelloooooOO !

> I didn't hear about that problem before, but I could try to give it some thinking. Do you have any reference to start with?

The wikipedia page contains some, including a pointer toward the
result of NP-Hardness:
http://en.wikipedia.org/wiki/Order_dimension

It appears from time to time in graph theory because of Schnyder's
characterization of planar graphs:
http://en.wikipedia.org/wiki/Schnyder's_theorem

I personally do not intend to use it for anything. Just being curious :-)

Nathann

[Jori Mantysalo]

On Mon, 22 Dec 2014, Nathann Cohen wrote:

> I wondered how one could compute the dimension of a poset, i.e. a smallest set of
> linear extension whose interection is the poset.
>
> It is apparently known for being NP-Hard, but that never stopped us in the past.
> Plus I am curious to learn how this could be done. We need some code for that !
>
> Tell me if you have any idea, please !

No ideas.

Should we made *something* for questions like this? As an another example,
there is no known easy way to compute Frattini sublattice, i.e.
intersection of all proper sublattices of a given lattice.

Should we just make a function with note "This is direct computation with
no optimization at all."? Being able to compute some examples it might be
easier to try other algorithms, find some corner cases etc.

--
Jori Mäntysalo

[Nathann Cohen]

> Should we made *something* for questions like this?

I don't see what exactly we could do except thinking of an algorithm O_o

> Should we just make a function with note "This is direct computation with no
> optimization at all."? Being able to compute some examples it might be
> easier to try other algorithms, find some corner cases etc.

Well the only way I know to do this computation is to enumerate all
linear extensions, and it seems to be a very bad idea :-P

Nathann

[Dima Pasechnik]

it is known that this dimension is equivalent to the chromatic number of
certain hypergraph (hypergraph of incompatible pairs):
http://www.ams.org/mathscinet-getitem?mr=1796000

Does Sage do colouring of hypergraphs (this is probably some dumb ILP
way to formulate this)?

Dima

>
> Nathann
>

[Nathann Cohen]

> it is known that this dimension is equivalent to the chromatic number of
> certain hypergraph (hypergraph of incompatible pairs):
> http://www.ams.org/mathscinet-getitem?mr=1796000

Ohhhhhhh cool ! I'll do that, thanks :-)

> Does Sage do colouring of hypergraphs (this is probably some dumb ILP
> way to formulate this)?

Yeah, it will probably be a 'dumb ILP' again. Trying to be smart
probably wouldn't pay in that case.

Nathann

[Thierry]

Hi,

it seems there is an algorithm based on graph colouring (about what Sage
knows a bit already), you can have a look at
http://www.sciencedirect.com/science/article/pii/S0196677498909749 (i
succeeded to download the pdf so email me if you need it)

Ciao,
Thierry

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

[Thierry]

Hi,

On Mon, Dec 22, 2014 at 12:00:09PM +0200, Jori Mantysalo wrote:
> Should we made *something* for questions like this? As an another
> example, there is no known easy way to compute Frattini sublattice,
> i.e. intersection of all proper sublattices of a given lattice.
>
> Should we just make a function with note "This is direct computation
> with no optimization at all."? Being able to compute some examples
> it might be easier to try other algorithms, find some corner cases
> etc.

I think it is a good idea to have such straightforward algorithms for
which no better algorithm is known (after some bibliography checking):

- it provides a comparison point for further computational research.

- it is easier for someone not involved in Sage development to say "i
know a better way than your dumb code" than "this functionality does
not exist, it is perhaps useful to someone else, i know some way, but
i am not sure it is the most efficient, let me still propose it so that
perhaps someone will find a better way".

- it is also technically useful since it puts the structure within Sage's
source code (the right method within the right class with doctest
structure and so on), making easier for some researcher to implement
her own algoritmh, without to think about Sage stuff, it suffices to
add one possibility for the 'algorithm=...' keyword and drop the new code
under the existing one.

Beyond MILP generic way of solving things, a possibility could be to have
a CSP solver (which is more expressive than MILP) such as
http://numberjack.ucc.ie/ (whose interface is written in Python, throught
somme better tools may exist) within Sage, so that it is easy to implement
methods for problems that do not have specific algorithms in the
litterature.

Ciao,
Thierry

[Vincent Delecroix]

2014-12-22 19:09 UTC+01:00, Thierry <sage-goo...@lma.metelu.net>:

> Beyond MILP generic way of solving things, a possibility could be to have
> a CSP solver (which is more expressive than MILP) such as
> http://numberjack.ucc.ie/ (whose interface is written in Python, throught
> somme better tools may exist) within Sage, so that it is easy to implement
> methods for problems that do not have specific algorithms in the
> litterature.

The following worked for me:

$ sage -pip install Numberjack

Vincent

[Nathann Cohen]

Yoooooooo again,

> it is known that this dimension is equivalent to the chromatic number of
> certain hypergraph (hypergraph of incompatible pairs):
> http://www.ams.org/mathscinet-getitem?mr=1796000

HMmmm... I am not sure I get the definition of this hypergraph
completely, but I am not sure either that I know how to build it. Its
edges do not seem very straightforward to list :-/

Nathann

[Nathann Cohen]

> HMmmm... I am not sure I get the definition of this hypergraph
> completely, but I am not sure either that I know how to build it. Its
> edges do not seem very straightforward to list :-/

My mistake. It is doable, and quite doable. And it will be done soon,
possibly today.

Nathann

[Nathann Cohen]

I have been working on this for several hours now. So far I have
proved that C4 is not planar, that Schyder's theorem is wrong, or that
my code contains a bug.

Nathann

[Nathann Cohen]

Wellllllllllllllllllllllll.

Here is yet another thing that we can do in Sage: compute the dimension of a Poset (even if it takes... "some time" :-P)

http://trac.sagemath.org/ticket/17540

By the way, while implementing/debugging I thought "God, my job would be easier if I had some other software to check the results". Doesn't seem to exist anywhere else but on paper :-P

Nooowwwwwww need a review ;-)

Nathann

P.S. : Thanks again Dima for the pointer !