Page 1 of 2
Checking if a polytope is a matroid polytope
Posted: 25 Sep 2017, 21:26
by mbrandt
A theorem by [GGMS] says that a polytope with vertices in \( \{0,1\}^n \) is a matroid polytope if and only if every edge of the polytope is parallel to \( e_i - e_j \) for some \( i \) and \( j \).
My question is, has this been implemented somewhere in polymake? Specifically, I would like to be able to ask if a polytope is a matroid polytope or not.
Additionally, we say a regular subdivision is a matroid subdivision if every polytope in the subdivision is a matroid polytope. I would like to be able to test if a regular subdivision is a matroid subdivision or not as well.
Re: Checking if a polytope is a matroid polytope
Posted: 27 Sep 2017, 14:05
by gawrilow
Apparently it's missing now in the code base, but it's quite easy to implement: just iterate over $polytope->GRAPH->EDGE_DIRECTIONS and check that every vector contains exactly one x != 0 and one -x element, the rest must be zeroes.
Re: Checking if a polytope is a matroid polytope
Posted: 27 Sep 2017, 19:52
by mbrandt
Thanks for the reply. I have never written any subroutines in perl and am not very familiar with the language. I wrote the following attempt at a solution:
Code: Select all
sub matroidal {
my @M = shift(@_);
my $bool = 1;
foreach @vector (@M) {
if (scalar(grep {$_ =~ 1} @vector) ==1) {
if (scalar(grep {$_ =~ -1} @vector) ==1) {
if (scalar(grep {$_ =~ 0} @vector) == scalar(@vector)-2){
};
else {
$bool = 0
};
};
else {
$bool = 0
};
};
else {
$bool = 0
};
};
return $bool;
};
Where the input is the list of edge directions. This returns a compilation error and I cannot see the problem. Do you see what I have done wrong?
Re: Checking if a polytope is a matroid polytope
Posted: 27 Sep 2017, 22:15
by gawrilow
Indeed, the perl syntax is not overly obvious for beginners...
The syntax error I guess comes from the foreach line. The loop variable must be a scalar.
Another problem which would show up during the execution is that lists are usually passed by reference.
To iterate over a list, the scalar holding the reference must be "dereferenced" using the @ operator.
To shorten your torture, please find a correct version:
Code: Select all
sub matroidal {
my ($edges)=@_;
foreach my $vector (@$edges) {
if (1 != grep { $_ == 1 } @$vector or
1 != grep { $_ == -1 } @$vector or
2 != grep { $_ != 0 } @$vector) {
return 0; # false
}
}
return 1; # true
}
my $p=new Polytope(...);
print matroidal($p->GRAPH->EDGE_DIRECTIONS);
Re: Checking if a polytope is a matroid polytope
Posted: 28 Sep 2017, 19:18
by mbrandt
One last question: If I wanted to check whether a regular subdivision was matroidal or not, how would I do this? Is there a property like EDGE_DIRECTIONS which I could apply to the subdivision (or the simplicial complex coming from the subdivision)?
Re: Checking if a polytope is a matroid polytope
Posted: 28 Sep 2017, 22:34
by gawrilow
There is no such property in PolyhedralComplex, but it can easily be computed on the fly:
Code: Select all
print matroidal(edge_directions($complex->GRAPH, $complex->VERTICES));
Re: Checking if a polytope is a matroid polytope
Posted: 28 Sep 2017, 23:27
by mbrandt
Thank you so much for your help!
I will just make one remark that if the subdivision is not a triangulation then one instead needs to use a polyhedral complex. Otherwise, extra edges will be added when Polymake makes a simplicial complex and these will likely not be of the form e_i-e_j. An example (of a matroid subdivision which is not a triangulation) is included below.
Code: Select all
$p = hypersimplex(2,4);
$w = new Vector<Rational>([1,0,0,0,0,0]);
$M = $p->VERTICES;
$S = new fan::SubdivisionOfPoints(POINTS=>$M,WEIGHTS=>$w);
$PC = $S->POLYHEDRAL_COMPLEX;
print matroidal(edge_directions($PC->GRAPH, $p->VERTICES));
Re: Checking if a polytope is a matroid polytope
Posted: 28 Sep 2017, 23:33
by gawrilow
Well, in your initial post you've spoken about "every polytope in the subdivision", which sounds like you've got an instance of a polyhedral complex in the first place. So why should you look at the triangulation instead? Or have I misunderstood your request?
Re: Checking if a polytope is a matroid polytope
Posted: 29 Sep 2017, 19:39
by mbrandt
Ah, sorry. In my own code I had been using simplicial complexes when a polyhedral complex was needed. Sorry for the confusion.
Re: Checking if a polytope is a matroid polytope
Posted: 07 Jun 2020, 01:47
by mbrandt
Hi,
I have just updated my version of Polymake, and the above code no longer works. I get the following error (after running the line print matroidal(edge_directions($PC->GRAPH, $p->VERTICES));):
polymake: ERROR: C++/perl Interface module compilation failed; most likely due to a type mismatch.
Set the variable $Polymake::User::Verbose::cpp to a positive value and repeat for more details.
How can I fix this?