Burr–Erdős conjecture
ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ, ಬರ್-ಎರ್ಡೋಸ್ ಊಹೆಯು ರಾಮ್ಸೇ ಸಂಖ್ಯೆಯ ವಿರಳ ಗ್ರಾಫ್ಗಳಿಗೆ ಸಂಬಂಧಿಸಿದ ಒಂದು ಸಮಸ್ಯೆಯಾಗಿತ್ತು. ಈ ಊಹೆಗೆ ಸ್ಟೀಫನ್ ಬರ್ ಮತ್ತು ಪಾಲ್ ಎರ್ಡೋಸ್ ಅವರ ಹೆಸರನ್ನು ಇಡಲಾಗಿದೆ, ಮತ್ತು ಇದು ಎರ್ಡೋಸ್ ಅವರ ಹೆಸರಿನ ಅನೇಕ ಊಹೆಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ; ಯಾವುದೇ ವಿರಳವಾದ ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬದಲ್ಲಿನ ರಾಮ್ಸೇ ಸಂಖ್ಯೆಯ ಗ್ರಾಫ್ಗಳು ಗ್ರಾಫ್ನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯಲ್ಲಿ ರೇಖೀಯವಾಗಿ ಬೆಳೆಯಬೇಕು ಎಂದು ಅದು ಹೇಳುತ್ತದೆ. ಈ ಊಹೆಯನ್ನು ಚೂಂಗ್ಬಮ್ ಲೀ ಅವರು ಸಾಬೀತುಪಡಿಸಿದ್ದಾರೆ. ಹೀಗಾಗಿ ಇದು ಈಗ ಒಂದು ಪ್ರಮೇಯವಾಗಿದೆ. ವ್ಯಾಖ್ಯಾನಗಳು ಜಿ ಒಂದು ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ ಆಗಿದ್ದರೆ, ಜಿ ಯ ಅವನತಿಯು ಕನಿಷ್ಠ ಸಂಖ್ಯೆ ಪಿ ಆಗಿರುತ್ತದೆ, ಅಂದರೆ ಜಿ ಯ ಪ್ರತಿಯೊಂದು ಉಪವಿಭಾಗವು ಡಿಗ್ರಿ ಪಿ ಅಥವಾ ಅದಕ್ಕಿಂತ ಚಿಕ್ಕದಾದ ಶೃಂಗವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಅವನತಿ ಪಿ ಹೊಂದಿರುವ ಗ್ರಾಫ್ ಅನ್ನು ಪಿ-ಡಿಜೆನೆರೇಟ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಸಮಾನವಾಗಿ, ಪಿ-ಡಿಜೆನರೇಟ್ ಗ್ರಾಫ್ ಎಂಬುದು ಒಂದು ಗ್ರಾಫ್ ಆಗಿದ್ದು, ಇದನ್ನು ಪದೇ ಪದೇ ಡಿಗ್ರಿ ಪಿ ಅಥವಾ ಅದಕ್ಕಿಂತ ಚಿಕ್ಕದಾದ ಶೃಂಗವನ್ನು ತೆಗೆದುಹಾಕುವ ಮೂಲಕ ಖಾಲಿ ಗ್ರಾಫ್ಗೆ ಇಳಿಸಬಹುದು. ಯಾವುದೇ ಗ್ರಾಫ್ ಜಿಗೆ ಕನಿಷ್ಠ ಪೂರ್ಣಾಂಕ, ರಾಮ್ಸೇ ಸಂಖ್ಯೆ ಜಿ ಇದೆ ಎಂದು ರಾಮ್ಸೆಯ ಪ್ರಮೇಯವು ಅನುಸರಿಸುತ್ತದೆ, ಅಂದರೆ ಕನಿಷ್ಠ ಶೃಂಗಗಳ ಮೇಲೆ ಕೆಂಪು ಅಥವಾ ನೀಲಿ ಬಣ್ಣದ ಅಂಚುಗಳಿರುವ ಯಾವುದೇ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ ಜಿ ಯ ಏಕವರ್ಣದ ನಕಲನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ತ್ರಿಕೋನದ ರಾಮ್ಸೇ ಸಂಖ್ಯೆಯು 6 ಆಗಿದೆಃ ಆರು ಶೃಂಗಗಳ ಮೇಲೆ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ನ ಅಂಚುಗಳು ಕೆಂಪು ಅಥವಾ ನೀಲಿ ಬಣ್ಣದಲ್ಲಿದ್ದರೂ, ಯಾವಾಗಲೂ ಕೆಂಪು ತ್ರಿಕೋನ ಅಥವಾ ನೀಲಿ ತ್ರಿಕೋನ ಇರುತ್ತದೆ. 1973 ರಲ್ಲಿ, ಸ್ಟೀಫನ್ ಬರ್ ಮತ್ತು ಪಾಲ್ ಎರ್ಡೋಸ್ ಈ ಕೆಳಗಿನ ಊಹೆಯನ್ನು ಮಾಡಿದರುಃ ಪ್ರತಿ ಪೂರ್ಣಾಂಕ p ಗೆ ಸ್ಥಿರವಾದ cp ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ, ಇದರಿಂದಾಗಿ n ಶೃಂಗಗಳ ಮೇಲೆ ಯಾವುದೇ p-ಡಿಜನರೇಟ್ ಗ್ರಾಫ್ G ಗರಿಷ್ಠ cp n ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಅಂದರೆ, n-ವೆರ್ಟೆಕ್ಸ್ ಗ್ರಾಫ್ G ಯು p-ಡಿಜನರೇಟ್ ಆಗಿದ್ದರೆ, G ಯ ಏಕವರ್ಣದ ನಕಲು ಪ್ರತಿ ಎರಡು ಅಂಚುಗಳ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ನಲ್ಲಿ ಅಸ್ತಿತ್ವದಲ್ಲಿರಬೇಕು. ಸಂಪೂರ್ಣ ಊಹೆಯನ್ನು ಸಾಬೀತುಪಡಿಸುವ ಮೊದಲು, ಕೆಲವು ವಿಶೇಷ ಪ್ರಕರಣಗಳಲ್ಲಿ ಇದನ್ನು ಮೊದಲು ಇತ್ಯರ್ಥಪಡಿಸಲಾಯಿತು. ಇದು ಬೌಂಡೆಡ್-ಡಿಗ್ರಿ ಗ್ರಾಫ್ಗಳಿಗೆ ಸಾಬೀತಾಗಿದೆ; ಅವುಗಳ ಪುರಾವೆಯು ಸಿ. ಪಿ. ಯ ಹೆಚ್ಚಿನ ಮೌಲ್ಯಕ್ಕೆ ಕಾರಣವಾಯಿತು, ಮತ್ತು ಈ ಸ್ಥಿರಾಂಕಕ್ಕೆ ಸುಧಾರಣೆಗಳನ್ನು ಮತ್ತು ಮೂಲಕ ಮಾಡಲಾಯಿತು. ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ, p-ಜೋಡಿಸಬಹುದಾದ ಗ್ರಾಫ್ಗಳಿಗೆ ಈ ಊಹೆಯು ನಿಜವೆಂದು ತಿಳಿದುಬಂದಿದೆ, ಇದರಲ್ಲಿ ಸೀಮಿತವಾದ ಗರಿಷ್ಠ ಡಿಗ್ರಿ ಹೊಂದಿರುವ ಗ್ರಾಫ್ಗಳು, ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಕೆಪಿಯ ಉಪವಿಭಾಗವನ್ನು ಹೊಂದಿರದ ಗ್ರಾಫ್ಗಳು ಸೇರಿವೆ. ಇದು ಉಪವಿಭಕ್ತ ರೇಖಾಚಿತ್ರಗಳಿಗೂ ಹೆಸರುವಾಸಿಯಾಗಿದೆ, ಯಾವುದೇ ಎರಡು ಪಕ್ಕದ ಶೃಂಗಗಳು ಎರಡಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಮಟ್ಟವನ್ನು ಹೊಂದಿರದ ರೇಖಾಚಿತ್ರಗಳು. ಅನಿಯಂತ್ರಿತ ರೇಖಾಚಿತ್ರಗಳಿಗೆ, ರಾಮ್ಸೇ ಸಂಖ್ಯೆಯು ಸ್ವಲ್ಪಮಟ್ಟಿಗೆ ಸೂಪರ್ಲೀನಿಯರ್ ಆಗಿ ಬೆಳೆಯುವ ಕಾರ್ಯದಿಂದ ಸುತ್ತುವರೆದಿದೆ ಎಂದು ತಿಳಿದುಬಂದಿದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಯಾವುದೇ ಪಿ-ಡಿಜೆನೆರೇಟ್ ಎನ್-ವೆರ್ಟೆಕ್ಸ್ ಗ್ರಾಫ್ ಜಿ, ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳಿಗೆ ಸ್ಥಿರವಾದ ಸಿ. ಪಿ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ ಎಂದು ತೋರಿಸಿದೆ. .. .. .. .. .. .. .. .. ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ ರಾಮ್ಸೇ ಸಿದ್ಧಾಂತ ಬರ್-ಎರ್ಡೊಸ್ ಊಹೆಯ ಸಿದ್ಧಾಂತಗಳನ್ನು ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಸಾಬೀತುಪಡಿಸಿದ ಊಹೆಗಳು