Checking if a polytope is a matroid polytope

General discussion on polymake goes here.

Moderator: Moderators

mbrandt
Posts: 5
Joined: 25 Sep 2017, 21:20

Checking if a polytope is a matroid polytope

Postby mbrandt » 25 Sep 2017, 21:26

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.

User avatar
gawrilow
Main Author
Posts: 308
Joined: 25 Dec 2010, 17:40

Re: Checking if a polytope is a matroid polytope

Postby gawrilow » 27 Sep 2017, 14:05

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

Re: Checking if a polytope is a matroid polytope

Postby mbrandt » 27 Sep 2017, 19:52

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?

User avatar
gawrilow
Main Author
Posts: 308
Joined: 25 Dec 2010, 17:40

Re: Checking if a polytope is a matroid polytope

Postby gawrilow » 27 Sep 2017, 22:15

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

Re: Checking if a polytope is a matroid polytope

Postby mbrandt » 28 Sep 2017, 19:18

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

User avatar
gawrilow
Main Author
Posts: 308
Joined: 25 Dec 2010, 17:40

Re: Checking if a polytope is a matroid polytope

Postby gawrilow » 28 Sep 2017, 22:34

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

Re: Checking if a polytope is a matroid polytope

Postby mbrandt » 28 Sep 2017, 23:27

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

User avatar
gawrilow
Main Author
Posts: 308
Joined: 25 Dec 2010, 17:40

Re: Checking if a polytope is a matroid polytope

Postby gawrilow » 28 Sep 2017, 23:33

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

Re: Checking if a polytope is a matroid polytope

Postby mbrandt » 29 Sep 2017, 19:39

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


Return to “General Discussion”

cron