Polyhedral combinatorics
ಪಾಲಿಹೆಡ್ರಲ್ ಕಾಂಬಿನೇಟರಿಕ್ಸ್ ಗಣಿತಶಾಸ್ತ್ರದ ಒಂದು ಶಾಖೆಯಾಗಿದ್ದು, ಕಾಂಬಿನೇಟರಿಕ್ಸ್ ಮತ್ತು ಡಿಸ್ಕ್ರೀಟ್ ಜ್ಯಾಮಿತಿಯೊಳಗೆ, ಇದು ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಹೆಡ್ರಾ ಮತ್ತು ಉನ್ನತ-ಆಯಾಮದ ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಟೋಪ್ಗಳ ಮುಖಗಳನ್ನು ಎಣಿಸುವ ಮತ್ತು ವಿವರಿಸುವ ಸಮಸ್ಯೆಗಳನ್ನು ಅಧ್ಯಯನ ಮಾಡುತ್ತದೆ. ಪಾಲಿಹೆಡ್ರಲ್ ಕಾಂಬಿನೇಟರಿಕ್ಸ್ನಲ್ಲಿನ ಸಂಶೋಧನೆಯು ಎರಡು ವಿಭಿನ್ನ ಕ್ಷೇತ್ರಗಳಿಗೆ ಸೇರುತ್ತದೆ. ಈ ಕ್ಷೇತ್ರದಲ್ಲಿನ ಗಣಿತಶಾಸ್ತ್ರಜ್ಞರು ಪಾಲಿಟೋಪ್ಗಳ ಸಂಯೋಜನೆಯನ್ನು ಅಧ್ಯಯನ ಮಾಡುತ್ತಾರೆ; ಉದಾಹರಣೆಗೆ, ಅವರು ಅನಿಯಂತ್ರಿತ ಪಾಲಿಟೋಪ್ಗಳಲ್ಲಿ ಅಥವಾ ಪಾಲಿಟೋಪ್ಗಳ ಕೆಲವು ಪ್ರಮುಖ ಉಪವರ್ಗಗಳಲ್ಲಿ ಉನ್ನತ ಆಯಾಮಗಳ ಶೃಂಗಗಳು, ಅಂಚುಗಳು ಮತ್ತು ಮುಖಗಳ ನಡುವಿನ ಸಂಬಂಧಗಳನ್ನು ವಿವರಿಸುವ ಅಸಮಾನತೆಗಳನ್ನು ಹುಡುಕುತ್ತಾರೆ ಮತ್ತು ಪಾಲಿಟೋಪ್ಗಳ ಸಂಪರ್ಕ ಮತ್ತು ವ್ಯಾಸದಂತಹ ಇತರ ಸಂಯೋಜನೆಯ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಅಧ್ಯಯನ ಮಾಡುತ್ತಾರೆ (ಯಾವುದೇ ಇತರ ಶೃಂಗದಿಂದ ಯಾವುದೇ ಶೃಂಗವನ್ನು ತಲುಪಲು ಅಗತ್ಯವಿರುವ ಹಂತಗಳ ಸಂಖ್ಯೆ). ಹೆಚ್ಚುವರಿಯಾಗಿ, ಅನೇಕ ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನಿಗಳು ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳಿಂದ ಉಂಟಾಗುವ ಕೆಲವು ನಿರ್ದಿಷ್ಟ ಪಾಲಿಟೋಪ್ಗಳ (ವಿಶೇಷವಾಗಿ 0-1 ಪಾಲಿಟೋಪ್ಗಳು, ಅವುಗಳ ಶೃಂಗಗಳು ಹೈಪರ್ಕ್ಯೂಬ್ನ ಉಪಗುಂಪುಗಳಾಗಿರುತ್ತವೆ) ಮುಖಗಳ ನಿಖರವಾದ ವಿವರಣೆಗಳ ಸಂಶೋಧನೆಯನ್ನು ವಿವರಿಸಲು "ಪಾಲಿಹೆಡ್ರಲ್ ಕಾಂಬಿನೇಟರಿಕ್ಸ್" ಎಂಬ ಪದವನ್ನು ಬಳಸುತ್ತಾರೆ. ಮುಖಗಳು ಮತ್ತು ಮುಖ-ಎಣಿಕೆ ವಾಹಕಗಳು ಒಂದು ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಟೋಪ್ P ಯ ಮುಖವನ್ನು P ಮತ್ತು ಮುಚ್ಚಿದ ಅರ್ಧ ಜಾಗ H ನ ಛೇದಕ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು, ಅಂದರೆ H ನ ಗಡಿಯು P ಯ ಯಾವುದೇ ಆಂತರಿಕ ಬಿಂದುವನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ. ಮುಖದ ಆಯಾಮವು ಈ ಹೊದಿಕೆಯ ಆಯಾಮವಾಗಿದೆ. 0-ಆಯಾಮದ ಮುಖಗಳು ಸ್ವತಃ ಶೃಂಗಗಳಾಗಿವೆ, ಮತ್ತು 1-ಆಯಾಮದ ಮುಖಗಳು (ಅಂಚುಗಳು ಎಂದು ಕರೆಯಲ್ಪಡುತ್ತವೆ) ಶೃಂಗಗಳ ಜೋಡಿಗಳನ್ನು ಸಂಪರ್ಕಿಸುವ ರೇಖೆಯ ಭಾಗಗಳಾಗಿವೆ. ಈ ವ್ಯಾಖ್ಯಾನವು ಖಾಲಿ ಸೆಟ್ ಮತ್ತು ಸಂಪೂರ್ಣ ಪಾಲಿಟೋಪ್ ಪಿ ಅನ್ನು ಸಹ ಒಳಗೊಂಡಿದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಪಿ ಸ್ವತಃ ಆಯಾಮ ಡಿ ಹೊಂದಿದ್ದರೆ, ಆಯಾಮ ಡಿ-1 ಹೊಂದಿರುವ ಪಿ ಮುಖಗಳನ್ನು ಪಿ ಮುಖಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಆಯಾಮ ಡಿ-2 ಹೊಂದಿರುವ ಮುಖಗಳನ್ನು ರೇಖೆಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಪಿ ಯ ಮುಖಗಳನ್ನು ಸೇರ್ಪಡೆಯ ಮೂಲಕ ಭಾಗಶಃ ಕ್ರಮಗೊಳಿಸಬಹುದು, ಮುಖದ ಜಾಲರಿಯನ್ನು ರೂಪಿಸುತ್ತದೆ, ಅದು ಅದರ ಮೇಲಿನ ಅಂಶವಾದ ಪಿ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ಅದರ ಕೆಳಗಿನ ಅಂಶವಾಗಿ ಖಾಲಿ ಸೆಟ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಪಾಲಿಹೆಡ್ರಲ್ ಸಂಯೋಜನೆಯಲ್ಲಿ ಒಂದು ಪ್ರಮುಖ ಸಾಧನವೆಂದರೆ ಪಾಲಿಟೋಪ್ನ ಎಫ್-ವೆಕ್ಟರ್, ವೆಕ್ಟರ್ (ಎಫ್0, ಎಫ್1,., ಎಫ್ಡಿ−1), ಅಲ್ಲಿ ಫೈ ಎಂಬುದು ಪಾಲಿಟೋಪ್ನ ಐ-ಆಯಾಮದ ವೈಶಿಷ್ಟ್ಯಗಳ ಸಂಖ್ಯೆಯಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, ಒಂದು ಘನವು ಎಂಟು ಶೃಂಗಗಳು, ಹನ್ನೆರಡು ಅಂಚುಗಳು ಮತ್ತು ಆರು ಮುಖಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಆದ್ದರಿಂದ ಅದರ f-ವಾಹಕವು (8,12,6) ಆಗಿದೆ. ಡ್ಯುಯಲ್ ಪಾಲಿಟೋಪ್ ಹಿಮ್ಮುಖ ಕ್ರಮದಲ್ಲಿ ಒಂದೇ ಸಂಖ್ಯೆಗಳೊಂದಿಗೆ ಎಫ್-ವೆಕ್ಟರ್ ಅನ್ನು ಹೊಂದಿದೆ; ಆದ್ದರಿಂದ, ಉದಾಹರಣೆಗೆ, ಸಾಮಾನ್ಯ ಆಕ್ಟಾಹೆಡ್ರನ್, ಕ್ಯೂಬ್ಗೆ ಡ್ಯುಯಲ್, ಎಫ್-ವೆಕ್ಟರ್ ಅನ್ನು ಹೊಂದಿದೆ (6,12,8). ಕಾನ್ಫಿಗರೇಶನ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳು ಸಾಮಾನ್ಯ ಪಾಲಿಟೋಪ್ಗಳ ಎಫ್-ವಾಹಕಗಳನ್ನು ಕರ್ಣೀಯ ಅಂಶಗಳಾಗಿ ಒಳಗೊಂಡಿರುತ್ತವೆ. ಮುಖದ ಜಾಲರಿಯ ಎಲ್ಲಾ ಹಂತಗಳಲ್ಲಿನ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸುವ ಮೂಲಕ, f-ವಾಹಕದ ಪ್ರತಿ ತುದಿಯಲ್ಲಿ ಒಂದನೇ ಸಂಖ್ಯೆಯನ್ನು ಸಂಯೋಜಿಸುವ ಮೂಲಕ ವಿಸ್ತರಿಸಿದ f-ವಾಹಕವು ರೂಪುಗೊಳ್ಳುತ್ತದೆ; ವಾಹಕದ ಎಡಭಾಗದಲ್ಲಿ, f−1 = 1 ಖಾಲಿ ಸಮೂಹವನ್ನು ಮುಖವಾಗಿ ಎಣಿಸುತ್ತದೆ, ಆದರೆ ಬಲಭಾಗದಲ್ಲಿ, fd = 1 ಸ್ವತಃ P ಅನ್ನು ಎಣಿಸುತ್ತದೆ. ಕ್ಯೂಬ್ಗೆ ವಿಸ್ತರಿಸಿದ f-ವಾಹಕವು (1,8,12,6,1) ಮತ್ತು ಆಕ್ಟಾಹೆಡ್ರನ್ಗೆ ಇದು (1,6,12,8,1) ಆಗಿದೆ. ಈ ಉದಾಹರಣೆಯ ಪಾಲಿಹೆಡ್ರಾದ ವಾಹಕಗಳು ಏಕರೂಪವಾಗಿದ್ದರೂ (ಗುಣಾಂಕಗಳನ್ನು ಎಡದಿಂದ ಬಲಕ್ಕೆ ಕ್ರಮದಲ್ಲಿ ತೆಗೆದುಕೊಳ್ಳಲಾಗುತ್ತದೆ, ಗರಿಷ್ಠಕ್ಕೆ ಹೆಚ್ಚಾಗುತ್ತದೆ ಮತ್ತು ನಂತರ ಕಡಿಮೆಯಾಗುತ್ತದೆ), ಇದು ನಿಜವಲ್ಲದ ಉನ್ನತ-ಆಯಾಮದ ಪಾಲಿಟೋಪ್ಗಳಿವೆ. ಸರಳವಾದ ಪಾಲಿಟೋಪ್ಗಳಿಗೆ (ಪ್ರತಿಯೊಂದು ಮುಖವು ಸಿಂಪ್ಲೆಕ್ಸ್ ಆಗಿರುವ ಪಾಲಿಟೋಪ್ಗಳು), ಈ ವಾಹಕಗಳನ್ನು ಪರಿವರ್ತಿಸುವುದು ಸಾಮಾನ್ಯವಾಗಿ ಅನುಕೂಲಕರವಾಗಿದೆ, ಇದು ಎಚ್-ವಾಹಕ ಎಂದು ಕರೆಯಲ್ಪಡುವ ವಿಭಿನ್ನ ವಾಹಕವನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ. ನಾವು f-ವಾಹಕದ ಪದಗಳನ್ನು (ಅಂತಿಮ 1 ಅನ್ನು ಬಿಟ್ಟುಬಿಟ್ಟರೆ) ಬಹುಪದ f (x) = βxd−i−1 ರ ಗುಣಾಂಕಗಳೆಂದು ವ್ಯಾಖ್ಯಾನಿಸಿದರೆ (ಉದಾಹರಣೆಗೆ, ಆಕ್ಟಾಹೆಡ್ರನ್ಗೆ ಇದು ಬಹುಪದ f (x) = x3 + 6x2 + 12x + 8 ಅನ್ನು ನೀಡುತ್ತದೆ), ಆಗ h-ವಾಹಕವು ಬಹುಪದ h (x) = f (x−1) ನ ಗುಣಾಂಕಗಳನ್ನು ಪಟ್ಟಿ ಮಾಡುತ್ತದೆ (ಮತ್ತೆ, ಆಕ್ಟಾಹೆಡ್ರನ್ಗೆ, h (x) = x3 + 3x2 + 3x + 1). ಜಿಗ್ಲರ್ ಬರೆಯುವಂತೆ, "ಸರಳವಾದ ಪಾಲಿಟೋಪ್ಗಳ ಬಗೆಗಿನ ವಿವಿಧ ಸಮಸ್ಯೆಗಳಿಗೆ, ಮುಖದ ಸಂಖ್ಯೆಗಳ ಬಗೆಗಿನ ಮಾಹಿತಿಯನ್ನು ಎನ್ಕೋಡ್ ಮಾಡಲು ಎಚ್-ವಾಹಕಗಳು ಎಫ್-ವಾಹಕಗಳಿಗಿಂತ ಹೆಚ್ಚು ಅನುಕೂಲಕರ ಮತ್ತು ಸಂಕ್ಷಿಪ್ತ ಮಾರ್ಗವಾಗಿದೆ". ಸಮಾನತೆಗಳು ಮತ್ತು ಅಸಮಾನತೆಗಳು ಪಾಲಿಟೋಪ್ನ ಎಫ್-ವಾಹಕದ ಗುಣಾಂಕಗಳ ನಡುವಿನ ಅತ್ಯಂತ ಪ್ರಮುಖ ಸಂಬಂಧವೆಂದರೆ ಯೂಲರ್ನ ಸೂತ್ರ ‡ (−1) ಇಫಿ = 0, ಅಲ್ಲಿ ಮೊತ್ತದ ಪದಗಳು ವಿಸ್ತೃತ ಎಫ್-ವಾಹಕದ ಗುಣಾಂಕಗಳ ಮೇಲೆ ವ್ಯಾಪ್ತಿಯನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಮೂರು ಆಯಾಮಗಳಲ್ಲಿ, ವಿಸ್ತೃತ f-ವಾಹಕದ (1, v, e, f, 1) ಎಡ ಮತ್ತು ಬಲ ತುದಿಗಳಲ್ಲಿ ಎರಡು 1 ಗಳನ್ನು ಸಮೀಕರಣದ ಬಲಭಾಗಕ್ಕೆ ಚಲಿಸುವುದರಿಂದ ಈ ಗುರುತನ್ನು ಹೆಚ್ಚು ಪರಿಚಿತ ರೂಪವಾದ v − e + f = 2 ಆಗಿ ಪರಿವರ್ತಿಸುತ್ತದೆ. ಮೂರು ಆಯಾಮದ ಪಾಲಿಹೆಡ್ರಾನ್ನ ಪ್ರತಿಯೊಂದು ಅಂಶವು ಕನಿಷ್ಠ ಮೂರು ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವುದರಿಂದ, ಅದು 2e ≤ 3f ಅನ್ನು ಎರಡು ಬಾರಿ ಎಣಿಸುವ ಮೂಲಕ ಅನುಸರಿಸುತ್ತದೆ ಮತ್ತು ಯೂಲರ್ನ ಸೂತ್ರದಿಂದ e ಮತ್ತು f ಅನ್ನು ತೊಡೆದುಹಾಕಲು ಈ ಅಸಮಾನತೆಯನ್ನು ಬಳಸುವುದರಿಂದ ಮತ್ತಷ್ಟು ಅಸಮಾನತೆಗಳಿಗೆ ಕಾರಣವಾಗುತ್ತದೆ e ≤ 3v−6 ಮತ್ತು f ≤ 2v−4. ದ್ವಂದ್ವತೆಯಿಂದ, e ≤ 3f−6 ಮತ್ತು v ≤ 2f−4. ಈ ಸಮಾನತೆಗಳು ಮತ್ತು ಅಸಮಾನತೆಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುವ ಯಾವುದೇ 3-ಆಯಾಮದ ಪೂರ್ಣಾಂಕ ವಾಹಕವು ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಹೆಡ್ರಾನ್ನ f-ವಾಹಕವಾಗಿದೆ ಎಂದು ಸ್ಟೈನಿಟ್ಜ್ನ ಪ್ರಮೇಯವು ಅನುಸರಿಸುತ್ತದೆ. ಹೆಚ್ಚಿನ ಆಯಾಮಗಳಲ್ಲಿ, ಪಾಲಿಟೋಪ್ನ ಮುಖಗಳ ಸಂಖ್ಯೆಗಳ ನಡುವಿನ ಇತರ ಸಂಬಂಧಗಳು ಸಹ ಮುಖ್ಯವಾಗುತ್ತವೆ, ಇದರಲ್ಲಿ ಡೆಹ್ನ್-ಸೋಮರ್ವಿಲ್ಲೆ ಸಮೀಕರಣಗಳು ಸೇರಿವೆ, ಇದನ್ನು ಸರಳವಾದ ಪಾಲಿಟೋಪ್ಗಳ ಎಚ್-ವಾಹಕಗಳ ಪರಿಭಾಷೆಯಲ್ಲಿ ವ್ಯಕ್ತಪಡಿಸಲಾಗುತ್ತದೆ, ಇದು ಎಲ್ಲಾ ಕೆಗಳಿಗೆ ಸರಳವಾದ ರೂಪವಾದ ಎಚ್. ಕೆ = ಎಚ್. ಡಿ-ಕೆ ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಕೆ = 0 ಹೊಂದಿರುವ ಈ ಸಮೀಕರಣಗಳ ಉದಾಹರಣೆಯು ಯೂಲರ್ನ ಸೂತ್ರಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ ಆದರೆ ಡಿ> 3 ಗೆ ಈ ಸಮೀಕರಣಗಳ ಇತರ ನಿದರ್ಶನಗಳು ಪರಸ್ಪರ ರೇಖೀಯವಾಗಿ ಸ್ವತಂತ್ರವಾಗಿರುತ್ತವೆ ಮತ್ತು ಎಚ್-ವಾಹಕಗಳನ್ನು (ಮತ್ತು ಆದ್ದರಿಂದ ಎಫ್-ವಾಹಕಗಳನ್ನು) ಹೆಚ್ಚುವರಿ ರೀತಿಯಲ್ಲಿ ನಿರ್ಬಂಧಿಸುತ್ತವೆ. ಪಾಲಿಟೋಪ್ ಮುಖದ ಎಣಿಕೆಗಳ ಮೇಲಿನ ಮತ್ತೊಂದು ಪ್ರಮುಖ ಅಸಮಾನತೆಯನ್ನು ಮೇಲಿನ ಬೌಂಡ್ ಪ್ರಮೇಯವು ನೀಡುತ್ತದೆ, ಇದನ್ನು ಮೊದಲು ಈ ಮೂಲಕ ಸಾಬೀತುಪಡಿಸಲಾಗಿದೆ, ಇದು n ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಡಿ-ಆಯಾಮದ ಪಾಲಿಟೋಪ್ ಯಾವುದೇ ಇತರ ಆಯಾಮದ ಅನೇಕ ಮುಖಗಳನ್ನು ಹೊಂದಿರಬಹುದು ಎಂದು ಹೇಳುತ್ತದೆ, ಅದೇ ಸಂಖ್ಯೆಯ ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ನೆರೆಯ ಪಾಲಿಟೋಪ್ಃ ಅಲ್ಲಿ ನಕ್ಷತ್ರವು ಎಂದರೆ d ಸಮವಾಗಿದ್ದಾಗ ಮೊತ್ತದ ಅಂತಿಮ ಪದವನ್ನು ಅರ್ಧದಷ್ಟು ಮಾಡಬೇಕು ಎಂದರ್ಥ. ಲಕ್ಷಣರಹಿತವಾಗಿ, ಇದು ಎಲ್ಲಾ ಆಯಾಮಗಳ ಹೆಚ್ಚಿನ ಮುಖಗಳಿವೆ ಎಂದು ಸೂಚಿಸುತ್ತದೆ. ನಾಲ್ಕು ಆಯಾಮಗಳಲ್ಲಿಯೂ ಸಹ, ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಟೋಪ್ಗಳ ಸಂಭವನೀಯ f-ವಾಹಕಗಳ ಸಮೂಹವು ನಾಲ್ಕು ಆಯಾಮದ ಪೂರ್ಣಾಂಕ ಜಾಲರಿಯ ಕನ್ವೆಕ್ಸ್ ಉಪವಿಭಾಗವನ್ನು ರೂಪಿಸುವುದಿಲ್ಲ ಮತ್ತು ಈ ವಾಹಕಗಳ ಸಂಭವನೀಯ ಮೌಲ್ಯಗಳ ಬಗ್ಗೆ ಹೆಚ್ಚು ತಿಳಿದಿಲ್ಲ. ಗ್ರಾಫ್-ಸೈದ್ಧಾಂತಿಕ ಗುಣಲಕ್ಷಣಗಳು ಪಾಲಿಟೋಪ್ಗಳ ಮುಖಗಳ ಸಂಖ್ಯೆಯನ್ನು ತನಿಖೆ ಮಾಡುವುದರ ಜೊತೆಗೆ, ಸಂಶೋಧಕರು ಅವುಗಳ ಇತರ ಸಂಯೋಜಿತ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಅಧ್ಯಯನ ಮಾಡಿದ್ದಾರೆ, ಉದಾಹರಣೆಗೆ ಪಾಲಿಟೋಪ್ಗಳ ಶೃಂಗಗಳು ಮತ್ತು ಅಂಚುಗಳಿಂದ ಪಡೆದ ಗ್ರಾಫ್ಗಳ ವಿವರಣೆಗಳು (ಅವುಗಳ 1-ಅಸ್ಥಿಪಂಜರ). ಯಾವುದೇ ಡಿ-ಆಯಾಮದ ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಟೋಪ್ನಿಂದ ಈ ರೀತಿಯಲ್ಲಿ ಪಡೆದ ಗ್ರಾಫ್ ಡಿ-ವೆರ್ಟೆಕ್ಸ್-ಸಂಪರ್ಕಿತವಾಗಿದೆ ಎಂದು ಬಾಲಿನ್ಸ್ಕಿಯ ಪ್ರಮೇಯವು ಹೇಳುತ್ತದೆ. ತ್ರಿ-ಆಯಾಮದ ಪಾಲಿಹೆಡ್ರಾದ ಸಂದರ್ಭದಲ್ಲಿ, ಪಾಲಿಹೆಡ್ರಾದ ರೇಖಾಚಿತ್ರಗಳನ್ನು ನಿಖರವಾಗಿ ನಿರೂಪಿಸಲು ಈ ಗುಣ ಮತ್ತು ಸಮತಲತೆಯನ್ನು ಬಳಸಬಹುದುಃ ಸ್ಟೈನಿಟ್ಜ್ನ ಪ್ರಮೇಯವು, ಜಿ 3-ವೆರ್ಟೆಕ್ಸ್-ಸಂಪರ್ಕಿತ ಪ್ಲ್ಯಾನರ್ ರೇಖಾಚಿತ್ರವಾಗಿದ್ದರೆ ಮಾತ್ರ ಜಿ ಮೂರು-ಆಯಾಮದ ಪಾಲಿಹೆಡ್ರಾನ್ನ ಅಸ್ಥಿಪಂಜರವಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಒಂದು ಸರಳ ಪಾಲಿಟೋಪ್ನ ಮುಖದ ರಚನೆಯನ್ನು ಅದರ ರೇಖಾಚಿತ್ರದಿಂದ ಪುನರ್ನಿರ್ಮಿಸಬಹುದು ಎಂದು (ಹಿಂದೆ ಮೈಕಾ ಪರ್ಲೆಸ್ ಊಹಿಸಿದ) ಒಂದು ಪ್ರಮೇಯವು ಹೇಳುತ್ತದೆ. ಅಂದರೆ, ನೀಡಲಾದ ನಿರ್ದೇಶಿಸದ ರೇಖಾಚಿತ್ರವು ಸರಳ ಪಾಲಿಟೋಪ್ನ ಅಸ್ಥಿಪಂಜರವಾಗಿದ್ದರೆ, ಇದು ನಿಜವಾಗಿರುವ ಒಂದೇ ಒಂದು ಪಾಲಿಟೋಪ್ (ಸಂಯೋಜಿತ ಸಮಾನತೆಯವರೆಗೆ) ಇರುತ್ತದೆ. ಇದು (ಸರಳವಲ್ಲದ) ನೆರೆಯ ಪಾಲಿಟೋಪ್ಗಳಿಗೆ ತದ್ವಿರುದ್ಧವಾಗಿದೆ, ಅದರ ಗ್ರಾಫ್ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ ಆಗಿದೆ; ಒಂದೇ ಗ್ರಾಫ್ಗೆ ಅನೇಕ ವಿಭಿನ್ನ ನೆರೆಯ ಪಾಲಿಟೋಪ್ಗಳು ಇರಬಹುದು. ಅನನ್ಯ ಸಿಂಕ್ ದೃಷ್ಟಿಕೋನಗಳನ್ನು ಆಧರಿಸಿದ ಈ ಪ್ರಮೇಯದ ಮತ್ತೊಂದು ಪುರಾವೆಯನ್ನು ಅವರು ನೀಡಿದರು, ಮತ್ತು ಸರಳವಾದ ಪಾಲಿಟೋಪ್ಗಳ ಮುಖದ ಜಾಲರಿಗಳನ್ನು ಅವುಗಳ ಗ್ರಾಫ್ಗಳಿಂದ ಪುನರ್ನಿರ್ಮಿಸಲು ಬಹುಪದ ಸಮಯದ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪಡೆಯಲು ಈ ಪ್ರಮೇಯವನ್ನು ಹೇಗೆ ಬಳಸುವುದು ಎಂಬುದನ್ನು ತೋರಿಸಿದರು. ಆದಾಗ್ಯೂ, ನೀಡಲಾದ ಗ್ರಾಫ್ ಅಥವಾ ಜಾಲರಿಯನ್ನು ಸರಳ ಪಾಲಿಟೋಪ್ನ ಮುಖದ ಜಾಲಿಯಾಗಿ ಅರಿತುಕೊಳ್ಳಬಹುದೇ ಎಂದು ಪರೀಕ್ಷಿಸುವುದು (ಧ್ರುವೀಯತೆಯಿಂದ) ಸರಳವಾದ ಪಾಲಿಟೋಪ್ಗಳ ಸಾಕ್ಷಾತ್ಕಾರಕ್ಕೆ ಸಮಾನವಾಗಿದೆ, ಇದು ವಾಸ್ತವದ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತಕ್ಕೆ ಸಂಪೂರ್ಣವಾಗಿದೆ ಎಂದು ತೋರಿಸಲಾಗಿದೆ. ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ಗಾಗಿ ಸಿಂಪ್ಲೆಕ್ಸ್ ವಿಧಾನದ ಸಂದರ್ಭದಲ್ಲಿ, ಪಾಲಿಟೋಪ್ನ ವ್ಯಾಸವನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳುವುದು ಮುಖ್ಯವಾಗಿದೆ, ಯಾವುದೇ ಇತರ ಶೃಂಗದಿಂದ ಒಂದು ಮಾರ್ಗದಿಂದ ಯಾವುದೇ ಶೃಂಗವನ್ನು ತಲುಪಲು ಅಗತ್ಯವಿರುವ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಅಂಚುಗಳು. ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂನ ರೇಖೀಯ ಅಸಮಾನತೆಗಳ ವ್ಯವಸ್ಥೆಯು ಪ್ರೋಗ್ರಾಂಗೆ ಎಲ್ಲಾ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಪರಿಹಾರಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಪಾಲಿಟೋಪ್ನ ಅಂಶಗಳನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತದೆ ಮತ್ತು ಸಿಂಪ್ಲೆಕ್ಸ್ ವಿಧಾನವು ಈ ಪಾಲಿಟೋಪ್ನಲ್ಲಿನ ಮಾರ್ಗವನ್ನು ಅನುಸರಿಸುವ ಮೂಲಕ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ. ಹೀಗಾಗಿ, ವ್ಯಾಸವು ಈ ವಿಧಾನಕ್ಕೆ ಅಗತ್ಯವಿರುವ ಹಂತಗಳ ಸಂಖ್ಯೆಯ ಮೇಲೆ ಕಡಿಮೆ ಮಿತಿಯನ್ನು ಒದಗಿಸುತ್ತದೆ. ಈಗ ನಿರಾಕರಿಸಲಾಗಿರುವ ಹಿರ್ಷ್ ಊಹೆಯು, ಸ್ಥಿರ ಆಯಾಮ ಮತ್ತು ಅಂಶಗಳ ಸಂಖ್ಯೆಯೊಂದಿಗೆ ಪಾಲಿಟೋಪ್ನ ವ್ಯಾಸವು ಎಷ್ಟು ದೊಡ್ಡದಾಗಿರಬಹುದು ಎಂಬುದರ ಮೇಲೆ ಬಲವಾದ (ರೇಖೀಯ) ಬಂಧವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಅವುಗಳ ವ್ಯಾಸದ ಮೇಲಿನ ಗಡಿಯನ್ನು ದುರ್ಬಲ (ಅರೆ-ಬಹುಪದ ಮತ್ತು) ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಜೊತೆಗೆ ಪಾಲಿಟೋಪ್ಗಳ ವಿಶೇಷ ವರ್ಗಗಳಿಗೆ ಹಿರ್ಷ್ ಊಹೆಯ ಪುರಾವೆಗಳಿವೆ. ಕಂಪ್ಯೂಟೇಶನಲ್ ಗುಣಲಕ್ಷಣಗಳು ಒಂದು ನಿರ್ದಿಷ್ಟ ಪಾಲಿಟೋಪ್ನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯು ಕೆಲವು ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆ k ಯಿಂದ ಸುತ್ತುವರಿಯಲ್ಪಟ್ಟಿದೆಯೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವುದು ಕಂಪ್ಯೂಟೇಶನಲ್ ಆಗಿ ಕಷ್ಟಕರವಾದ ಸಮಸ್ಯೆಯಾಗಿದೆ ಮತ್ತು ಸಂಕೀರ್ಣತೆಯ ವರ್ಗ ಪಿಪಿಗೆ ಸಂಪೂರ್ಣವಾಗಿದೆ. 0-1 ಪಾಲಿಟೋಪ್ಗಳ ಮುಖಗಳು ಸಂಯೋಜನೆಯ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳ ಪರಿಹಾರಗಳಿಗೆ ಅನುಗುಣವಾದ ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಪಾಲಿಟೋಪ್ಗಳ ಮುಖಗಳನ್ನು ನಿಖರವಾಗಿ ವಿವರಿಸಲು ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ಗೆ ಕತ್ತರಿಸುವ-ಸಮತಲ ವಿಧಾನಗಳ ಸಂದರ್ಭದಲ್ಲಿ ಇದು ಮುಖ್ಯವಾಗಿದೆ. ಸಾಮಾನ್ಯವಾಗಿ, ಈ ಸಮಸ್ಯೆಗಳು ಬೈನರಿ ವಾಹಕಗಳಿಂದ ವಿವರಿಸಬಹುದಾದ ಪರಿಹಾರಗಳನ್ನು ಹೊಂದಿವೆ, ಮತ್ತು ಅನುಗುಣವಾದ ಪಾಲಿಟೋಪ್ಗಳು ಎಲ್ಲಾ ಶೂನ್ಯ ಅಥವಾ ಒಂದಾಗಿರುವ ಶೃಂಗ ನಿರ್ದೇಶಾಂಕಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಉದಾಹರಣೆಗೆ, ಬಿರ್ಖೋಫ್ ಪಾಲಿಟೋಪ್ ಅನ್ನು ಪರಿಗಣಿಸಿ, ಇದು ಕ್ರಮಪಲ್ಲಟನೆ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳ ಕನ್ವೆಕ್ಸ್ ಸಂಯೋಜನೆಯಿಂದ ರೂಪುಗೊಳ್ಳಬಹುದಾದ n × n ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳ ಗುಂಪಾಗಿದೆ. ಸಮಾನವಾಗಿ, ಅದರ ಶೃಂಗಗಳನ್ನು ಸಂಪೂರ್ಣ ಉಭಯಪಕ್ಷೀಯ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಎಲ್ಲಾ ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಗಳನ್ನು ವಿವರಿಸುವಂತೆ ಯೋಚಿಸಬಹುದು, ಮತ್ತು ಈ ಪಾಲಿಟೋಪ್ನಲ್ಲಿನ ರೇಖೀಯ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯನ್ನು ಉಭಯಪಕ್ಷೀಯ ಕನಿಷ್ಠ ತೂಕದ ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಯ ಸಮಸ್ಯೆ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು. ಬಿರ್ಖೋಫ್-ವಾನ್ ನ್ಯೂಮನ್ ಪ್ರಮೇಯವು ಈ ಪಾಲಿಟೋಪ್ ಅನ್ನು ಎರಡು ರೀತಿಯ ರೇಖೀಯ ಅಸಮಾನತೆ ಅಥವಾ ಸಮಾನತೆಯಿಂದ ವಿವರಿಸಬಹುದು ಎಂದು ಹೇಳುತ್ತದೆ. ಮೊದಲನೆಯದಾಗಿ, ಪ್ರತಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಕೋಶಕ್ಕೆ, ಈ ಕೋಶವು ಋಣಾತ್ಮಕವಲ್ಲದ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದೆ ಎಂಬ ನಿರ್ಬಂಧವಿದೆ. ಮತ್ತು ಎರಡನೆಯದಾಗಿ, ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಪ್ರತಿ ಸಾಲು ಅಥವಾ ಕಾಲಮ್ಗೆ, ಆ ಸಾಲು ಅಥವಾ ಕಾಲಮ್ನಲ್ಲಿರುವ ಕೋಶಗಳ ಮೊತ್ತವು ಒಂದಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ ಎಂಬ ನಿರ್ಬಂಧವಿದೆ. ಸಾಲು ಮತ್ತು ಕಾಲಮ್ನ ನಿರ್ಬಂಧಗಳು ಬಿರ್ಖೋಫ್ ಪಾಲಿಟೋಪ್ ಇರುವ n2−2n + 1 ಆಯಾಮದ ರೇಖೀಯ ಉಪಕ್ಷೇತ್ರವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತವೆ ಮತ್ತು ಋಣಾತ್ಮಕವಲ್ಲದ ನಿರ್ಬಂಧಗಳು ಆ ಉಪಕ್ಷೇತ್ರದೊಳಗೆ ಬಿರ್ಖೋಫ್ ಪಾಲಿಟೋಪ್ನ ಅಂಶಗಳನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತವೆ. ಆದಾಗ್ಯೂ, ಬಿರ್ಖೋಫ್ ಪಾಲಿಟೋಪ್ ಅಸಾಮಾನ್ಯವಾಗಿದ್ದು, ಅದರ ಅಂಶಗಳ ಸಂಪೂರ್ಣ ವಿವರಣೆ ಲಭ್ಯವಿದೆ. ಅನೇಕ ಇತರ 0-1 ಪಾಲಿಟೋಪ್ಗಳಿಗೆ, ಘಾತೀಯವಾಗಿ ಅನೇಕ ಅಥವಾ ಸೂಪರೆಕ್ಸ್ಪೊನೆನ್ಶಿಯಲ್ ಆಗಿ ಅನೇಕ ಅಂಶಗಳಿವೆ, ಮತ್ತು ಅವುಗಳ ಅಂಶಗಳ ಭಾಗಶಃ ವಿವರಣೆಗಳು ಮಾತ್ರ ಲಭ್ಯವಿವೆ. ಅಮೂರ್ತ ಪಾಲಿಟೋಪ್ ಸಂಯೋಜಿತ ಸಂವಹನ ಬೀಜಗಣಿತ ಮ್ಯಾಟ್ರಾಯಿಡ್ ಪಾಲಿಟೋಪ್ ಆರ್ಡರ್ ಪಾಲಿಟೋಪ್ ಸರಳ ಗೋಳ ಸ್ಥಿರ ಹೊಂದಾಣಿಕೆಯ ಪಾಲಿಟೋಪ್ ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳನ್ನು ಸಹ ನೋಡಿ. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ಬಾಹ್ಯ ಕೊಂಡಿಗಳು.