 ## Checking if a polytope is a matroid polytope

General discussion on polymake goes here.
mbrandt
Posts: 7
Joined: 25 Sep 2017, 21:20

### Checking if a polytope is a matroid polytope

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
Main Author
Posts: 405
Joined: 25 Dec 2010, 17:40

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 Posts: 7 Joined: 25 Sep 2017, 21:20 ### Re: Checking if a polytope is a matroid polytope 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 Main Author Posts: 405 Joined: 25 Dec 2010, 17:40 ### Re: Checking if a polytope is a matroid polytope 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
Posts: 7
Joined: 25 Sep 2017, 21:20

### Re: Checking if a polytope is a matroid polytope

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
Main Author
Posts: 405
Joined: 25 Dec 2010, 17:40

### Re: Checking if a polytope is a matroid polytope

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
Posts: 7
Joined: 25 Sep 2017, 21:20

### Re: Checking if a polytope is a matroid polytope

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 Main Author Posts: 405 Joined: 25 Dec 2010, 17:40 ### Re: Checking if a polytope is a matroid polytope 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 Posts: 7 Joined: 25 Sep 2017, 21:20 ### Re: Checking if a polytope is a matroid polytope Ah, sorry. In my own code I had been using simplicial complexes when a polyhedral complex was needed. Sorry for the confusion. mbrandt Posts: 7 Joined: 25 Sep 2017, 21:20 ### Re: Checking if a polytope is a matroid polytope 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? 