Barnette's conjecture
ಬಾರ್ನೆಟ್ರ ಊಹೆಯು ಗ್ರಾಫ್ಗಳಲ್ಲಿರುವ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರಗಳಿಗೆ ಸಂಬಂಧಿಸಿದ ಗಣಿತಶಾಸ್ತ್ರದ ಒಂದು ಶಾಖೆಯಾದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಬಗೆಹರಿಯದ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಇದನ್ನು ಡೇವಿಸ್ನ ಕ್ಯಾಲಿಫೋರ್ನಿಯಾ ವಿಶ್ವವಿದ್ಯಾನಿಲಯದ ಪ್ರೊಫೆಸರ್ ಎಮೆರಿಟಸ್ ಡೇವಿಡ್ ಡಬ್ಲ್ಯೂ. ಬಾರ್ನೆಟ್ರ ಹೆಸರನ್ನು ಇಡಲಾಗಿದೆ; ಪ್ರತಿ ಶೃಂಗಕ್ಕೆ ಮೂರು ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ಪ್ರತಿ ಉಭಯಪಕ್ಷೀಯ ಪಾಲಿಹೆಡ್ರಲ್ ಗ್ರಾಫ್ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಅದು ಹೇಳುತ್ತದೆ. ವ್ಯಾಖ್ಯಾನಗಳು ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ ಎನ್ನುವುದು ಯಾವುದೇ ಕ್ರಾಸಿಂಗ್ಗಳಿಲ್ಲದೆ ಯೂಕ್ಲಿಡಿಯನ್ ಸಮತಲದಲ್ಲಿ ಹುದುಗಿಸಬಹುದಾದ ಒಂದು ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ ಆಗಿದೆ. ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ ಅನ್ನು ಪಾಲಿಹೆಡ್ರಲ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಅದು 3-ವೆರ್ಟೆಕ್ಸ್-ಸಂಪರ್ಕಿತವಾಗಿದ್ದರೆ ಮಾತ್ರ, ಅಂದರೆ, ಎರಡು ಶೃಂಗಗಳು ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲದಿದ್ದರೆ ಅದರ ತೆಗೆದುಹಾಕುವಿಕೆಯು ಉಳಿದ ಗ್ರಾಫ್ ಅನ್ನು ಸಂಪರ್ಕ ಕಡಿತಗೊಳಿಸುತ್ತದೆ. ಪ್ರತಿ ಅಂಚು ಪ್ರತಿ ಬಣ್ಣದ ಒಂದು ಅಂತಿಮ ಬಿಂದುವನ್ನು ಹೊಂದಿರುವಂತೆ ಅದರ ಶೃಂಗಗಳನ್ನು ಎರಡು ವಿಭಿನ್ನ ಬಣ್ಣಗಳಿಂದ ಬಣ್ಣ ಮಾಡಬಹುದಾದರೆ ರೇಖಾಚಿತ್ರವು ಉಭಯಪಕ್ಷೀಯವಾಗಿರುತ್ತದೆ. ಪ್ರತಿ ಶೃಂಗವು ನಿಖರವಾಗಿ ಮೂರು ಅಂಚುಗಳ ಅಂತಿಮ ಬಿಂದುವಾಗಿದ್ದರೆ ರೇಖಾಚಿತ್ರವು ಘನ (ಅಥವಾ 3-ನಿಯಮಿತ) ಆಗಿರುತ್ತದೆ. ಅಂತಿಮವಾಗಿ, ಅದರ ಪ್ರತಿಯೊಂದು ಶೃಂಗಗಳ ಮೂಲಕ ನಿಖರವಾಗಿ ಒಮ್ಮೆಯಾದರೂ ಹಾದುಹೋಗುವ ಚಕ್ರವಿದ್ದರೆ ರೇಖಾಚಿತ್ರವು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಆಗಿರುತ್ತದೆ. ಬಾರ್ನೆಟ್ರ ಊಹೆಯು ಪ್ರತಿ ಕ್ಯೂಬಿಕ್ ಬೈಪಾರ್ಟೈಟ್ ಪಾಲಿಹೆಡ್ರಲ್ ಗ್ರಾಫ್ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಎಂದು ಹೇಳುತ್ತದೆ. ಸ್ಟೈನಿಟ್ಜ್ನ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ ಒಂದು ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಹೆಡ್ರಾನ್ನ ಅಂಚುಗಳು ಮತ್ತು ಶೃಂಗಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ ಮತ್ತು ಅದು ಪಾಲಿಹೆಡ್ರಲ್ ಆಗಿದ್ದರೆ ಮಾತ್ರ. ಮೂರು ಆಯಾಮದ ಪಾಲಿಹೆಡ್ರನ್ ಒಂದು ಸರಳ ಪಾಲಿಹೆಡ್ರನ್ ಆಗಿದ್ದರೆ ಮಾತ್ರ ಘನ ನಕ್ಷೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಮತ್ತು, ಗ್ರಾಫ್ನ ಪ್ಲ್ಯಾನರ್ ಎಂಬೆಡಿಂಗ್ನಲ್ಲಿ, ಎಲ್ಲಾ ಮುಖದ ಚಕ್ರಗಳು ಸಮ ಉದ್ದವನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ ಉಭಯಪಕ್ಷೀಯವಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಬಾರ್ನೆಟ್ರ ಊಹೆಯನ್ನು ಸಮಾನ ರೂಪದಲ್ಲಿ ಹೇಳಬಹುದುಃ ಮೂರು ಆಯಾಮದ ಸರಳ ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಹೆಡ್ರನ್ ಅದರ ಪ್ರತಿಯೊಂದು ಮುಖದ ಮೇಲೆ ಸಮ ಸಂಖ್ಯೆಯ ಅಂಚುಗಳನ್ನು ಹೊಂದಿದೆ ಎಂದು ಭಾವಿಸೋಣ. ನಂತರ, ಊಹೆಯ ಪ್ರಕಾರ, ಪಾಲಿಹೆಡ್ರಾನ್ನ ಗ್ರಾಫ್ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರವನ್ನು ಹೊಂದಿದೆ. ಪ್ರತಿ ಘನ ಪಾಲಿಹೆಡ್ರಲ್ ಗ್ರಾಫ್ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಎಂದು ಇತಿಹಾಸವು ಊಹಿಸಿದೆ; ಇದನ್ನು ಟೈಟ್ನ ಊಹೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಇದನ್ನು 46 ಶೃಂಗಗಳೊಂದಿಗೆ ಪ್ರತಿ-ಉದಾಹರಣೆಯನ್ನು ನಿರ್ಮಿಸಿದವರು ನಿರಾಕರಿಸಿದರು; ಇತರ ಸಂಶೋಧಕರು ನಂತರ ಇನ್ನೂ ಸಣ್ಣ ಪ್ರತಿ-ಉದಾಹರಣೆಗಳನ್ನು ಕಂಡುಕೊಂಡರು. ಆದಾಗ್ಯೂ, ಈ ತಿಳಿದಿರುವ ಪ್ರತಿ-ಉದಾಹರಣೆಗಳಲ್ಲಿ ಯಾವುದೂ ಉಭಯಪಕ್ಷೀಯವಾಗಿಲ್ಲ. ಟುಟ್ಟೆ ಸ್ವತಃ ಪ್ರತಿ ಘನ 3-ಸಂಪರ್ಕಿತ ಉಭಯಪಕ್ಷೀಯ ರೇಖಾಚಿತ್ರವು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಎಂದು ಊಹಿಸಿದರು, ಆದರೆ ಇದಕ್ಕೆ ವಿರುದ್ಧವಾದ ಉದಾಹರಣೆಯಾದ ಹಾರ್ಟನ್ ರೇಖಾಚಿತ್ರದ ಆವಿಷ್ಕಾರದಿಂದ ಇದು ಸುಳ್ಳು ಎಂದು ತೋರಿಸಲಾಗಿದೆ. ಪ್ರತಿ ಉಭಯಪಕ್ಷೀಯ ಘನ ಪಾಲಿಹೆಡ್ರನ್ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಆಗಿದೆ, ಅಥವಾ, ಸಮಾನವಾಗಿ, ಟೈಟ್ನ ಊಹೆಗೆ ಪ್ರತಿ ಪ್ರತಿ-ಉದಾಹರಣೆಯು ಉಭಯಪಕ್ಷೀಯವಲ್ಲ ಎಂದು ಹೇಳುವ ಮೂಲಕ ಟೈಟ್ ಮತ್ತು ಟುಟ್ಟೆಯ ಊಹೆಗಳ ದುರ್ಬಲ ಸಂಯೋಜನೆಯನ್ನು ಪ್ರಸ್ತಾಪಿಸಿದರು. ಸಮಾನವಾದ ರೂಪಗಳು ಬಾರ್ನೆಟ್ನ ಊಹೆಯು ಮೇಲ್ನೋಟಕ್ಕೆ ಬಲವಾದ ಹೇಳಿಕೆಗೆ ಸಮಾನವಾಗಿದೆ ಎಂದು ತೋರಿಸಿದವು, ಉಭಯಪಕ್ಷೀಯ ಘನ ಪಾಲಿಹೆಡ್ರಾನ್ನ ಒಂದೇ ಮುಖದಲ್ಲಿರುವ ಪ್ರತಿ ಎರಡು ಅಂಚುಗಳಿಗೆ e ಮತ್ತು f ಗೆ, e ಅನ್ನು ಒಳಗೊಂಡಿರುವ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರವಿದೆ ಆದರೆ f ಅನ್ನು ಹೊಂದಿಲ್ಲ. ಸ್ಪಷ್ಟವಾಗಿ, ಈ ಹೇಳಿಕೆಯು ನಿಜವಾಗಿದ್ದರೆ, ಪ್ರತಿ ಉಭಯಪಕ್ಷೀಯ ಘನ ಪಾಲಿಹೆಡ್ರಾನ್ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರವನ್ನು ಹೊಂದಿರುತ್ತದೆಃ ಕೇವಲ e ಮತ್ತು f ಅನ್ನು ಅನಿಯಂತ್ರಿತವಾಗಿ ಆಯ್ಕೆ ಮಾಡಿ. ಇತರ ದಿಕ್ಕುಗಳಲ್ಲಿ, ಮೂಲ ಬಾರ್ನೆಟ್ ಊಹೆಗೆ ಪ್ರತಿಯಾಗಿ ಉದಾಹರಣೆಯನ್ನು ಪರಿವರ್ತಿಸಬಹುದು ಎಂದು ಕೆಲ್ಮನ್ ತೋರಿಸಿದರು. ಪ್ರತಿ ಕ್ಯೂಬಿಕ್ ಬೈಪಾರ್ಟೈಟ್ ಪಾಲಿಹೆಡ್ರಲ್ ಗ್ರಾಫ್ನ ಡ್ಯುಯಲ್ನ ಶೃಂಗಗಳನ್ನು ಎರಡು ಉಪಗುಂಪುಗಳಾಗಿ ವಿಂಗಡಿಸಬಹುದು ಎಂಬ ಹೇಳಿಕೆಗೆ ಬಾರ್ನೆಟ್ನ ಊಹೆಯು ಸಮನಾಗಿರುತ್ತದೆ, ಅದರ ಪ್ರೇರಿತ ಉಪಗುಂಪುಗಳು ಮರಗಳಾಗಿವೆ. ಡ್ಯುಯಲ್ ಗ್ರಾಫ್ನಲ್ಲಿ ಅಂತಹ ವಿಭಜನೆಯಿಂದ ಉಂಟಾಗುವ ಕಡಿತವು ಪ್ರೈಮಲ್ ಗ್ರಾಫ್ನಲ್ಲಿ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರಕ್ಕೆ ಅನುರೂಪವಾಗಿದೆ. ಭಾಗಶಃ ಫಲಿತಾಂಶಗಳು ಬಾರ್ನೆಟ್ರ ಊಹೆಯ ಸತ್ಯವು ತಿಳಿದಿಲ್ಲವಾದರೂ, 86ಕ್ಕಿಂತ ಕಡಿಮೆ ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಯಾವುದೇ ಪ್ರತಿ-ಉದಾಹರಣೆಗಳಿಲ್ಲ ಎಂದು ಗಣನೆಯ ಪ್ರಯೋಗಗಳು ತೋರಿಸಿವೆ. ಬಾರ್ನೆಟ್ನ ಊಹೆ ಸುಳ್ಳು ಎಂದು ಸಾಬೀತಾದರೆ, ಬೈಪಾರ್ಟೈಟ್ ಕ್ಯೂಬಿಕ್ ಪಾಲಿಹೆಡ್ರನ್ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಆಗಿದೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸಲು ಅದನ್ನು ಎನ್ಪಿ-ಪೂರ್ಣ ಎಂದು ತೋರಿಸಬಹುದು. ಸಮತಟ್ಟಾದ ನಕ್ಷೆಯು ಉಭಯಪಕ್ಷೀಯವಾಗಿದ್ದರೆ ಮತ್ತು ಘನವಾಗಿದ್ದರೆ ಆದರೆ ಸಂಪರ್ಕ 2 ಮಾತ್ರ ಇದ್ದರೆ, ಅದು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಅಲ್ಲದದ್ದಾಗಿರಬಹುದು, ಮತ್ತು ಈ ನಕ್ಷೆಗಳಿಗೆ ಹ್ಯಾಮಿಲ್ಟೋನಿಸಿಟಿಯನ್ನು ಪರೀಕ್ಷಿಸಲು ಅದು ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿರುತ್ತದೆ. ಮತ್ತೊಂದು ಫಲಿತಾಂಶವನ್ನು ಈ ರೀತಿ ಪಡೆಯಲಾಯಿತುಃ ಪ್ರತಿ ಕೆಂಪು-ಹಸಿರು ಚಕ್ರವು 4ನೇ ಹಂತದ ಶೃಂಗವನ್ನು ಹೊಂದಿರುವಂತೆ, ನೀಲಿ, ಕೆಂಪು ಮತ್ತು ಹಸಿರು ಬಣ್ಣಗಳೊಂದಿಗೆ ಉಭಯ ನಕ್ಷೆಯು ಶೃಂಗ-ಬಣ್ಣವನ್ನು ಹೊಂದಿರಬಹುದಾದರೆ, ಪ್ರಾಥಮಿಕ ನಕ್ಷೆಯು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಆಗಿರುತ್ತದೆ. ಬಾರ್ನೆಟ್ನ ಸಂಬಂಧಿತ ಊಹೆಯು ಎಲ್ಲಾ ಮುಖಗಳು ಆರು ಅಥವಾ ಅದಕ್ಕಿಂತ ಕಡಿಮೆ ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ಪ್ರತಿ ಘನ ಪಾಲಿಹೆಡ್ರಲ್ ಗ್ರಾಫ್ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಎಂದು ಹೇಳುತ್ತದೆ. ಒಂದು ವ್ಯತಿರಿಕ್ತ ಉದಾಹರಣೆ ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ, ಅದು 177 ಕ್ಕೂ ಹೆಚ್ಚು ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರಬೇಕು ಎಂದು ಕಂಪ್ಯೂಟೇಶನಲ್ ಪ್ರಯೋಗಗಳು ತೋರಿಸಿವೆ. ಈ ಊಹೆಯು ಸಾಬೀತಾಗಿದೆ. ಈ ಎರಡು ಊಹೆಗಳ ಛೇದನವು ಎಲ್ಲಾ ಮುಖಗಳು ನಾಲ್ಕು ಅಥವಾ ಆರು ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ಪ್ರತಿ ಉಭಯಪಕ್ಷೀಯ ಘನ ಪಾಲಿಹೆಡ್ರಲ್ ಗ್ರಾಫ್ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಆಗಿರುತ್ತದೆ. ಇದು ನಿಜವೆಂದು ಸಾಬೀತಾಯಿತು. ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳು; ಸೈಂಟಿಫಿಕ್ ಪೇಪರ್ಸ್, ಸಂಪುಟದಲ್ಲಿ ಮರುಮುದ್ರಣಗೊಂಡಿದೆ. II, pp. 85-98 ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ಓಪನ್ ಪ್ರಾಬ್ಲಮ್ ಗಾರ್ಡನ್ನಲ್ಲಿ ಬಾರ್ನೆಟ್ರ ಕಾನ್ಸೆಕ್ಟರ್, ರಾಬರ್ಟ್ ಸಮಲ್, 2007. ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಪರಿಹರಿಸಲಾಗದ ಸಮಸ್ಯೆಗಳ ಊಹೆಗಳು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಮಾರ್ಗಗಳು ಮತ್ತು ಚಕ್ರಗಳನ್ನು ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳು