Blow-up lemma
1997ರಲ್ಲಿ ಜಾನೊಸ್ ಕೊಮ್ಲೋಸ್, ಗಾಬೊರ್ ಎನ್. ಸಾರ್ಕೋಜಿ ಮತ್ತು ಎಂಡ್ರೆ ಸ್ಜೆಮೆರೆಡಿ ಅವರು ಸಾಬೀತುಪಡಿಸಿದ ಬ್ಲೋ-ಅಪ್ ಲೆಮ್ಮಾವು, ತೀವ್ರ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ವಿಶೇಷವಾಗಿ ಕ್ರಮಬದ್ಧತೆಯ ವಿಧಾನದ ಸಂದರ್ಭದಲ್ಲಿ, ಒಂದು ಪ್ರಮುಖ ಫಲಿತಾಂಶವಾಗಿದೆ. ಸ್ಜೆಮೆರೆಡಿಯ ಕ್ರಮಬದ್ಧತೆಯ ಲೆಮ್ಮಾದ ಹೇಳಿಕೆಯಲ್ಲಿನ ನಿಯಮಿತ ಜೋಡಿಗಳು ಸೀಮಿತ ಮಟ್ಟದ ವ್ಯಾಪಿಸಿರುವ ಗ್ರಾಫ್ಗಳನ್ನು ಹುದುಗುವ ಸಂದರ್ಭದಲ್ಲಿ ಸಂಪೂರ್ಣ ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ಗಳಂತೆ ವರ್ತಿಸುತ್ತವೆ ಎಂದು ಅದು ಹೇಳುತ್ತದೆ. ವ್ಯಾಖ್ಯಾನಗಳು ಮತ್ತು ಹೇಳಿಕೆ ಬ್ಲೋ-ಅಪ್ ಲೆಮ್ಮಾವನ್ನು ಔಪಚಾರಿಕವಾಗಿ ಹೇಳಲು, ನಾವು ಮೊದಲು ಸೂಪರ್-ರೆಗ್ಯುಲರ್ ಜೋಡಿಯ ಕಲ್ಪನೆಯನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಬೇಕಾಗಿದೆ. ಸೂಪರ್-ರೆಗ್ಯುಲರ್ ಜೋಡಿಗಳು ಶೃಂಗದ ಗುಂಪಿನ ಒಂದು ಜೋಡಿ ಉಪಗುಂಪುಗಳನ್ನು-ಸೂಪರ್-ರೆಗ್ಯುಲರ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಪ್ರತಿಯೊಂದಕ್ಕೂ ಮತ್ತು ತೃಪ್ತಿಕರವಾಗಿದ್ದರೆ ಮತ್ತು ನಾವು ಹೊಂದಿದ್ದೇವೆ ಮತ್ತು ಇದಲ್ಲದೆ, ಎಲ್ಲರಿಗೂ ಮತ್ತು ಎಲ್ಲರಿಗೂ. ಇಲ್ಲಿ ಒಂದು ಅಂಚಿನೊಂದಿಗೆ ಮತ್ತು ಅಂತಹ ಜೋಡಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಬ್ಲೋ-ಅಪ್ ಲೆಮ್ಮಾದ ಹೇಳಿಕೆಯು ಕ್ರಮ ಮತ್ತು ಧನಾತ್ಮಕ ನಿಯತಾಂಕಗಳ ಗ್ರಾಫ್ ಅನ್ನು ನೀಡಿದರೆ, ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಹಿಡಿದಿಟ್ಟುಕೊಳ್ಳುವಂತಹ ಧನಾತ್ಮಕ ಅಂಶವಿದೆ. ಅನಿಯಂತ್ರಿತ ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕಗಳಾಗಿರಲಿ ಮತ್ತು ಅದರ ಶೃಂಗಗಳನ್ನು ಜೋಡಿಯಾಗಿ ಬೇರ್ಪಡಿಸುವ ಗಾತ್ರಗಳ ಸೆಟ್ಗಳೊಂದಿಗೆ ಬದಲಾಯಿಸೋಣ. ನಾವು ಒಂದೇ ಶೃಂಗದ ಗುಂಪಿನ ಮೇಲೆ ಎರಡು ಗ್ರಾಫ್ಗಳನ್ನು ನಿರ್ಮಿಸುತ್ತೇವೆ. ಅನುಗುಣವಾದ ಶೃಂಗದ ಸೆಟ್ಗಳ ನಡುವಿನ ಸಂಪೂರ್ಣ ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ನೊಂದಿಗೆ ಪ್ರತಿ ಅಂಚನ್ನು ಬದಲಿಸುವ ಮೂಲಕ ಮೊದಲ ಗ್ರಾಫ್ ಅನ್ನು ಪಡೆಯಲಾಗುತ್ತದೆ. ಪ್ರತಿ ಅಂಚನ್ನು ಮತ್ತು ನಡುವೆ-ಸೂಪರ್-ರೆಗ್ಯುಲರ್ ಜೋಡಿಯೊಂದಿಗೆ ಬದಲಾಯಿಸುವ ಮೂಲಕ ಸ್ಪಾರ್ಸರ್ ಗ್ರಾಫ್ ಜಿ ಅನ್ನು ನಿರ್ಮಿಸಲಾಗಿದೆ. ಗ್ರಾಫ್ ಅನ್ನು ಅದರೊಳಗೆ ಹುದುಗಿಸಬಹುದಾದರೆ ಅದನ್ನು ಈಗಾಗಲೇ ಜಿ. ಪ್ರೂಫ್ ಸ್ಕೆಚ್ನಲ್ಲಿ ಹುದುಗಿಸಬಹುದು. ಬ್ಲೋ-ಅಪ್ ಲೆಮ್ಮಾದ ಪುರಾವೆಯು ಅದರ ಶೃಂಗಗಳನ್ನು ಅನುಕ್ರಮವಾಗಿ ಹುದುಗಿಸಲು ಯಾದೃಚ್ಛಿಕ ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ (ಆರ್ಜಿಎ) ಅನ್ನು ಬಳಸುವುದನ್ನು ಆಧರಿಸಿದೆ. ಸೂಕ್ತವಾದ ನಿಯತಾಂಕಗಳ ಆಯ್ಕೆಗೆ ಅಲ್ಗಾರಿದಮ್ನ ವೈಫಲ್ಯದ ಪ್ರಮಾಣವು 1 ಕ್ಕಿಂತ ಕಡಿಮೆಯಿರುತ್ತದೆ (ಮತ್ತು ವಾಸ್ತವವಾಗಿ) ಎಂದು ಬಂಧಿಸುವ ಮೂಲಕ ವಾದವು ಮುಂದುವರಿಯುತ್ತದೆ. ಇದರರ್ಥ ಅಲ್ಗಾರಿದಮ್ ಯಶಸ್ವಿಯಾಗಲು ಶೂನ್ಯವಲ್ಲದ ಅವಕಾಶವಿದೆ, ಆದ್ದರಿಂದ ಎಂಬೆಡಿಂಗ್ ಅಸ್ತಿತ್ವದಲ್ಲಿರಬೇಕು. ಈ ರೀತಿಯಲ್ಲಿ ಎಲ್ಲಾ ಶೃಂಗಗಳನ್ನು ನೇರವಾಗಿ ಹುದುಗಿಸಲು ಪ್ರಯತ್ನಿಸುವುದು ಕೆಲಸ ಮಾಡುವುದಿಲ್ಲ ಏಕೆಂದರೆ ಸಣ್ಣ ಸಂಖ್ಯೆಯ ಶೃಂಗಗಳು ಮಾತ್ರ ಉಳಿದಿರುವಾಗ ಅಲ್ಗಾರಿದಮ್ ಅಂಟಿಕೊಳ್ಳಬಹುದು. ಬದಲಾಗಿ, ನಾವು ಬಫರ್ ಶೃಂಗಗಳು ಎಂದು ಕರೆಯಲ್ಪಡುವ ಶೃಂಗದ ಗುಂಪಿನ ಒಂದು ಸಣ್ಣ ಭಾಗವನ್ನು ಬದಿಗಿಟ್ಟು, ಉಳಿದ ಶೃಂಗಗಳನ್ನು ಹುದುಗಿಸಲು ಪ್ರಯತ್ನಿಸುತ್ತೇವೆ. ಬಫರ್ ಶೃಂಗಗಳು ಮತ್ತು ಉಳಿದ ಶೃಂಗಗಳ ನಡುವೆ ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಹಾಲ್ನ ವಿವಾಹ ಪ್ರಮೇಯವನ್ನು ಬಳಸಿಕೊಂಡು ಬಫರ್ ಶೃಂಗಗಳನ್ನು ತರುವಾಯ ಹುದುಗಿಸಲಾಗುತ್ತದೆ. ಹಿಂದಿನ ವಿಭಾಗಗಳಲ್ಲಿ ಪರಿಚಯಿಸಲಾದ ಎಲ್ಲಾ ಸಂಕೇತಗಳನ್ನು ನಾವು ಎರವಲು ಪಡೆಯುತ್ತೇವೆ. ಅವಕಾಶ ಮಾಡಿಕೊಡಿ. ಇದನ್ನು ಒಳಗೊಳ್ಳಬಹುದಾದ್ದರಿಂದ, ನಾವು ಎಲ್ಲರಿಗೂ ಬರೆಯಬಹುದು. ಒಂದು ಶೃಂಗಕ್ಕೆ, ಸೂಚಿಸೋಣ. ಫಾರ್, ಅನುಗುಣವಾದ ಶೃಂಗಗಳ ಸೆಟ್ಗಳ ನಡುವಿನ ಅಂಚುಗಳ ಸಾಂದ್ರತೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ನಾವು ನಿರ್ಮಿಸಲು ಬಯಸುವ ಎಂಬೆಡಿಂಗ್ ಆಗಿದೆ. ಅಲ್ಗಾರಿದಮ್ ಮುಕ್ತಾಯಗೊಳ್ಳುವ ಕೊನೆಯ ಸಮಯ ಇದು. ಅಲ್ಗಾರಿದಮ್ನ ಹಂತ 0 ರ ರೂಪರೇಖೆಃ ಪ್ರಾರಂಭವು ದುರಾಸೆಯಿಂದ ಶೃಂಗಗಳ ಗುಂಪಿನಿಂದ ಬಫರ್ ಶೃಂಗಗಳ ಗುಂಪನ್ನು ಕನಿಷ್ಠ ಒಂದಕ್ಕೊಂದು ಗರಿಷ್ಠ ಶೃಂಗಗಳ ಅಂತರವಾಗಿ ಆಯ್ಕೆ ಮಾಡಿ, ಪಟ್ಟಿಯಲ್ಲಿ ಉಳಿದ ಶೃಂಗಗಳನ್ನು (ಅವುಗಳಲ್ಲಿ) ಕ್ರಮಗೊಳಿಸಿ, ಮೊದಲಿನ ನೆರೆಹೊರೆಯವರನ್ನು ಇರಿಸಿ. ಪ್ರಸ್ತುತ ಆದ್ಯತೆಯ ಶೃಂಗಗಳ ಸಾಲನ್ನು ಘೋಷಿಸಿ, ಅದು ಆರಂಭದಲ್ಲಿ ಖಾಲಿಯಾಗಿದೆ. ಎಲ್ಲಾ "ಮುಕ್ತ ತಾಣಗಳ" ಗುಂಪನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಶೃಂಗಗಳಿಂದ ಸೂಚ್ಯಂಕಗೊಳಿಸಲಾದ ಸೆಟ್ಗಳ ಶ್ರೇಣಿಯನ್ನು ಘೋಷಿಸಿ, ಅಂದರೆ, ಶೃಂಗದಲ್ಲಿನ ಖಾಲಿ ಇರುವ ಶೃಂಗಗಳ ಗುಂಪನ್ನು ಈಗಾಗಲೇ ಒಳಭಾಗದಲ್ಲಿರುವ ನೆರೆಹೊರೆಯವರಿಂದ ಯಾವುದೇ ಸಾಮೀಪ್ಯದ ಷರತ್ತುಗಳನ್ನು ಉಲ್ಲಂಘಿಸದೆ ಮ್ಯಾಪ್ ಮಾಡಬಹುದು. ಇದನ್ನು ಆರಂಭಿಸಲಾಗಿದೆ. ಹಂತ 1: ಯಾದೃಚ್ಛಿಕ ದುರಾಶೆ ಎಂಬೆಡಿಂಗ್ ಉಳಿದ ಶೃಂಗಗಳ ಗುಂಪಿನಿಂದ ಒಂದು ಶೃಂಗವನ್ನು ಈ ಕೆಳಗಿನಂತೆ ಆಯ್ಕೆ ಮಾಡಿಃ ಆದ್ಯತೆಯ ಶೃಂಗಗಳ ಸಾಲು ಖಾಲಿಯಾಗಿಲ್ಲದಿದ್ದರೆ, ನಂತರ ಶೃಂಗವನ್ನು ಆಯ್ಕೆ ಮಾಡಿ ಇಲ್ಲದಿದ್ದರೆ, ಉಳಿದ ಶೃಂಗಗಳ ಪಟ್ಟಿಯಿಂದ ಒಂದು ಶೃಂಗವನ್ನು ಆಯ್ಕೆ ಮಾಡಿ "ಉತ್ತಮ" ಆಯ್ಕೆಗಳ ಗುಂಪಿನಿಂದ ಯಾದೃಚ್ಛಿಕವಾಗಿ ಶೃಂಗಕ್ಕಾಗಿ ಚಿತ್ರವನ್ನು ಆಯ್ಕೆ ಮಾಡಿ, ಅಲ್ಲಿ ಯಾವುದೇ ಹೊಸ ಫ್ರೀ-ಸೆಟ್ಗಳು ನಿರೀಕ್ಷಿತ ಮೌಲ್ಯಕ್ಕಿಂತ ಗಾತ್ರದಲ್ಲಿ ಹೆಚ್ಚು ಭಿನ್ನವಾಗಿರದಿದ್ದರೆ ಆಯ್ಕೆಯು ಉತ್ತಮವಾಗಿರುತ್ತದೆ. ಉಚಿತ ಸೆಟ್ಗಳನ್ನು ನವೀಕರಿಸಿ, ಮತ್ತು ಆದ್ಯತೆಯ ಶೃಂಗಗಳ ಗುಂಪಿನಲ್ಲಿನ ಕೊನೆಯ ನವೀಕರಣದಲ್ಲಿ ಅವುಗಳ ಗಾತ್ರಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ ಮುಕ್ತ ಸೆಟ್ಗಳು ತುಂಬಾ ಚಿಕ್ಕದಾಗಿರುವ ಶೃಂಗಗಳನ್ನು ಇರಿಸಿ, ಸರತಿಯು ಯಾವುದೇ ಸೆಟ್ಗಳ ಸಾಕಷ್ಟು ದೊಡ್ಡ ಭಾಗವನ್ನು ಹೊಂದಿದ್ದರೆ ಸ್ಥಗಿತಗೊಳಿಸಿ ಅಥವಾ ಎರಡೂ ಸೆಟ್ಗಳಲ್ಲಿ ಅಳವಡಿಸಲು ಬಫರ್ ಅಲ್ಲದ ಶೃಂಗಗಳು ಉಳಿದಿದ್ದರೆ, ಸಮಯವನ್ನು ನವೀಕರಿಸಿ ಮತ್ತು ಹಂತ 1 ಕ್ಕೆ ಹಿಂತಿರುಗಿ; ಇಲ್ಲದಿದ್ದರೆ ಹಂತ 2 ಕ್ಕೆ ಮುಂದುವರಿಯಿರಿ. ಹಂತ 2: ಉಳಿದ ಶೃಂಗಗಳಿಗೆ ಕೋನಿಗ್-ಹಾಲ್ ಹೊಂದಾಣಿಕೆ ಎಂಬೆಡ್ ಮಾಡಲು ಉಳಿದಿರುವ ಶೃಂಗಗಳ ಗುಂಪನ್ನು ಪರಿಗಣಿಸಿ, ಇದು ನಿಖರವಾಗಿ, ಮತ್ತು ಮುಕ್ತ ತಾಣಗಳ ಗುಂಪನ್ನು ಪರಿಗಣಿಸಿ. ಈ ಎರಡು ಸೆಟ್ಗಳ ನಡುವೆ ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ ಅನ್ನು ರಚಿಸಿ, ಪ್ರತಿಯೊಂದಕ್ಕೂ ಸೇರಿಕೊಳ್ಳಿ ಮತ್ತು ಈ ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ನಲ್ಲಿ ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಯನ್ನು ಕಂಡುಕೊಳ್ಳಿ. ಈ ಹೊಂದಾಣಿಕೆಯ ಪ್ರಕಾರ ಹುದುಗಿಸಲಾಗಿದೆ. ನಿಖರತೆಯ ಪುರಾವೆ ನಿಖರತೆಯ ಪುರಾವೆಯು ತಾಂತ್ರಿಕವಾಗಿದೆ ಮತ್ತು ಸಾಕಷ್ಟು ತೊಡಗಿಸಿಕೊಂಡಿದೆ, ಆದ್ದರಿಂದ ನಾವು ವಿವರಗಳನ್ನು ಬಿಟ್ಟುಬಿಡುತ್ತೇವೆ. ಪ್ರಮುಖ ವಾದವು ಈ ಕೆಳಗಿನಂತೆ ಮುಂದುವರಿಯುತ್ತದೆಃ ಹಂತ 1: ಹೆಚ್ಚಿನ ಶೃಂಗಗಳು ಉತ್ತಮವಾಗಿವೆ, ಮತ್ತು ಸಾಕಷ್ಟು ಶೃಂಗಗಳು ಮುಕ್ತವಾಗಿವೆ, ಏಕಕಾಲದಲ್ಲಿ ಅದರ ಮೇಲೆ ಪ್ರಚೋದನೆಯ ಮೂಲಕ ಸಾಬೀತುಪಡಿಸಿ, ಆ ಸಮಯದಲ್ಲಿ ಶೀರ್ಷವು ಹುದುಗಿದ್ದರೆ, ಆಯ್ಕೆಗಳ ಒಂದು ಸಣ್ಣ ಭಾಗ ಮಾತ್ರ ಕೆಟ್ಟದಾಗಿದೆ, ಎಲ್ಲಾ ಮುಕ್ತ ಸೆಟ್ಗಳು ಹುದುಗಿಸದ ಶೃಂಗಗಳಿಗೆ ಸಾಕಷ್ಟು ದೊಡ್ಡದಾಗಿರುತ್ತವೆ ಹಂತ 2: "ಮುಖ್ಯ ಲೆಮ್ಮಾ" ಪರಿಗಣಿಸಿ, ಮತ್ತು ಅದು ತುಂಬಾ ಚಿಕ್ಕದಲ್ಲ. ಮೊದಲ ಹಂತದಲ್ಲಿ ಯಾವುದೇ ಶೃಂಗಗಳನ್ನು ಹುದುಗಿಸದ ಘಟನೆಯನ್ನು ಪರಿಗಣಿಸಿ, ಆ ಸಮಯದಲ್ಲಿ ಮುಕ್ತ ಶೃಂಗಗಳ ಭಾಗವು ಚಿಕ್ಕದಾಗಿತ್ತು. ನಂತರ, ಸಂಭವಿಸುವ ಸಂಭವನೀಯತೆ ಕಡಿಮೆ ಎಂದು ನಾವು ಸಾಬೀತುಪಡಿಸುತ್ತೇವೆ. ಹಂತ 3: ಹಂತ 1 ಹೆಚ್ಚಿನ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ಯಶಸ್ವಿಯಾಗುತ್ತದೆ ಮೊದಲ ಹಂತವು ವಿಫಲಗೊಳ್ಳುವ ಏಕೈಕ ಮಾರ್ಗವೆಂದರೆ ಅದು ಸ್ಥಗಿತಗೊಂಡರೆ, ಏಕೆಂದರೆ ಮೊದಲ ಹಂತದ ವೇಳೆಗೆ ಉತ್ತಮ ಶೃಂಗಗಳ ಸಾಕಷ್ಟು ಆಯ್ಕೆ ಯಾವಾಗಲೂ ಇರುತ್ತದೆ ಎಂದು ನಮಗೆ ತಿಳಿದಿದೆ. ಸರತಿಯು ತುಂಬಾ ಉದ್ದವಾಗಿದ್ದಾಗ ಮಾತ್ರ ಪ್ರೋಗ್ರಾಂ ಸ್ಥಗಿತಗೊಳ್ಳುತ್ತದೆ. ನಂತರ ವಾದವು ವೈಫಲ್ಯದ ಎಲ್ಲಾ ವಿಧಾನಗಳ ಮೇಲೆ ಒಗ್ಗೂಡಿಸುವ ಮೂಲಕ ಮುಂದುವರಿಯುತ್ತದೆ, ಯಾವುದೇ ನಿರ್ದಿಷ್ಟ ಆಯ್ಕೆಗೆ, ಮತ್ತು ವಿಫಲವಾದ ಕ್ಯೂವಿನ ಉಪವಿಭಾಗವನ್ನು ಪ್ರತಿನಿಧಿಸುವುದರೊಂದಿಗೆ, ತ್ರಿವಳಿ "ಮುಖ್ಯ ಲೆಮ್ಮಾದ" ಷರತ್ತುಗಳನ್ನು ಪೂರೈಸುತ್ತದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಸಂಭವಿಸುವ ಕಡಿಮೆ ಸಂಭವನೀಯತೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಹಂತ 4: ಆರಂಭಿಕ ಹಂತದಲ್ಲಿ ಯಾವುದೇ ಸರತಿ ಇಲ್ಲ. ಬಫರ್ನಲ್ಲಿನ ಶೃಂಗಗಳ ನೆರೆಹೊರೆಯವರು ಮೊದಲು ಹುದುಗುವಂತಾಗಲು ಪಟ್ಟಿಯನ್ನು ಹೊಂದಿಸಲಾಗಿದೆ ಎಂಬುದನ್ನು ನೆನಪಿಸಿಕೊಳ್ಳಿ. ಈ ಎಲ್ಲಾ ಶೃಂಗಗಳು ಹುದುಗುವ ಸಮಯವನ್ನು ಆರಂಭಿಕ ಹಂತ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಆರಂಭಿಕ ಹಂತದಲ್ಲಿ ಸರತಿ ಸಾಲುಗಳಿಗೆ ಯಾವುದೇ ಶೃಂಗಗಳನ್ನು ಸೇರಿಸಲಾಗುವುದಿಲ್ಲ ಎಂದು ಇಂಡಕ್ಷನ್ ಮೂಲಕ ಸಾಬೀತುಪಡಿಸಿ. ಇದು ಬಫರ್ ಶೃಂಗಗಳ ಎಲ್ಲಾ ನೆರೆಹೊರೆಯವರು ಉಳಿದ ಶೃಂಗಗಳ ಮೊದಲು ಸೇರಿಸಲ್ಪಡುತ್ತಾರೆ. ಹಂತ 5: ಬಫರ್ ಶೃಂಗಗಳು ಸಾಕಷ್ಟು ಮುಕ್ತ ತಾಣಗಳನ್ನು ಹೊಂದಿವೆ ಮತ್ತು, ಯಾವುದೇ ಶೃಂಗಗಳು ಹುದುಗುವ ಮೊದಲು ಮುಕ್ತವಾಗಿದ್ದ ಊಹೆಯ ಮೇಲೆ ಷರತ್ತುಬದ್ಧವಾದ ಸಂಭವನೀಯತೆಯ ಮೇಲೆ ಸಾಕಷ್ಟು ದೊಡ್ಡ ಕೆಳ ಮಿತಿಯನ್ನು ನಾವು ಕಾಣಬಹುದು. ಹಂತ 6: ಹಂತ 2 ಹೆಚ್ಚಿನ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ಯಶಸ್ವಿಯಾಗುತ್ತದೆ ಹಾಲ್ನ ವಿವಾಹ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಹಾಲ್ನ ಸ್ಥಿತಿಯನ್ನು ಉಲ್ಲಂಘಿಸಿದರೆ ಮಾತ್ರ ಹಂತ 2 ವಿಫಲಗೊಳ್ಳುತ್ತದೆ. ಇದು ಸಂಭವಿಸಬೇಕಾದರೆ, ಕೆಲವು ಮತ್ತು ಅಂತಹವುಗಳು ಇರಬೇಕು. ಮುಕ್ತ ಸೆಟ್ಗಳ ದೊಡ್ಡತನದಿಂದ ತುಂಬಾ ಚಿಕ್ಕದಾಗಿರಲು ಸಾಧ್ಯವಿಲ್ಲ (ಹಂತ 1). ತುಂಬಾ ದೊಡ್ಡದಾಗಿದ್ದರೆ, ಹೆಚ್ಚಿನ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ, ಅಂತಹ ಸಂದರ್ಭದಲ್ಲಿ ವೈಫಲ್ಯದ ಸಂಭವನೀಯತೆಯು ಕಡಿಮೆಯಾಗಿರುತ್ತದೆ. ತುಂಬಾ ಚಿಕ್ಕದಾಗಲೀ ಅಥವಾ ತುಂಬಾ ದೊಡ್ಡದಾಗಲೀ ಇಲ್ಲದಿದ್ದರೆ, ಅದು ಬಳಕೆಯಾಗದ ಶೃಂಗಗಳ ದೊಡ್ಡ ಗುಂಪಾಗಿದೆ ಎಂದು ಗಮನಿಸಿದರೆ, ನಾವು ಮುಖ್ಯ ಲೆಮ್ಮಾವನ್ನು ಬಳಸಬಹುದು ಮತ್ತು ವೈಫಲ್ಯದ ಸಂಭವನೀಯತೆಯನ್ನು ಜೋಡಿಸಬಹುದು. ಅಪ್ಲಿಕೇಶನ್ಗಳು ದಟ್ಟವಾದ ಗ್ರಾಫ್ಗಳನ್ನು ಹುದುಗಿಸುವಲ್ಲಿ ಬ್ಲೋ-ಅಪ್ ಲೆಮ್ಮಾವು ಹಲವಾರು ಅಪ್ಲಿಕೇಶನ್ಗಳನ್ನು ಹೊಂದಿದೆ. ಪೋಸಾ-ಸೆಮೌರ್ ಕಾನ್ಸೆಕ್ಟರ್ 1962 ರಲ್ಲಿ, ಲಾಜೋಸ್ ಪೋಸಾ ಕನಿಷ್ಠ ಡಿಗ್ರಿ ಹೊಂದಿರುವ ಪ್ರತಿ-ವೆರ್ಟೆಕ್ಸ್ ಗ್ರಾಫ್ ಕನಿಷ್ಠ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರದ ವರ್ಗವನ್ನು ಹೊಂದಿರುತ್ತದೆ ಎಂದು ಊಹಿಸಿ, ಡಿರಾಕ್ನ ಪ್ರಮೇಯವನ್ನು ಸಾಮಾನ್ಯೀಕರಿಸಿದರು. 1974ರಲ್ಲಿ ಪೌಲ್ ಸೆಮೌರ್ ಈ ಊಹೆಯನ್ನು ಈ ಕೆಳಗಿನಂತೆ ವಿಸ್ತರಿಸಿದರುಃ ಕನಿಷ್ಠ ಡಿಗ್ರಿ ಹೊಂದಿರುವ ಶೃಂಗಗಳ ಮೇಲಿನ ಪ್ರತಿಯೊಂದು ಗ್ರಾಫ್ ಕನಿಷ್ಠ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರದ-th ಶಕ್ತಿಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. 1998 ರಲ್ಲಿ ಕೊಮ್ಲೋಸ್, ಸಾರ್ಕೋಜಿ ಮತ್ತು ಸ್ಜೆಮೆರೆಡಿ ಅವರು ಎಲ್ಲಾ ಸಾಕಷ್ಟು ದೊಡ್ಡ ಮೌಲ್ಯಗಳಿಗೆ (ಸ್ಥಿರಕ್ಕಾಗಿ) ಊಹೆಯನ್ನು ಸಾಬೀತುಪಡಿಸಲು ಬ್ಲೋ-ಅಪ್ ಲೆಮ್ಮಾವನ್ನು ಬಳಸಿದರು. 1995ರಲ್ಲಿ, ನೊಗಾ ಅಲೋನ್ ಮತ್ತು ರಾಫೆಲ್ ಯೂಸ್ಟರ್ ಪ್ರಸಿದ್ಧ ಹಾಜ್ನಾಲ್-ಸ್ಝೆಮೆರೆಡಿ ಪ್ರಮೇಯದ ಸಾಮಾನ್ಯೀಕರಣವನ್ನು ಅನಿಯಂತ್ರಿತ-ಅಂಶಗಳೆಂದು ಪರಿಗಣಿಸಿದರು (ಕೇವಲ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ಗಳ ಬದಲಿಗೆ), ಮತ್ತು ಈ ಕೆಳಗಿನ ಹೇಳಿಕೆಯನ್ನು ಸಾಬೀತುಪಡಿಸಿದರುಃ ಶೃಂಗಗಳೊಂದಿಗಿನ ಪ್ರತಿ ಸ್ಥಿರ ಗ್ರಾಫ್ಗೆ, n ಶೃಂಗಗಳೊಂದಿಗೆ ಮತ್ತು ಕನಿಷ್ಠ ಡಿಗ್ರಿ ಹೊಂದಿರುವ ಯಾವುದೇ ಗ್ರಾಫ್ G ಯು H ನ ಶೃಂಗಗಳ ಬೇರ್ಪಡಿಸುವ ಪ್ರತಿಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಫಲಿತಾಂಶವು ಕೇವಲ ಸ್ಥಿರ (ರೇಖೀಯ ಬದಲಿಗೆ) ದೋಷವನ್ನು ಮಾತ್ರ ಹೊಂದಿರುತ್ತದೆ ಎಂದು ಅವರು ಊಹಿಸಿದರುಃ ಪ್ರತಿ ಪೂರ್ಣಾಂಕಕ್ಕೂ ಒಂದು ಸ್ಥಿರಾಂಕವಿದೆ, ಅಂದರೆ ಶೃಂಗಗಳೊಂದಿಗಿನ ಪ್ರತಿ ಗ್ರಾಫ್ಗೆ, ಶೃಂಗಗಳೊಂದಿಗಿನ ಮತ್ತು ಕನಿಷ್ಠ ಡಿಗ್ರಿ ಹೊಂದಿರುವ ಯಾವುದೇ ಗ್ರಾಫ್ ಕನಿಷ್ಠ ಶೃಂಗಗಳ ಬೇರ್ಪಡಿಸುವ ಪ್ರತಿಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಈ ಊಹೆಯನ್ನು ಕೊಮ್ಲೋಸ್, ಸಾರ್ಕೋಜಿ ಮತ್ತು ಸ್ಜೆಮೆರೆಡಿ ಅವರು 2001 ರಲ್ಲಿ ಬ್ಲೋ-ಅಪ್ ಲೆಮ್ಮಾವನ್ನು ಬಳಸಿ ಸಾಬೀತುಪಡಿಸಿದರು. ಇತಿಹಾಸ ಮತ್ತು ರೂಪಾಂತರಗಳು 1997 ರಲ್ಲಿ ಕೊಮ್ಲೋಸ್, ಸಾರ್ಕೋಜಿ ಮತ್ತು ಸ್ಜೆಮೆರೆಡಿ ಅವರು ಮೊದಲು ಪ್ರಕಟಿಸಿದ ಬ್ಲೋ-ಅಪ್ ಲೆಮ್ಮಾವು, ವಿಸ್ತಾರವಾದ ಗ್ರಾಫ್ಗಳನ್ನು ಹುದುಗಿಸಲು ಕ್ರಮಬದ್ಧ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು ಅಸ್ತಿತ್ವದಲ್ಲಿರುವ ಪುರಾವೆ ತಂತ್ರಗಳ ಪರಿಷ್ಕರಣೆಯಾಗಿ ಹೊರಹೊಮ್ಮಿತು, ಮರಗಳನ್ನು ವ್ಯಾಪಿಸುವ ಬೊಲ್ಲೊಬಾಸ್ ಊಹೆಯ ಪುರಾವೆಯಂತೆ, ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರದ ಕೆ-ನೇ ಗ್ರಾಫ್ ಶಕ್ತಿಯನ್ನು ಹೊಂದಲು ಅಗತ್ಯವಾದ ಕನಿಷ್ಠ ಡಿಗ್ರಿ ಬಗ್ಗೆ ಪೋಸಾ-ಸೈಮೂರ್ ಊಹೆಯ ಮೇಲೆ ಕೆಲಸ ಮಾಡಿ ಮತ್ತು ಪರಿಪೂರ್ಣ ಎಚ್-ಅಂಶವನ್ನು ಹೊಂದಲು ಗ್ರಾಫ್ಗೆ ಅಗತ್ಯವಿರುವ ಕನಿಷ್ಠ ಡಿಗ್ರಿ ಕುರಿತು ಅಲೋನ್-ಯೂಸ್ಟರ್ ಊಹೆಯ ಪುರಾವೆ. ಈ ಎಲ್ಲಾ ಪ್ರಮೇಯಗಳ ಪುರಾವೆಗಳು ಬಹುಪಾಲು ಶೃಂಗಗಳನ್ನು ಹುದುಗಿಸಲು ಯಾದೃಚ್ಛಿಕ ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸುವುದರ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿವೆ, ಮತ್ತು ನಂತರ ಉಳಿದ ಶೃಂಗಗಳಿಗೆ ಹುದುಗುವಿಕೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕಾನಿಗ್-ಹಾಲ್ ರೀತಿಯ ವಾದವನ್ನು ಬಳಸುತ್ತವೆ. ಬ್ಲೋ-ಅಪ್ ಲೆಮ್ಮಾದ ಮೊದಲ ಪುರಾವೆಯೂ ಇದೇ ರೀತಿಯ ವಾದವನ್ನು ಬಳಸಿತು. ಆದಾಗ್ಯೂ, ನಂತರ 1997 ರಲ್ಲಿ, ಅದೇ ಲೇಖಕರು ಮತ್ತೊಂದು ಪ್ರಬಂಧವನ್ನು ಪ್ರಕಟಿಸಿದರು, ಅದು ಯಾದೃಚ್ಛಿಕ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನಿರ್ಣಾಯಕವಾಗಿಸಲು ಸುಧಾರಣೆಯನ್ನು ಕಂಡುಕೊಂಡಿತು. ಪೀಟರ್ ಕೀವಾಶ್ 2010 ರಲ್ಲಿ ಹೈಪರ್ಗ್ರಾಫ್ಗಳಿಗೆ ಬ್ಲೋ-ಅಪ್ ಲೆಮ್ಮಾದ ಸಾಮಾನ್ಯೀಕರಣವನ್ನು ಕಂಡುಕೊಂಡರು. ಸ್ಟೀಫನ್ ಗ್ಲಾಕ್ ಮತ್ತು ಫೆಲಿಕ್ಸ್ ಜೂಸ್ ಅವರು 2018 ರಲ್ಲಿ ಮಳೆಬಿಲ್ಲಿನ ಗ್ರಾಫ್ಗಳಿಗಾಗಿ ಬ್ಲೋ-ಅಪ್ ಲೆಮ್ಮಾದ ರೂಪಾಂತರವನ್ನು ಕಂಡುಹಿಡಿದರು. 2019ರಲ್ಲಿ, ಪೀಟರ್ ಅಲೆನ್, ಜೂಲಿಯಾ ಬಾಟ್ಚರ್, ಹೈಪ್ ಹಾನ್, ಯೋಶಿಹಾರು ಕೊಹಾಯಕಾವಾ ಮತ್ತು ಯೂರಿ ಪರ್ಸನ್, ಬೌಂಡೆಡ್ ಡಿಗ್ರಿ ಗ್ರಾಫ್ಗಳನ್ನು ಯಾದೃಚ್ಛಿಕ ಮತ್ತು ಸೂಡೋರಾಂಡಮ್ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಹುದುಗಿಸಲು ಬ್ಲೋ-ಅಪ್ ಲೆಮ್ಮಾದ ವಿರಳ ಸಾದೃಶ್ಯಗಳನ್ನು ಕಂಡುಕೊಂಡರು.