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: 270
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: 270
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: 270
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: 270
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”

Who is online

Users browsing this forum: No registered users and 1 guest

cron