61:
68:
54:
75:
45:
31:
38:
24:
398:. 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. These characterizations are of further interest in
410:
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
658:
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.
390:. 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
394:, that is, it exactly describes the matching polytope, while for general graphs it is non-integral. Hence, for bipartite graphs, it suffices to solve the corresponding linear program to obtain a valid
386:, a polytope defined by pairwise inequalities between coordinates corresponding to comparable elements in the set. Another well-known polytope in combinatorial optimization is the
230:
556:
287:
699:, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 74, Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics (SIAM), p. 4,
341:
236:, 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
609:
636:
579:
656:
483:
254:
191:
741:, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics (SIAM), p. 90,
415:, have a unique solution, and verifying that this solution point obeys all of the other inequalities. Therefore, testing integrality belongs to the
232:, 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
871:
836:
165:. The special cases of two- and three-dimensional integral polytopes may be called polygons or polyhedra instead of polytopes, respectively.
789:
764:
712:
895:
Ding, Guoli; Feng, Li; Zang, Wenan (2008), "The complexity of recognizing linear systems with certain integrality properties",
449:, where they correspond to polarized projective toric varieties. For instance, the toric variety corresponding to a
412:
375:
360:
127:
395:
383:
200:
146:
503:
263:
97:
368:
367:
that their points must obey. When a polytope is integral, linear programming can be used to solve
347:
in Loday's convex realization is also an integer polytope and a deformation of the permutahedron.
981:
489:
439:
356:
296:
293:
has vertices whose coordinates are obtained by applying all possible permutations to the vector
371:
problems for the given system of inequalities, a problem that can otherwise be more difficult.
877:
867:
842:
832:
760:
708:
673:
496:
are the convex hulls of vectors representing the exponents of each variable in the terms of a
399:
387:
364:
139:
60:
736:
948:
912:
904:
798:
750:
742:
700:
694:
668:
584:
454:
416:
962:
926:
812:
774:
722:
614:
67:
53:
958:
922:
808:
770:
718:
493:
462:
391:
135:
74:
939:
Barvinok, A. I. (1994), "Computing the
Ehrhart polynomial of a convex lattice polytope",
561:
641:
468:
422:
of problems for which a negative answer can be easily proven. More specifically, it is
379:
239:
176:
44:
975:
446:
423:
344:
290:
154:
87:
233:
150:
908:
497:
92:
881:
846:
746:
704:
458:
289:
has as its vertices all integer points whose coordinates are zero or one. A
257:
30:
37:
23:
434:
Many of the important properties of an integral polytope, including its
953:
917:
803:
755:
450:
378:
problems are automatically integral. For instance, this is true of the
194:
143:
16:
A convex polytope whose vertices all have integer
Cartesian coordinates
861:
826:
435:
419:
82:
445:
Integral polytopes are prominently featured in the theory of
492:, an important instance of lattice polytopes called the
363:, convex polytopes are often described by a system of
18:
644:
617:
587:
564:
506:
471:
299:
266:
242:
203:
179:
787:Stanley, Richard P. (1986), "Two poset polytopes",
402:used for finding such matchings in general graphs.
650:
630:
603:
573:
550:
477:
335:
281:
248:
224:
185:
696:Combinatorial Optimization: Packing and Covering
197:can be represented as an integer polytope in
8:
149:. That is, it is a polytope that equals the
120:Four integral polytopes in three dimensions
438:and number of vertices, is encoded by its
952:
916:
802:
754:
643:
622:
616:
595:
586:
563:
536:
523:
505:
470:
298:
273:
269:
268:
265:
241:
210:
206:
205:
202:
178:
685:
457:. The toric variety corresponding to a
485:-fold product of the projective line.
941:Discrete & Computational Geometry
790:Discrete & Computational Geometry
157:. Integral polytopes are also called
7:
866:. North-Holland. pp. 274–281.
831:. North-Holland. pp. 269–274.
897:Mathematical Programming, Series A
225:{\displaystyle \mathbb {R} ^{n+1}}
14:
551:{\displaystyle xy+2x^{2}+y^{5}+4}
400:Edmonds' famous blossom algorithm
638:with exponent vector (0,5), and
282:{\displaystyle \mathbb {R} ^{n}}
73:
66:
59:
52:
43:
36:
29:
22:
500:. For example, the polynomial
330:
300:
1:
611:with exponent vector (2,0),
581:with exponent vector (1,1),
374:Some polyhedra arising from
693:Cornuéjols, Gérard (2001),
336:{\displaystyle (1,2,...,n)}
998:
413:system of linear equations
376:combinatorial optimization
909:10.1007/s10107-007-0103-y
361:mathematical optimization
119:
738:Discrete convex analysis
406:Computational complexity
359:and related problems in
128:polyhedral combinatorics
860:Lovász, László (1986).
825:Lovász, László (1986).
747:10.1137/1.9780898718508
705:10.1137/1.9780898717105
735:Murota, Kazuo (2003),
652:
632:
605:
604:{\displaystyle 2x^{2}}
575:
552:
479:
337:
283:
250:
226:
187:
653:
633:
631:{\displaystyle y^{5}}
606:
576:
553:
480:
384:partially ordered set
338:
284:
251:
227:
193:-dimensional regular
188:
147:Cartesian coordinates
642:
615:
585:
562:
504:
469:
297:
264:
240:
201:
177:
369:integer programming
365:linear inequalities
954:10.1007/BF02574364
804:10.1007/BF02187680
648:
628:
601:
574:{\displaystyle xy}
571:
548:
490:algebraic geometry
475:
440:Ehrhart polynomial
357:linear programming
355:In the context of
333:
279:
246:
222:
183:
873:978-0-444-87916-5
838:978-0-444-87916-5
674:Reeve tetrahedron
651:{\displaystyle 4}
478:{\displaystyle n}
388:matching polytope
249:{\displaystyle n}
186:{\displaystyle n}
159:lattice polytopes
132:integral polytope
124:
123:
989:
966:
965:
956:
936:
930:
929:
920:
892:
886:
885:
857:
851:
850:
822:
816:
815:
806:
784:
778:
777:
758:
732:
726:
725:
690:
669:Delzant polytope
657:
655:
654:
649:
637:
635:
634:
629:
627:
626:
610:
608:
607:
602:
600:
599:
580:
578:
577:
572:
558:has four terms,
557:
555:
554:
549:
541:
540:
528:
527:
494:Newton polytopes
484:
482:
481:
476:
455:projective space
417:complexity class
392:bipartite graphs
342:
340:
339:
334:
288:
286:
285:
280:
278:
277:
272:
255:
253:
252:
247:
231:
229:
228:
223:
221:
220:
209:
192:
190:
189:
184:
126:In geometry and
77:
70:
63:
56:
47:
40:
33:
26:
19:
997:
996:
992:
991:
990:
988:
987:
986:
972:
971:
970:
969:
938:
937:
933:
894:
893:
889:
874:
863:Matching theory
859:
858:
854:
839:
828:Matching theory
824:
823:
819:
786:
785:
781:
767:
734:
733:
729:
715:
692:
691:
687:
682:
665:
640:
639:
618:
613:
612:
591:
583:
582:
560:
559:
532:
519:
502:
501:
467:
466:
463:Segre embedding
447:toric varieties
432:
430:Related objects
408:
353:
351:In optimization
295:
294:
267:
262:
261:
238:
237:
204:
199:
198:
175:
174:
171:
136:convex polytope
99:
17:
12:
11:
5:
995:
993:
985:
984:
974:
973:
968:
967:
931:
903:(2): 321–334,
887:
872:
852:
837:
817:
779:
765:
727:
713:
684:
683:
681:
678:
677:
676:
671:
664:
661:
647:
625:
621:
598:
594:
590:
570:
567:
547:
544:
539:
535:
531:
526:
522:
518:
515:
512:
509:
474:
431:
428:
407:
404:
380:order polytope
352:
349:
332:
329:
326:
323:
320:
317:
314:
311:
308:
305:
302:
276:
271:
245:
219:
216:
213:
208:
182:
170:
167:
155:integer points
122:
121:
117:
116:
113:
110:
107:
103:
102:
95:
90:
85:
79:
78:
71:
64:
57:
49:
48:
41:
34:
27:
15:
13:
10:
9:
6:
4:
3:
2:
994:
983:
980:
979:
977:
964:
960:
955:
950:
946:
942:
935:
932:
928:
924:
919:
914:
910:
906:
902:
898:
891:
888:
883:
879:
875:
869:
865:
864:
856:
853:
848:
844:
840:
834:
830:
829:
821:
818:
814:
810:
805:
800:
796:
792:
791:
783:
780:
776:
772:
768:
766:0-89871-540-7
762:
757:
752:
748:
744:
740:
739:
731:
728:
724:
720:
716:
714:0-89871-481-8
710:
706:
702:
698:
697:
689:
686:
679:
675:
672:
670:
667:
666:
662:
660:
645:
623:
619:
596:
592:
588:
568:
565:
545:
542:
537:
533:
529:
524:
520:
516:
513:
510:
507:
499:
495:
491:
486:
472:
464:
460:
456:
452:
448:
443:
441:
437:
429:
427:
425:
424:coNP-complete
421:
418:
414:
405:
403:
401:
397:
393:
389:
385:
381:
377:
372:
370:
366:
362:
358:
350:
348:
346:
345:associahedron
327:
324:
321:
318:
315:
312:
309:
306:
303:
292:
291:permutahedron
274:
259:
256:-dimensional
243:
235:
217:
214:
211:
196:
180:
168:
166:
164:
160:
156:
152:
148:
145:
141:
137:
133:
129:
118:
114:
111:
108:
106:(±1, ±1, ±1)
105:
104:
101:
96:
94:
91:
89:
88:Cuboctahedron
86:
84:
81:
80:
76:
72:
69:
65:
62:
58:
55:
51:
50:
46:
42:
39:
35:
32:
28:
25:
21:
20:
947:(1): 35–48,
944:
940:
934:
900:
896:
890:
862:
855:
827:
820:
794:
788:
782:
737:
730:
695:
688:
487:
444:
433:
409:
373:
354:
172:
162:
158:
131:
125:
115:(0, ±1, ±2)
109:(0, ±1, ±1)
918:10722/58972
797:(1): 9–23,
756:2433/149564
234:orthoscheme
163:Z-polytopes
151:convex hull
112:(0, 0, ±1)
680:References
498:polynomial
100:octahedron
93:Octahedron
982:Polytopes
882:316569965
847:316569965
459:unit cube
258:unit cube
142:all have
98:Truncated
976:Category
663:See also
396:matching
169:Examples
140:vertices
963:1280575
927:2393045
813:0824105
775:1997998
723:1828452
465:of the
461:is the
451:simplex
382:of any
195:simplex
153:of its
144:integer
961:
925:
880:
870:
845:
835:
811:
773:
763:
721:
711:
436:volume
138:whose
453:is a
343:. An
134:is a
130:, an
878:OCLC
868:ISBN
843:OCLC
833:ISBN
761:ISBN
709:ISBN
420:coNP
83:Cube
949:doi
913:hdl
905:doi
901:114
799:doi
751:hdl
743:doi
701:doi
488:In
260:in
173:An
161:or
978::
959:MR
957:,
945:12
943:,
923:MR
921:,
911:,
899:,
876:.
841:.
809:MR
807:,
793:,
771:MR
769:,
759:,
749:,
719:MR
717:,
707:,
442:.
426:.
951::
915::
907::
884:.
849:.
801::
795:1
753::
745::
703::
646:4
624:5
620:y
597:2
593:x
589:2
569:y
566:x
546:4
543:+
538:5
534:y
530:+
525:2
521:x
517:2
514:+
511:y
508:x
473:n
331:)
328:n
325:,
322:.
319:.
316:.
313:,
310:2
307:,
304:1
301:(
275:n
270:R
244:n
218:1
215:+
212:n
207:R
181:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
