Erdős–Szekeres theorem
ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ, ಎರ್ಡೋಸ್-ಸ್ಜೆಕೆರೆಸ್ ಪ್ರಮೇಯವು, r, s ಅನ್ನು ನೀಡಿದರೆ, ಕನಿಷ್ಠ (r−1) (s−1) + 1 ಉದ್ದವಿರುವ ವಿಭಿನ್ನ ನೈಜ ಸಂಖ್ಯೆಗಳ ಯಾವುದೇ ಅನುಕ್ರಮವು ಏಕತಾನತೆಯಿಂದ ಹೆಚ್ಚುತ್ತಿರುವ ಉದ್ದದ ಅನುಕ್ರಮವನ್ನು ಅಥವಾ ಏಕತಾನತೆಯಿಂದ ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಉದ್ದದ ಅನುಕ್ರಮವನ್ನು ಹೊಂದಿರುತ್ತದೆ ಎಂದು ಪ್ರತಿಪಾದಿಸುತ್ತದೆ. ಇದು ರಾಮ್ಸೇ ಅವರ ಪ್ರಮೇಯದ ನಿಖರವಾದ ಉಪಸಂಹಾರಗಳಲ್ಲಿ ಒಂದನ್ನು ಮಾಡುವ ಒಂದು ಅಂತಿಮ ಫಲಿತಾಂಶವಾಗಿದೆ. ವಿಭಿನ್ನ ನೈಜ ಸಂಖ್ಯೆಗಳ ಪ್ರತಿಯೊಂದು ಅನಂತ ಅನುಕ್ರಮವು ಏಕತಾನತೆಯಿಂದ ಹೆಚ್ಚುತ್ತಿರುವ ಅನಂತ ಅನುಕ್ರಮ ಅಥವಾ ಏಕತಾನತೆಯಿಂದ ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಅನಂತ ಅನುಕ್ರಮವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಸಾಬೀತುಪಡಿಸಲು ರಾಮ್ಸೆಯ ಪ್ರಮೇಯವು ಸುಲಭಗೊಳಿಸುತ್ತದೆಯಾದರೂ, ಪಾಲ್ ಎರ್ಡೋಸ್ ಮತ್ತು ಜಾರ್ಜ್ ಸ್ಜೆಕೆರೆಸ್ ಅವರು ಸಾಬೀತುಪಡಿಸಿದ ಫಲಿತಾಂಶವು ಮುಂದೆ ಹೋಗುತ್ತದೆ. ಉದಾಹರಣೆ r = 3 ಮತ್ತು s = 2 ಗೆ, ಮೂರು ಸಂಖ್ಯೆಗಳ ಯಾವುದೇ ಕ್ರಮಪಲ್ಲಟನೆಯು ಮೂರು ಉದ್ದದ ಹೆಚ್ಚುತ್ತಿರುವ ಅನುಕ್ರಮವನ್ನು ಅಥವಾ ಎರಡು ಉದ್ದದ ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಅನುಕ್ರಮವನ್ನು ಹೊಂದಿರುತ್ತದೆ ಎಂದು ಸೂತ್ರವು ನಮಗೆ ಹೇಳುತ್ತದೆ. ಸಂಖ್ಯೆಗಳ ಆರು ಕ್ರಮಪಲ್ಲಟನೆಗಳಲ್ಲಿ 1,2,3:1,2,3 ಎಲ್ಲಾ ಮೂರು ಸಂಖ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಹೆಚ್ಚುತ್ತಿರುವ ಅನುಕ್ರಮವನ್ನು ಹೊಂದಿದೆ 1,3,2 ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಅನುಕ್ರಮವನ್ನು ಹೊಂದಿದೆ 3,2 2,1,3 ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಅನುಕ್ರಮವನ್ನು ಹೊಂದಿದೆ 2 2,3,1 ಎರಡು ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಅನುಕ್ರಮಗಳನ್ನು ಹೊಂದಿದೆ, 2,1 ಮತ್ತು 3,1 3,1,2 ಎರಡು ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಅನುಕ್ರಮಗಳನ್ನು ಹೊಂದಿದೆ, 3,1 ಮತ್ತು 3,2 3,2,1 ಮೂರು ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಉದ್ದ-2 ಅನುಕ್ರಮಗಳನ್ನು ಹೊಂದಿದೆ, 3,2,3,1, ಮತ್ತು 2,1. ಪರ್ಯಾಯ ವ್ಯಾಖ್ಯಾನಗಳು ಜ್ಯಾಮಿತೀಯ ವ್ಯಾಖ್ಯಾನ ಯುಕ್ಲಿಡಿಯನ್ ಸಮತಲದಲ್ಲಿನ ಬಿಂದುಗಳ x-ನಿರ್ದೇಶಾಂಕಗಳಾಗಿ ಅನುಕ್ರಮದಲ್ಲಿ ಸಂಖ್ಯೆಗಳ ಸ್ಥಾನಗಳನ್ನು ಮತ್ತು y-ನಿರ್ದೇಶಾಂಕಗಳಾಗಿ ಸಂಖ್ಯೆಗಳನ್ನು ಅರ್ಥೈಸಿಕೊಳ್ಳಬಹುದು; ಇದಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ, ಸಮತಲದಲ್ಲಿ ಹೊಂದಿಸಲಾದ ಯಾವುದೇ ಬಿಂದುವಿಗೆ, ಅವುಗಳ x-ನಿರ್ದೇಶಾಂಕಗಳಿಂದ ಕ್ರಮಿಸಲಾದ ಬಿಂದುಗಳ y-ನಿರ್ದೇಶಾಂಕಗಳು, ಸಂಖ್ಯೆಗಳ ಅನುಕ್ರಮವನ್ನು ರೂಪಿಸುತ್ತವೆ (ಎರಡು ಬಿಂದುಗಳು ಸಮಾನ x-ನಿರ್ದೇಶಾಂಕಗಳನ್ನು ಹೊಂದಿಲ್ಲದಿದ್ದರೆ). ಅನುಕ್ರಮಗಳು ಮತ್ತು ಬಿಂದು ಸೆಟ್ಗಳ ನಡುವಿನ ಈ ಅನುವಾದದೊಂದಿಗೆ, ಎರ್ಡೋಸ್-ಸ್ಜೆಕೆರೆಸ್ ಪ್ರಮೇಯವನ್ನು ಕನಿಷ್ಠ rs − r − s + 2 ಬಿಂದುಗಳ ಯಾವುದೇ ಗುಂಪಿನಲ್ಲಿ ನಾವು r − 1 ಧನಾತ್ಮಕ-ಇಳಿಜಾರು ಅಂಚುಗಳು ಅಥವಾ s − 1 ಋಣಾತ್ಮಕ-ಇಳಿಜಾರು ಅಂಚುಗಳ ಬಹುಭುಜಾಕೃತಿಯ ಮಾರ್ಗವನ್ನು ಕಂಡುಕೊಳ್ಳಬಹುದು ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ (r = s ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಮೂಲಕ), ಕನಿಷ್ಠ n ಬಿಂದುಗಳ ಯಾವುದೇ ಗುಂಪಿನಲ್ಲಿ ನಾವು ಒಂದೇ-ಚಿಹ್ನೆಯ ಇಳಿಜಾರುಗಳೊಂದಿಗೆ ಕನಿಷ್ಠ ತುದಿಯ ಅಂಚುಗಳ ಬಹುಭುಜಾಕೃತಿಯ ಮಾರ್ಗವನ್ನು ಕಂಡುಕೊಳ್ಳಬಹುದು. ಉದಾಹರಣೆಗೆ, r = s = 5 ಅನ್ನು ತೆಗೆದುಕೊಂಡರೆ, ಕನಿಷ್ಠ 17 ಬಿಂದುಗಳ ಯಾವುದೇ ಗುಂಪಿನಲ್ಲಿ ನಾಲ್ಕು ಅಂಚಿನ ಮಾರ್ಗವಿರುತ್ತದೆ, ಇದರಲ್ಲಿ ಎಲ್ಲಾ ಇಳಿಜಾರುಗಳು ಒಂದೇ ಚಿಹ್ನೆಯನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಅಂತಹ ಮಾರ್ಗವಿಲ್ಲದ rs − r − s + 1 ಬಿಂದುಗಳ ಉದಾಹರಣೆ, ಈ ಬಂಧವು ಬಿಗಿಯಾಗಿದೆ ಎಂದು ತೋರಿಸುತ್ತದೆ, (r − 1) ನಿಂದ (s − 1) ಗ್ರಿಡ್ಗೆ ಸಣ್ಣ ತಿರುಗುವಿಕೆಯನ್ನು ಅನ್ವಯಿಸುವ ಮೂಲಕ ರಚಿಸಬಹುದು. ಕ್ರಮಪಲ್ಲಟನೆಯ ಮಾದರಿಯ ವ್ಯಾಖ್ಯಾನ ಎರ್ಡಾಸ್-ಸ್ಜೆಕೆರೆಸ್ ಪ್ರಮೇಯವನ್ನು ಕ್ರಮಪಲ್ಲಟನೆಯ ಮಾದರಿಗಳ ಭಾಷೆಯಲ್ಲಿಯೂ ಸಹ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು, ಕನಿಷ್ಠ rs + 1 ಉದ್ದದ ಪ್ರತಿಯೊಂದು ಕ್ರಮಪಲ್ಲಟನೆಯು 1,2,3,., r + 1 ಅಥವಾ s + 1, s,., 2,1 ಮಾದರಿಯನ್ನು ಹೊಂದಿರಬೇಕು ಎಂದು ಹೇಳುತ್ತದೆ. ಎರ್ಡೋಸ್-ಸ್ಜೆಕೆರೆಸ್ ಪ್ರಮೇಯವನ್ನು ಹಲವಾರು ವಿಭಿನ್ನ ರೀತಿಯಲ್ಲಿ ಸಾಬೀತುಪಡಿಸಬಹುದು; ಈ ಕೆಳಗಿನ ಎರಡು ಸೇರಿದಂತೆ ಎರ್ಡೋಸ್-ಸ್ಜೆಕೆರೆಸ್ ಪ್ರಮೇಯದ ಆರು ವಿಭಿನ್ನ ಪುರಾವೆಗಳನ್ನು ಸಮೀಕ್ಷಿಸುತ್ತದೆ. ಸ್ಟೀಲ್ ಸಮೀಕ್ಷೆ ಮಾಡಿದ ಇತರ ಪುರಾವೆಗಳಲ್ಲಿ ಎರ್ಡೋಸ್ ಮತ್ತು ಸ್ಜೆಕೆರೆಸ್ ಅವರ ಮೂಲ ಪುರಾವೆ ಮತ್ತು, ಮತ್ತು ಸೇರಿವೆ. ಪಾರಿವಾಳದ ರಂಧ್ರದ ತತ್ವವು (r−1) (s−1) + 1 ಉದ್ದದ ಅನುಕ್ರಮವನ್ನು ನೀಡಿದರೆ, ಪ್ರತಿ ಸಂಖ್ಯೆಯನ್ನು ಜೋಡಿ (ಎಐ, ಬಿಐ) ಯೊಂದಿಗೆ ಅನುಕ್ರಮವಾಗಿ ಲೇಬಲ್ ಮಾಡಿ, ಅಲ್ಲಿ ಎಐ ಎಂಬುದು ನಿ ಮತ್ತು ಬಿಯೊಂದಿಗೆ ಕೊನೆಗೊಳ್ಳುವ ಏಕತಾನತೆಯಿಂದ ಹೆಚ್ಚುತ್ತಿರುವ ದೀರ್ಘಾವಧಿಯ ಅನುಕ್ರಮವಾಗಿದೆ. ಅನುಕ್ರಮದಲ್ಲಿ ಪ್ರತಿ ಎರಡು ಸಂಖ್ಯೆಗಳನ್ನು ಬೇರೆ ಬೇರೆ ಜೋಡಿಯೊಂದಿಗೆ ಲೇಬಲ್ ಮಾಡಲಾಗಿದೆಃ ಇಫ್ ಮತ್ತು ನಂತರ, ಮತ್ತು ಮತ್ತೊಂದೆಡೆ ಇಫ್. ಆದರೆ (r−1) (s−1) ಸಂಭವನೀಯ ಲೇಬಲ್ಗಳು ಎಐ ಗರಿಷ್ಠ r−1 ಆಗಿದ್ದರೆ ಮತ್ತು ಬಿಐ ಗರಿಷ್ಠ s−1 ಆಗಿದ್ದರೆ ಮಾತ್ರ ಇರುತ್ತವೆ, ಆದ್ದರಿಂದ ಪಾರಿವಾಳದ ರಂಧ್ರದ ತತ್ವದ ಪ್ರಕಾರ ಐ ಅಥವಾ ಬಿ ಈ ವ್ಯಾಪ್ತಿಯ ಹೊರಗಿರುವ ಐ ಮೌಲ್ಯವು ಅಸ್ತಿತ್ವದಲ್ಲಿರಬೇಕು. ಎಐ ವ್ಯಾಪ್ತಿಯಿಂದ ಹೊರಗಿದ್ದರೆ, ಎನ್ಐ ಕನಿಷ್ಠ ಆರ್ ಉದ್ದದ ಹೆಚ್ಚುತ್ತಿರುವ ಅನುಕ್ರಮದ ಭಾಗವಾಗಿದೆ, ಮತ್ತು ಬಿ ವ್ಯಾಪ್ತಿಯಿಂದ ಹೊರಗಿದ್ದರೆ, ಎನ್ಐ ಕನಿಷ್ಠ ಎಸ್ ಉದ್ದದ ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಅನುಕ್ರಮದ ಭಾಗವಾಗಿದೆ. ಈ ಪುರಾವೆಯನ್ನು ಒಂದು ಪುಟದ ಕಾಗದಕ್ಕೆ ಸಲ್ಲುತ್ತದೆ ಮತ್ತು ಅದನ್ನು ಅವರು ಸಮೀಕ್ಷೆ ಮಾಡಿದ ಪುರಾವೆಗಳಲ್ಲಿ "ಅತ್ಯಂತ ನುಣುಪಾದ ಮತ್ತು ಅತ್ಯಂತ ವ್ಯವಸ್ಥಿತ" ಎಂದು ಕರೆಯುತ್ತಾರೆ. ಮತ್ತೊಂದು ಪುರಾವೆಯು ಭಾಗಶಃ ಕ್ರಮಗಳಲ್ಲಿ ಸರಪಳಿ ವಿಭಜನೆಗಳ ಮೇಲೆ ದಿಲ್ವರ್ತ್ನ ಪ್ರಮೇಯವನ್ನು ಅಥವಾ ಅದರ ಸರಳವಾದ ದ್ವಿಗುಣವನ್ನು (ಮಿರ್ಸ್ಕಿಯ ಪ್ರಮೇಯ) ಬಳಸುತ್ತದೆ. ಪ್ರಮೇಯವನ್ನು ಸಾಬೀತುಪಡಿಸಲು, ಅನುಕ್ರಮದ ಸದಸ್ಯರ ಮೇಲೆ ಭಾಗಶಃ ಕ್ರಮವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಿ, ಇದರಲ್ಲಿ x ≤ y ಸಂಖ್ಯೆಗಳಾಗಿದ್ದರೆ x ಭಾಗಶಃ ಕ್ರಮದಲ್ಲಿ y ಗಿಂತ ಕಡಿಮೆ ಅಥವಾ ಸಮನಾಗಿರುತ್ತದೆ ಮತ್ತು x ಅನುಕ್ರಮದಲ್ಲಿ y ಗಿಂತ ನಂತರದದಲ್ಲ. ಈ ಭಾಗಶಃ ಕ್ರಮದಲ್ಲಿ ಸರಪಳಿಯು ಏಕತಾನತೆಯಿಂದ ಹೆಚ್ಚುತ್ತಿರುವ ಅನುಕ್ರಮವಾಗಿದೆ, ಮತ್ತು ಆಂಟಿಚೈನ್ ಏಕತಾನತೆಯಿಂದ ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಅನುಕ್ರಮವಾಗಿದೆ. ಮಿರ್ಸ್ಕಿಯ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಉದ್ದದ ಸರಣಿ r ಇರುತ್ತದೆ, ಅಥವಾ ಅನುಕ್ರಮವನ್ನು ಗರಿಷ್ಠ r-1 ಆಂಟಿಕೈನ್ಗಳಾಗಿ ವಿಂಗಡಿಸಬಹುದು; ಆದರೆ ಆ ಸಂದರ್ಭದಲ್ಲಿ ಅತಿದೊಡ್ಡ ಆಂಟಿಕೈನ್ಗಳು ಕನಿಷ್ಠ ಉದ್ದದೊಂದಿಗೆ ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಅನುಕ್ರಮವನ್ನು ರೂಪಿಸಬೇಕು, ಪರ್ಯಾಯವಾಗಿ, ದಿಲ್ವರ್ತ್ನ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಉದ್ದ s ನ ಆಂಟಿಕೈನ್ ಇದೆ, ಅಥವಾ ಅನುಕ್ರಮವನ್ನು ಗರಿಷ್ಠ s-1 ಸರಪಳಿಗಳಾಗಿ ವಿಂಗಡಿಸಬಹುದು, ಅವುಗಳಲ್ಲಿ ಉದ್ದವು ಕನಿಷ್ಠ r ಅನ್ನು ಹೊಂದಿರಬೇಕು. ರಾಬಿನ್ಸನ್-ಷೆನ್ಸ್ಟೆಡ್ ಪತ್ರವ್ಯವಹಾರದ ಅನ್ವಯವು ರಾಬಿನ್ಸನ್-ಷೆನ್ಸ್ಟೆಡ್ ಪತ್ರವ್ಯವಹಾರದ ಪರಿಣಾಮವಾಗಿಯೂ ಫಲಿತಾಂಶವನ್ನು ಪಡೆಯಬಹುದು. ರಾಬಿನ್ಸನ್-ಷೆನ್ಸ್ಟೆಡ್ ಪತ್ರವ್ಯವಹಾರವು ಪ್ರತಿ ಅನುಕ್ರಮಕ್ಕೂ ಯಂಗ್ ಟ್ಯಾಬ್ಲೋ ಪಿ ಅನ್ನು ಸಂಯೋಜಿಸುತ್ತದೆ ಎಂಬುದನ್ನು ನೆನಪಿಸಿಕೊಳ್ಳಿ, ಅದರ ನಮೂದುಗಳು ಅನುಕ್ರಮದ ಮೌಲ್ಯಗಳಾಗಿವೆ. ಟ್ಯಾಬ್ಲೋ ಪಿ ಈ ಕೆಳಗಿನ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಹೊಂದಿದೆಃ ದೀರ್ಘಾವಧಿಯ ಹೆಚ್ಚುತ್ತಿರುವ ನಂತರದ ಉದ್ದವು ಪಿ ಯ ಮೊದಲ ಸಾಲಿನ ಉದ್ದಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ. ದೀರ್ಘಾವಧಿಯ ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ನಂತರದ ಉದ್ದವು ಪಿ ಯ ಮೊದಲ ಕಾಲಮ್ನ ಉದ್ದಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ. ಈಗ, (r−1) (s−1) + 1 ನಮೂದುಗಳನ್ನು (r−1) (s−1) ಗಾತ್ರದ ಚೌಕ ಪೆಟ್ಟಿಗೆಯಲ್ಲಿ ಹೊಂದಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ, ಇದರಿಂದಾಗಿ ಮೊದಲ ಸಾಲು ಕನಿಷ್ಠ r ಉದ್ದವಾಗಿರುತ್ತದೆ ಅಥವಾ ಕೊನೆಯ ಸಾಲು ಕನಿಷ್ಠ s ಉದ್ದವಾಗಿರುತ್ತದೆ.