Ramsey-Turán theory
ರಾಮ್ಸೇ-ಟುರಾನ್ ಸಿದ್ಧಾಂತವು ವಿಪರೀತ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಉಪಕ್ಷೇತ್ರವಾಗಿದೆ. ಇದು ರಾಮ್ಸೇಯ ಪ್ರಮೇಯ ಮತ್ತು ಟುರಾನ್ನ ಪ್ರಮೇಯದ ಸಾಮಾನ್ಯ ಸಾಮಾನ್ಯೀಕರಣಗಳನ್ನು ಅಧ್ಯಯನ ಮಾಡುತ್ತದೆ. ಸಂಕ್ಷಿಪ್ತವಾಗಿ ಹೇಳುವುದಾದರೆ, ರಾಮ್ಸೇ-ಟುರಾನ್ ಸಿದ್ಧಾಂತವು ಗ್ರಾಫ್ ಅದರ ಉಪಗ್ರಾಫ್ಗಳು ಮತ್ತು ರಚನೆಯ ಮೇಲಿನ ನಿರ್ಬಂಧಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುವ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಅಂಚುಗಳನ್ನು ಕೇಳುತ್ತದೆ. ಈ ಸಿದ್ಧಾಂತವು ವಿಪರೀತ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಉದ್ಭವಿಸುವ ಅನೇಕ ನೈಸರ್ಗಿಕ ಪ್ರಶ್ನೆಗಳನ್ನು ಸಂಘಟಿಸುತ್ತದೆ. ಈ ಸಿದ್ಧಾಂತದ ಕೇಂದ್ರ ವಿಚಾರಗಳನ್ನು ಔಪಚಾರಿಕಗೊಳಿಸಿದ ಮೊದಲ ಲೇಖಕರು 1969 ರಲ್ಲಿ ಎರ್ಡೋಸ್ ಮತ್ತು ಸೋಸ್ ಆಗಿದ್ದರು, ಆದಾಗ್ಯೂ ಗಣಿತಶಾಸ್ತ್ರಜ್ಞರು ಈ ಹಿಂದೆ ಅನೇಕ ರಾಮ್ಸೇ-ಟುರಾನ್-ರೀತಿಯ ಸಮಸ್ಯೆಗಳನ್ನು ತನಿಖೆ ಮಾಡಿದ್ದರು. ರಾಮ್ಸೇಯ ಪ್ರಮೇಯ ಮತ್ತು ಟುರಾನ್ನ ಪ್ರಮೇಯವಾದ ಎರಡು ಬಣ್ಣಗಳು ಮತ್ತು ಸಂಪೂರ್ಣ ನಕ್ಷೆಗಾಗಿ ರಾಮ್ಸೇಯ ಪ್ರಮೇಯವು, 1930ರಲ್ಲಿ ಅದರ ಮೂಲ ರೂಪದಲ್ಲಿ ಸಾಬೀತಾಯಿತು, ಯಾವುದೇ ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕಕ್ಕೆ ಎರಡು ಬಣ್ಣಗಳನ್ನು ಬಳಸುವ ಸಂಪೂರ್ಣ ನಕ್ಷೆಯ ಅಂಚುಗಳ ಯಾವುದೇ ಬಣ್ಣಕ್ಕೆ ಅದರ ಏಕವರ್ಣದ ಪ್ರತಿಯನ್ನು ಹೊಂದುವಷ್ಟು ದೊಡ್ಡ ಪೂರ್ಣಾಂಕವಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ, ಯಾವುದೇ ಗ್ರಾಫ್ಗಳಿಗೆ, ಒಂದು ಮಿತಿ ಇರುತ್ತದೆ ಮತ್ತು ಅದರ ಅಂಚುಗಳು ಬಣ್ಣಗಳೊಂದಿಗೆ ಅನಿಯಂತ್ರಿತವಾಗಿ ಬಣ್ಣಗೊಂಡಿದ್ದರೆ, ಕೆಲವರಿಗೆ th ಬಣ್ಣದಲ್ಲಿ a ಇರುತ್ತದೆ. 1941 ರಲ್ಲಿ ಸಾಬೀತಾದ ಟುರಾನ್ನ ಪ್ರಮೇಯವು, a ಅನ್ನು ಹೊಂದಿರದ ಶೃಂಗಗಳ ಮೇಲಿನ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಅಂಚುಗಳೊಂದಿಗೆ ಗ್ರಾಫ್ ಅನ್ನು ನಿರೂಪಿಸುತ್ತದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಎಲ್ಲಾ ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕಗಳಿಗೆ, ಉಪವಿಭಾಗವಾಗಿ ಹೊಂದಿರದ-ವೆರ್ಟೆಕ್ಸ್ ಗ್ರಾಫ್ನ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ ಮತ್ತು ಟುರಾನ್ ಗ್ರಾಫ್ನಿಂದ ಗರಿಷ್ಠವನ್ನು ಅನನ್ಯವಾಗಿ ಸಾಧಿಸಲಾಗುತ್ತದೆ ಎಂದು ಪ್ರಮೇಯವು ಹೇಳುತ್ತದೆ. ಈ ಎರಡೂ ಶ್ರೇಷ್ಠ ಫಲಿತಾಂಶಗಳು ಒಂದು ನಿರ್ದಿಷ್ಟ ಆಸ್ತಿಯನ್ನು ಹೊಂದುವ ಮೊದಲು ಗ್ರಾಫ್ ಎಷ್ಟು ದೊಡ್ಡದಾಗಿರಬಹುದು ಎಂಬುದರ ಬಗ್ಗೆ ಪ್ರಶ್ನೆಗಳನ್ನು ಕೇಳುತ್ತವೆ. ಆದಾಗ್ಯೂ, ಗಮನಾರ್ಹವಾದ ಶೈಲಿಯ ವ್ಯತ್ಯಾಸವಿದೆ. ಟುರಾನ್ನ ಪ್ರಮೇಯದಲ್ಲಿನ ವಿಪರೀತ ನಕ್ಷೆಯು ಬಹಳ ಕಟ್ಟುನಿಟ್ಟಾದ ರಚನೆಯನ್ನು ಹೊಂದಿದ್ದು, ಸಣ್ಣ ವರ್ಣದ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿದೆ ಮತ್ತು ಸಣ್ಣ ಸಂಖ್ಯೆಯ ದೊಡ್ಡ ಸ್ವತಂತ್ರ ಸೆಟ್ಗಳನ್ನು ಹೊಂದಿದೆ. ಮತ್ತೊಂದೆಡೆ, ರಾಮ್ಸೇ ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಪರಿಗಣಿಸಲಾದ ಗ್ರಾಫ್ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ ಆಗಿದೆ, ಇದು ದೊಡ್ಡ ವರ್ಣದ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿದೆ ಮತ್ತು ಯಾವುದೇ ಕ್ಷುಲ್ಲಕವಲ್ಲದ ಸ್ವತಂತ್ರ ಸೆಟ್ ಅನ್ನು ಹೊಂದಿಲ್ಲ. ಈ ಎರಡು ರೀತಿಯ ಸಮಸ್ಯೆಗಳನ್ನು ಸಂಯೋಜಿಸುವ ನೈಸರ್ಗಿಕ ವಿಧಾನವೆಂದರೆ ಆಂಡ್ರಾಸ್ಫೈ ಅವರು ಈ ಕೆಳಗಿನ ಪ್ರಶ್ನೆಯನ್ನು ಕೇಳುವುದುಃ ಸಮಸ್ಯೆ 1: ನಿರ್ದಿಷ್ಟ ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕಕ್ಕೆ, ಸ್ವತಂತ್ರ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿರದ ಮತ್ತು ಹೊಂದಿರದ-ವೆರ್ಟೆಕ್ಸ್ ಗ್ರಾಫ್ ಆಗಿರಲಿ. ಅಂತಹ ರೇಖಾಚಿತ್ರವು ಹೊಂದಬಹುದಾದ ಗರಿಷ್ಠ ಅಂಚುಗಳ ಸಂಖ್ಯೆ ಎಷ್ಟು? ಮೂಲಭೂತವಾಗಿ, ಈ ಪ್ರಶ್ನೆಯು ರಾಮ್ಸೇ ವ್ಯವಸ್ಥೆಯಲ್ಲಿ ಟುರಾನ್ ಸಮಸ್ಯೆಗೆ ಉತ್ತರವನ್ನು ಕೇಳುತ್ತದೆ; ಇದು ಟುರಾನ್ನ ಸಮಸ್ಯೆಯನ್ನು ಕಡಿಮೆ ಕ್ರಮಬದ್ಧವಾದ, ಹೆಚ್ಚು ಯಾದೃಚ್ಛಿಕವಾದ ರಚನೆಯೊಂದಿಗೆ ಗ್ರಾಫ್ಗಳ ಉಪವಿಭಾಗಕ್ಕೆ ಸೀಮಿತಗೊಳಿಸುತ್ತದೆ. ಈ ಕೆಳಗಿನ ಪ್ರಶ್ನೆಯು ಸಮಸ್ಯೆಗಳನ್ನು ವಿರುದ್ಧ ದಿಕ್ಕಿನಲ್ಲಿ ಸಂಯೋಜಿಸುತ್ತದೆಃ ಸಮಸ್ಯೆ 2: ಗ್ರಾಫ್ಗಳನ್ನು ಸ್ಥಿರವಾಗಿರಿಸೋಣ. ಶೃಂಗಗಳ ಮೇಲೆ ಅಂಚಿನ ಬಣ್ಣದ ರೇಖಾಚಿತ್ರವು th ಬಣ್ಣದಲ್ಲಿ an ಅನ್ನು ಹೊಂದಿರದ ಷರತ್ತಿನ ಅಡಿಯಲ್ಲಿ ಹೊಂದಿರಬಹುದಾದ ಗರಿಷ್ಠ ಅಂಚುಗಳ ಸಂಖ್ಯೆ ಎಷ್ಟು? ರಾಮ್ಸೇ-ಟುರಾನ್ ಸಿದ್ಧಾಂತದ ಬೆನ್ನೆಲುಬು ಮೇಲಿನ ಸಮಸ್ಯೆಗಳ ಸಾಮಾನ್ಯ ಸಾಮಾನ್ಯೀಕರಣವಾಗಿದೆ. ಸಮಸ್ಯೆ 3: ಗ್ರಾಫ್ಗಳು ಸ್ಥಿರವಾಗಿರಲಿ. (1) (2) ನಂ ಬಣ್ಣದಿಂದ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಉಪ ನಕ್ಷೆಯು ನಂ. ಗರಿಷ್ಠ ಎಷ್ಟು ಅಂಚುಗಳನ್ನು ಹೊಂದಬಹುದು? ನಾವು ಗರಿಷ್ಠವನ್ನು ಸೂಚಿಸುತ್ತೇವೆ. ರಾಮ್ಸೇ-ಟುರಾನ್-ರೀತಿಯ ಸಮಸ್ಯೆಗಳು 3ನೇ ಸಮಸ್ಯೆಯ ವಿಶೇಷ ಪ್ರಕರಣಗಳಾಗಿವೆ. ಈ ಸಮಸ್ಯೆಯ ಅನೇಕ ಪ್ರಕರಣಗಳು ಮುಕ್ತವಾಗಿ ಉಳಿದಿವೆ, ಆದರೆ ಹಲವಾರು ಆಸಕ್ತಿದಾಯಕ ಪ್ರಕರಣಗಳನ್ನು ನಿಖರವಾದ ಲಕ್ಷಣರಹಿತ ಪರಿಹಾರಗಳೊಂದಿಗೆ ಪರಿಹರಿಸಲಾಗಿದೆ. ಗಮನಾರ್ಹ ಫಲಿತಾಂಶಗಳು ಸ್ವತಂತ್ರ ಸಂಖ್ಯೆಯ ಮೇಲಿನ ನಿರ್ಬಂಧವನ್ನು ಅವಲಂಬಿಸಿ ಸಮಸ್ಯೆ 3 ಅನ್ನು ಮೂರು ವಿಭಿನ್ನ ಪ್ರಕರಣಗಳಾಗಿ ವಿಂಗಡಿಸಬಹುದು. ನಿರ್ಬಂಧ-ಮುಕ್ತ ಪ್ರಕರಣವಿದೆ, ಅಲ್ಲಿ, ಇದು ಕ್ಲಾಸಿಕ್ ರಾಮ್ಸೇ ಸಮಸ್ಯೆಗೆ ಇಳಿಯುತ್ತದೆ. "ಮಧ್ಯಂತರ" ಪ್ರಕರಣವಿದೆ, ಅಲ್ಲಿ ಸ್ಥಿರವಾಗಿದೆ. ಕೊನೆಯದಾಗಿ, ಅತ್ಯಂತ ಶ್ರೀಮಂತ ಸಮಸ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಪ್ರಕರಣವಿದೆ. ಈ ಶ್ರೇಣಿಯಲ್ಲಿನ ಅತ್ಯಂತ ಮೂಲಭೂತ ಕ್ಷುಲ್ಲಕವಲ್ಲದ ಸಮಸ್ಯೆಯೆಂದರೆ ಎರ್ಡೋಸ್ ಮತ್ತು ಸೋಸ್ ಅವರು 1969 ರಲ್ಲಿ ಈ ಪರಿಸ್ಥಿತಿಯಲ್ಲಿ ರಾಮ್ಸೇ-ಟುರಾನ್ ಸಂಖ್ಯೆಯ ಅಸಿಂಪ್ಟೋಟಿಕ್ ಮೌಲ್ಯವನ್ನು ಯಾವಾಗ ನಿರ್ಧರಿಸಿದರು ಎಂಬುದುಃ ಸಮ ಸಂಖ್ಯೆಯ ಶೃಂಗಗಳ ಮೇಲೆ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ನ ಪ್ರಕರಣವು ಹೆಚ್ಚು ಸವಾಲಿನದ್ದಾಗಿದೆ, ಮತ್ತು ಇದನ್ನು ಎರ್ಡೋಸ್, ಹಾಜ್ನಾಲ್, ಸೋಸ್ ಮತ್ತು ಸ್ಜೆಮೆರೆಡಿ ಅವರು 1983 ರಲ್ಲಿ ಪರಿಹರಿಸಿದರುಃ ಎರಡೂ ಸಂದರ್ಭಗಳಲ್ಲಿ, ಈ ಸಮಸ್ಯೆಯನ್ನು ಟುರಾನ್ನ ಪ್ರಮೇಯಕ್ಕೆ ಹೆಚ್ಚುವರಿ ಷರತ್ತನ್ನು ಸೇರಿಸುವಂತೆ ನೋಡಬಹುದು. ಎರಡೂ ಸಂದರ್ಭಗಳಲ್ಲಿ, ಲಕ್ಷಣರಹಿತವಾಗಿ, ಪರಿಣಾಮವು ನಾವು ಅಥವಾ ಬದಲಿಗೆ ಹೊರಗಿಟ್ಟಿರುವಂತೆಯೇ ಇರುತ್ತದೆ ಎಂದು ಕಾಣಬಹುದು. ಉಲ್ಲೇಖಗಳು ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ