# What does PORTA do?

PORTA is a software package for analyzing polyhedra. One problem it can solve is:

Problem: Find H-representation of the convex hull of some given points
Input: a set S of points in n-dimensional space
Output: a minimal inequality system defining conv(S).

Minor note: If conv(S) is not full dimensional, PORTA will report some equations too.

For a longer tutorial on PORTA and Polymake, see the slides by Marc Pfetsch.

# Example: Independent Sets

Consider the 5-vertex cycle graph C_5 on vertex set {1,2,3,4,5}. We can list all of its stable/independent sets:

ALL_STABLE_SETS = { {}, {1}, {2}, {3}, {4}, {5}, {1,3}, {1,4}, {2,4}, {2,5}, {3,5} }.

We can write these stable sets in terms of their characteristic vectors:

0 0 0 0 0
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 1 0 0
1 0 0 1 0
0 1 0 1 0
0 1 0 0 1
0 0 1 0 1

Here, each ROW represents a stable set. We can give PORTA this collection ALL_STABLE_SETS, and it will return the following inequality description of conv(ALL_STABLE_SETS):

( 1) -x1 <= 0
( 2) -x2 <= 0
( 3) -x3 <= 0
( 4) -x4 <= 0
( 5) -x5 <= 0
( 6) +x4+x5 <= 1
( 7) +x3+x4 <= 1
( 8) +x2+x3 <= 1
( 9) +x1 +x5 <= 1
( 10) +x1+x2 <= 1
( 11) +x1+x2+x3+x4+x5 <= 2

Inequalities (1)–(5) are the nonnegativity bounds; (6)–(10) are the edge inequalities; (11) is an odd-hole inequality.