Integral polytope

<h2 id="examples">Examples</h2>
<p>An 
  
    
      
        n
      
    
    {\displaystyle n}
  
-dimensional regular <a href="/facts/Simplex/0FCfNRN8">simplex</a> can be represented as an integer polytope in 
  
    
      
        
          
            R
          
          
            n
            +
            1
          
        
      
    
    {\displaystyle \mathbb {R} ^{n+1}}
  
, the convex hull of the integer points for which one coordinate is one and the rest are zero. Another important type of integral simplex, the <a href="/facts/Orthoscheme/jwXB2mQV">orthoscheme</a>, can be formed as the convex hull of integer points whose coordinates begin with some number of consecutive ones followed by zeros in all remaining coordinates. The 
  
    
      
        n
      
    
    {\displaystyle n}
  
-dimensional <a href="/facts/Unit_cube/S52tnk6m">unit cube</a> in 
  
    
      
        
          
            R
          
          
            n
          
        
      
    
    {\displaystyle \mathbb {R} ^{n}}
  
 has as its vertices all integer points whose coordinates are zero or one. A <a href="/facts/Permutahedron/No1KH0rE">permutahedron</a> has vertices whose coordinates are obtained by applying all possible permutations to the vector 
  
    
      
        (
        1
        ,
        2
        ,
        .
        .
        .
        ,
        n
        )
      
    
    {\displaystyle (1,2,...,n)}
  
. An <a href="/facts/Associahedron/2ajjs785">associahedron</a> in Loday's convex realization is also an integer polytope and a deformation of the permutahedron.
</p>
<h2 id="in-optimization">In optimization</h2>
<p>In the context of <a href="/facts/Linear_programming/GduXFQxT">linear programming</a> and related problems in <a href="/facts/Mathematical_optimization/oRn8Iv5I">mathematical optimization</a>, convex polytopes are often described by a system of <a href="/facts/Linear_inequality/YGHD3tW5">linear inequalities</a> that their points must obey. When a polytope is integral, linear programming can be used to solve <a href="/facts/Integer_programming/MDaaadoA">integer programming</a> problems for the given system of inequalities, a problem that can otherwise be more difficult.
</p><p>Some polyhedra arising from <a href="/facts/Combinatorial_optimization/PTcloS79">combinatorial optimization</a> problems are automatically integral. For instance, this is true of the <a href="/facts/Order_polytope/l4xueKAh">order polytope</a> of any <a href="/facts/Partially_ordered_set/qb4a3FAX">partially ordered set</a>, a polytope defined by pairwise inequalities between coordinates corresponding to comparable elements in the set.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> Another well-known polytope in combinatorial optimization is the <a href="/facts/Matching_polytope/PQfMmLnt">matching polytope</a>. Clearly, one seeks for finding matchings algorithmically and one technique is linear programming. The polytope described by the linear program upper bounding the sum of edges taken per vertex is integral in the case of <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graphs</a>, that is, it exactly describes the matching polytope, while for general graphs it is non-integral.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> Hence, for bipartite graphs, it suffices to solve the corresponding linear program to obtain a valid <a href="/facts/Matching_(graph_theory)/s0pUJ7hd">matching</a>. For general graphs, however, there are two other characterizations of the matching polytope one of which makes use of the blossom inequality for odd subsets of vertices and hence allows to relax the integer program to a linear program while still obtaining valid matchings.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> These characterizations are of further interest in <a href="/facts/Blossom_algorithm/RoWYD8YM">Edmonds' famous blossom algorithm</a> used for finding such matchings in general graphs.
</p>
<h2 id="computational-complexity">Computational complexity</h2>
<p>For a polytope described by linear inequalities, when the polytope is non-integral, one can prove its non-integrality by finding a vertex whose coordinates are not integers. Such a vertex can be described combinatorially by specifying a subset of inequalities that, when turned into a <a href="/facts/System_of_linear_equations/fk9CFdgp">system of linear equations</a>, have a unique solution, and verifying that this solution point obeys all of the other inequalities. Therefore, testing integrality belongs to the <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a> <a href="/facts/CoNP/M67JgWNa">coNP</a> of problems for which a negative answer can be easily proven. More specifically, it is <a href="/facts/CoNP-complete/oGepXz5C">coNP-complete</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>
</p>
<h2 id="related-objects">Related objects</h2>
<p>Many of the important properties of an integral polytope, including its <a href="/facts/Volume/aeAXCBUd">volume</a> and number of vertices, is encoded by its <a href="/facts/Ehrhart_polynomial/WjuUYzrT">Ehrhart polynomial</a>.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>
</p><p>Integral polytopes are prominently featured in the theory of <a href="/facts/Toric_variety/m1wEbNWw">toric varieties</a>, where they correspond to polarized projective toric varieties.
For instance, the toric variety corresponding to a <a href="/facts/Simplex/0FCfNRN8">simplex</a> is a <a href="/facts/Projective_space/7MSpA9cM">projective space</a>. The toric variety corresponding to a <a href="/facts/Unit_cube/S52tnk6m">unit cube</a> is the <a href="/facts/Segre_embedding/xDVUkB2C">Segre embedding</a> of the 
  
    
      
        n
      
    
    {\displaystyle n}
  
 -fold product of the projective line.
</p><p>In <a href="/facts/Algebraic_geometry/rh7RHVp3">algebraic geometry</a>, an important instance of lattice polytopes called the <a href="/facts/Newton_polytope/8gzqVCja">Newton polytopes</a> are the convex hulls of vectors representing the exponents of each variable in the terms of a <a href="/facts/Polynomial/Lzak8VVx">polynomial</a>. For example, the polynomial 
  
    
      
        x
        y
        +
        2
        
          x
          
            2
          
        
        +
        
          y
          
            5
          
        
        +
        4
      
    
    {\displaystyle xy+2x^{2}+y^{5}+4}
  
 has four terms, 
  
    
      
        x
        y
      
    
    {\displaystyle xy}
  
 with exponent vector (1,1), 
  
    
      
        2
        
          x
          
            2
          
        
      
    
    {\displaystyle 2x^{2}}
  
 with exponent vector (2,0), 
  
    
      
        
          y
          
            5
          
        
      
    
    {\displaystyle y^{5}}
  
 with exponent vector (0,5), and 
  
    
      
        4
      
    
    {\displaystyle 4}
  
 with exponent vector (0,0). Its Newton polytope is the convex hull of the four points (1,1), (2,0), (0,5), and (0,0). This hull is an integral triangle with the point (1,1) interior to the triangle and the other three points as its vertices.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Delzant_polytope/yGRz9p7I">Delzant polytope</a></li>
<li><a href="/facts/Reeve_tetrahedron/nRqsSEFx">Reeve tetrahedron</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Cornuéjols, Gérard (2001), Combinatorial Optimization: Packing and Covering, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 74, Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics (SIAM), p. 4, doi:10.1137/1.9780898717105, ISBN 0-89871-481-8, MR 1828452 <a href="0-89871-481-8" target="_blank">0-89871-481-8</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Murota, Kazuo (2003), Discrete convex analysis, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics (SIAM), p. 90, doi:10.1137/1.9780898718508, hdl:2433/149564, ISBN 0-89871-540-7, MR 1997998 <a href="0-89871-540-7" target="_blank">0-89871-540-7</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Stanley, Richard P. (1986), "Two poset polytopes", Discrete & Computational Geometry, 1 (1): 9–23, doi:10.1007/BF02187680, MR 0824105 <a href="/wiki/Discrete_%26_Computational_Geometry" target="_blank">/wiki/Discrete_%26_Computational_Geometry</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Lovász, László (1986). Matching theory. North-Holland. pp. 269–274. ISBN 978-0-444-87916-5. OCLC 316569965. <a href="978-0-444-87916-5" target="_blank">978-0-444-87916-5</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Lovász, László (1986). Matching theory. North-Holland. pp. 274–281. ISBN 978-0-444-87916-5. OCLC 316569965. <a href="978-0-444-87916-5" target="_blank">978-0-444-87916-5</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Ding, Guoli; Feng, Li; Zang, Wenan (2008), "The complexity of recognizing linear systems with certain integrality properties", Mathematical Programming, Series A, 114 (2): 321–334, doi:10.1007/s10107-007-0103-y, hdl:10722/58972, MR 2393045 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Barvinok, A. I. (1994), "Computing the Ehrhart polynomial of a convex lattice polytope", Discrete & Computational Geometry, 12 (1): 35–48, doi:10.1007/BF02574364, MR 1280575 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
</ol>

Integral polytope open-in-new

Integral polytope