Checking if a polytope is a matroid polytope

[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.

[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.

[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?

[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);

[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)?

[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));

[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));

[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?

[mbrandt]

Ah, sorry. In my own code I had been using simplicial complexes when a polyhedral complex was needed. Sorry for the confusion.

[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?