[sage-combinat-devel] How to solve this combinatorial problem in Sage?
Hi! I am sure that the following combinatorial problem is well-known, but I am not a combinatorialist, and hence I thought it is best to ask here how to solve it with Sage. I have a finite set X and a set S of subsets of X. I'd like to get a list (or better: an iterator) of all subsets U of S (i.e., subsets of subsets) such that the union of the elements of U is equal to X. Ideally, I'd like that the number of intersection points (counted with multiplicity) of elements of U is ascending. Hence, if there is a disjoint cover of X by elements of S, then I'd like to get this first, and otherwise I'd like to first get a cover that is as close to being disjoint as possible. How to achieve it? Best regards, Simon -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-combinat-devel] Re: How to solve this combinatorial problem in Sage?
Hi, On 2013-04-15, Simon King simon.k...@uni-jena.de wrote: I have a finite set X and a set S of subsets of X. I'd like to get a list (or better: an iterator) of all subsets U of S (i.e., subsets of subsets) such that the union of the elements of U is equal to X. Ideally, I'd like that the number of intersection points (counted with multiplicity) of elements of U is ascending. Hence, if there is a disjoint cover of X by elements of S, then I'd like to get this first, and otherwise I'd like to first get a cover that is as close to being disjoint as possible. I have found that one can get disjoint (exact) covers via dancing links. But let me formulate a related problem that I'd even more like to solve: Given a matrix M over some finite field F, I need a linear combination of rows of M such that the resulting row has all coefficients non-zero (in F). Preferably, the set of rows to be combined should be small, but it is not needed that it is minimal. How can this be done? Best regards, Simon -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-combinat-devel] Re: How to solve this combinatorial problem in Sage?
Hi Simon how big is M, how big is F, and is M sparse or do you have few zeros? Kind regards Gary On Monday, April 15, 2013 1:17:14 PM UTC+2, Simon King wrote: Hi, On 2013-04-15, Simon King simon...@uni-jena.de javascript: wrote: I have a finite set X and a set S of subsets of X. I'd like to get a list (or better: an iterator) of all subsets U of S (i.e., subsets of subsets) such that the union of the elements of U is equal to X. Ideally, I'd like that the number of intersection points (counted with multiplicity) of elements of U is ascending. Hence, if there is a disjoint cover of X by elements of S, then I'd like to get this first, and otherwise I'd like to first get a cover that is as close to being disjoint as possible. I have found that one can get disjoint (exact) covers via dancing links. But let me formulate a related problem that I'd even more like to solve: Given a matrix M over some finite field F, I need a linear combination of rows of M such that the resulting row has all coefficients non-zero (in F). Preferably, the set of rows to be combined should be small, but it is not needed that it is minimal. How can this be done? Best regards, Simon -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-combinat-devel] Re: How to solve this combinatorial problem in Sage?
Hi Gary,
On 2013-04-15, garymako...@googlemail.com garymako...@googlemail.com wrote:
how big is M, how big is F, and is M sparse or do you have few zeros?
F is typically a small prime field, M is not sparse, but also not
particularly big, say, 200x100.
However, it turns out that after all I was mistaken: In contrast to what
I thought, the problem of enumerating covers starting with as few overlaps
as possible is more important for me than the problem with nowhere-zero row
combinations.
As you probably guessed, both problems are just attempts to solve
something else. So, perhaps it makes sense to formulate my *real*
problem:
I am computing the mod-p cohomology ring R of a finite group G. It is known
that the Krull dimension of the cohomology ring is equal to the p-rank r
of G. Now, I have given elements p_1,..., p_{r-1}, and I try to find an
element p_r of degree d such that p_1,..., p_r generate a sub-algebra
over which R is finite, i.e., p_1,...,p_r are parameters for R (Let's
call the problem: find a last parameter in degree d).
What I am looking for is a good heuristics, i.e., I would accept that
sometimes the algorithm can't find a last parameter in degree d even
though it exists.
R comes with a couple of maps f_1,...,f_k whose codomains are finite over a
polynomial ring (namely: the restriction maps to maximal p-elementary
abelian subgroups). It is known that p_1,...,p_r are parameters for R if
and only if their images under f_i forms a 0-dimensional ideal, simultaneously
for all i=1,...,k.
The brute force approach would be: Let S a basis of the degree-d part of
R (lets call them standard monomials). One can list all linear
combinations of the elements of S, and by applying the f_i one can test
whether the linear combination is a last parameter. Since S can easily
contain more than 40 elements, a cleverer approach seems needed.
For each element m of S, we can test for which i=1,...,k the images of
p_1,...,p_{r-1} together with the image of m span a zero-dimensional
ideal (let's say that m is fine at i). If two elements m, m' are both
fine at i, it could be that a linear combination of m and m' is not fine
at i. But if we find a subset of S such that for all i=1,...,k there is
exactly one element of the subset that is fine at i, then the sum of
elements of this subset yields a last parameter.
So, this should explain my interest in finding covers. If the cover has
some overlap (i.e., for some i there are several elements fine at i),
then the corresponding sum of elements of S is not guaranteed to provide
a parameter, but I would expect that with small overlap it is still rather
likely to find a last parameter.
For the other problem: I tried to construct a matrix over GF(p) whose
rows correspond to the elements of S and somehow encode the images under
the f_1,...,f_k. This idea was to do it in such a way that having a
linear combination of rows that has no zero entry is a necessary but
perhaps not sufficient condition that the corresponding linear
combination of elements of S is a last parameter. But the construction I
had in mind did not work.
Best regards,
Simon
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-combinat-devel] Re: How to solve this combinatorial problem in Sage?
Hi Simon
I'm struggling a little to understand what the programming bottleneck is in
all this. Clearly you do not want a completely naive search as you said
above; but are the 'tests' of the f_i on each m expensive in time, and is
the proof of the zero-dimensionality of the ideal also a slow process (ie I
assume you have to proceed via Groebner bases over the poly ring in some
number t of indeterminates over F_p right?) ? ie I guess what I'm getting
at is, how much (and where in the algorithm) are we able to get away with
'brute force', and where do we have to be clever? :)
Because to be honest the best solution that occurs to me from what you have
said so far is exactly what you tried to do with the matrices over finite
fields approach. So I would also like to understand better why that did not
work.
thanks and kind regards
Gary
On Mon, Apr 15, 2013 at 11:13 PM, Simon King simon.k...@uni-jena.de wrote:
Hi Gary,
On 2013-04-15, garymako...@googlemail.com garymako...@googlemail.com
wrote:
how big is M, how big is F, and is M sparse or do you have few zeros?
F is typically a small prime field, M is not sparse, but also not
particularly big, say, 200x100.
However, it turns out that after all I was mistaken: In contrast to what
I thought, the problem of enumerating covers starting with as few overlaps
as possible is more important for me than the problem with nowhere-zero row
combinations.
As you probably guessed, both problems are just attempts to solve
something else. So, perhaps it makes sense to formulate my *real*
problem:
I am computing the mod-p cohomology ring R of a finite group G. It is known
that the Krull dimension of the cohomology ring is equal to the p-rank r
of G. Now, I have given elements p_1,..., p_{r-1}, and I try to find an
element p_r of degree d such that p_1,..., p_r generate a sub-algebra
over which R is finite, i.e., p_1,...,p_r are parameters for R (Let's
call the problem: find a last parameter in degree d).
What I am looking for is a good heuristics, i.e., I would accept that
sometimes the algorithm can't find a last parameter in degree d even
though it exists.
R comes with a couple of maps f_1,...,f_k whose codomains are finite over a
polynomial ring (namely: the restriction maps to maximal p-elementary
abelian subgroups). It is known that p_1,...,p_r are parameters for R if
and only if their images under f_i forms a 0-dimensional ideal,
simultaneously
for all i=1,...,k.
The brute force approach would be: Let S a basis of the degree-d part of
R (lets call them standard monomials). One can list all linear
combinations of the elements of S, and by applying the f_i one can test
whether the linear combination is a last parameter. Since S can easily
contain more than 40 elements, a cleverer approach seems needed.
For each element m of S, we can test for which i=1,...,k the images of
p_1,...,p_{r-1} together with the image of m span a zero-dimensional
ideal (let's say that m is fine at i). If two elements m, m' are both
fine at i, it could be that a linear combination of m and m' is not fine
at i. But if we find a subset of S such that for all i=1,...,k there is
exactly one element of the subset that is fine at i, then the sum of
elements of this subset yields a last parameter.
So, this should explain my interest in finding covers. If the cover has
some overlap (i.e., for some i there are several elements fine at i),
then the corresponding sum of elements of S is not guaranteed to provide
a parameter, but I would expect that with small overlap it is still rather
likely to find a last parameter.
For the other problem: I tried to construct a matrix over GF(p) whose
rows correspond to the elements of S and somehow encode the images under
the f_1,...,f_k. This idea was to do it in such a way that having a
linear combination of rows that has no zero entry is a necessary but
perhaps not sufficient condition that the corresponding linear
combination of elements of S is a last parameter. But the construction I
had in mind did not work.
Best regards,
Simon
--
You received this message because you are subscribed to a topic in the
Google Groups sage-combinat-devel group.
To unsubscribe from this topic, visit
https://groups.google.com/d/topic/sage-combinat-devel/eKNz3fM5yJo/unsubscribe?hl=en
.
To unsubscribe from this group and all its topics, send an email to
sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to
Re: [sage-combinat-devel] Re: How to solve this combinatorial problem in Sage?
Hi Simon, Nathann,
On Mon, Apr 15, 2013 at 11:17:14AM +, Simon King wrote:
On 2013-04-15, Simon King simon.k...@uni-jena.de wrote:
I have a finite set X and a set S of subsets of X. I'd like to get a
list (or better: an iterator) of all subsets U of S (i.e., subsets of
subsets) such that the union of the elements of U is equal to X.
Ideally, I'd like that the number of intersection points (counted with
multiplicity) of elements of U is ascending.
Hence, if there is a disjoint cover of X by elements of S, then I'd like
to get this first, and otherwise I'd like to first get a cover that is as
close to being disjoint as possible.
I have found that one can get disjoint (exact) covers via dancing
links.
For non exact covers, this can be formulated straightforwardly as a
Mixed Integer Linear Program (MILP): take a 0-1 variable y_S for each
set S, and an inequation $\sum_{S, x\in S} y_S \geq 1$. So the problem
can be reduced (efficiently???) to that of iterating through the
integer points in a polytope. There are very optimized software using
backtracking algorithm to find optimal solutions for such systems of
equations.
As for iterating: Nathann, I haven't been following up on this one; do
you know what's the current status of this feature?
On a related note: Serge Guelton is working on Python bindings for the
ISL library, which might have this kind of features. Last time I got
in touch, he was considering coming to the Sage-Combinat days in June.
Cheers,
Nicolas
--
Nicolas M. Thiéry Isil nthi...@users.sf.net
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
