Lévy family of graphs
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಗಣಿತಶಾಸ್ತ್ರದ ಒಂದು ಶಾಖೆ, ಗ್ರಾಫ್ಗಳ ಲೆವಿ ಕುಟುಂಬವು Gn, n = 1,2,3, ಗ್ರಾಫ್ಗಳ ಒಂದು ಕುಟುಂಬವಾಗಿದೆ, ಇದು ಒಂದು ನಿರ್ದಿಷ್ಟ ರೀತಿಯ "ಸಾಂದ್ರತೆ" ಅಥವಾ "ಸಂಕೀರ್ಣತೆ" ಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ನೈಸರ್ಗಿಕವಾಗಿ ಕಂಡುಬರುವ ರೇಖಾಚಿತ್ರಗಳ ಅನೇಕ ಕುಟುಂಬಗಳು ಲೆವಿ ಕುಟುಂಬಗಳಾಗಿವೆ. ಅನೇಕ ಗಣಿತಶಾಸ್ತ್ರಜ್ಞರು ಈ ಸತ್ಯವನ್ನು ಗಮನಿಸಿದ್ದಾರೆ ಮತ್ತು ಇದಕ್ಕೆ ಸಿದ್ಧವಾದ ವಿವರಣೆ ಇಲ್ಲ ಎಂದು ಆಶ್ಚರ್ಯ ವ್ಯಕ್ತಪಡಿಸಿದ್ದಾರೆ. ಔಪಚಾರಿಕವಾಗಿ, Gn, n = 1,2,3,. ಗ್ರಾಫ್ಗಳ ಒಂದು ಕುಟುಂಬವು ಲೆವಿ ಕುಟುಂಬವಾಗಿದ್ದು, ಇಲ್ಲಿ D ಎಂಬುದು G ಯ ಗ್ರಾಫ್ ವ್ಯಾಸವಾಗಿದೆ ಮತ್ತು A (n) ಎಂಬುದು A ಯ ಎನ್-ಗ್ರಾಫ್ ನೆರೆಹೊರೆಯಾಗಿದೆ. ಗರಿಷ್ಠಗೊಳಿಸುವಿಕೆಯು ಜಿ ಯ ಉಪಗುಂಪುಗಳ ಮೇಲೆ ವ್ಯಾಪ್ತಿಯನ್ನು ಹೊಂದಿದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ, ಪದಗಳಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಒಬ್ಬರು ಜಿ ಯ ಅರ್ಧದಷ್ಟು ಗಾತ್ರದ ಉಪಗುಂಪನ್ನು ತೆಗೆದುಕೊಳ್ಳಬಹುದು, ಮತ್ತು ಅದನ್ನು ಗ್ರಾಫ್ ವ್ಯಾಸದಿಂದ ಮಾತ್ರ ಸ್ಫೋಟಿಸಬಹುದು, ಮತ್ತು ಬಹುತೇಕ ಎಲ್ಲಾ ಸೆಟ್ಗಳೊಂದಿಗೆ ಕೊನೆಗೊಳ್ಳುತ್ತದೆ. ಉದ್ದವಾದ "ಸ್ಟ್ರಿಂಗ್" (ಅಂದರೆ. "ಕಾಂಪ್ಯಾಕ್ಟ್" ಅಲ್ಲದ) ಕ್ರಮ n ರ ಸೈಕಲ್ ಗ್ರಾಫ್ನಂತಹ ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಗಳು ಸ್ಪಷ್ಟವಾಗಿ ಅಂತಹ ಗುಣಲಕ್ಷಣವನ್ನು ಹೊಂದಿಲ್ಲಃ ಒಂದು ಬಿಂದುವಿನ n/2 ನೆರೆಹೊರೆಯನ್ನು ಒಳಗೊಂಡಿರುವ ಉಪವಿಭಾಗವನ್ನು ಪರಿಗಣಿಸಬಹುದು (ಮಧ್ಯರಾತ್ರಿಯಿಂದ ಆರು ಗಂಟೆಯವರೆಗೆ, ಉದಾಹರಣೆಗೆ). ಗ್ರಾಫ್ ಸುಮಾರು n/2 ರ ಗ್ರಾಫ್ ವ್ಯಾಸವನ್ನು ಹೊಂದಿದೆ. ಆದ್ದರಿಂದ ಉಪವಿಭಾಗದ-ನೆರೆಹೊರೆಯು ಸುಮಾರು n/2 ಗಾತ್ರವನ್ನು ಮಾತ್ರ ಹೊಂದಿದೆ. ಒಂದು ಲೆವಿ ಕುಟುಂಬವು ಬಹುತೇಕ ಎಲ್ಲಾ ಸೆಟ್ಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಈ ನೆರೆಹೊರೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಲೆವಿ ಕುಟುಂಬವು ಬಹಳ ವಿಶೇಷ ರೀತಿಯ ಸಾಂದ್ರವಾದ ರಚನೆಯನ್ನು ಹೊಂದಿರಬೇಕು ಎಂಬುದು ಸ್ಪಷ್ಟವಾಗಿರಬೇಕು. n ಕ್ರಮದ ಹೈಪರ್ಕ್ಯೂಬ್ ಗ್ರಾಫ್ಗಳನ್ನು ಲೆವಿ ಕುಟುಂಬವೆಂದು ಕರೆಯಲಾಗುತ್ತದೆ. Sn ಎಂಬುದು n ಅಂಶಗಳ ಕ್ರಮಪಲ್ಲಟನೆಯ ಗುಂಪಿನ ಅಂಶಗಳಿರುವ ಬಿಂದುಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ ಆಗಿದ್ದರೆ, ಅಂಚುಗಳು ಸ್ಥಳಾಂತರದಿಂದ ಭಿನ್ನವಾಗಿರುವ ಬಿಂದುಗಳನ್ನು ಸೇರುತ್ತವೆ, ಆಗ Si, i = 1,2, ಸರಣಿಯು ಲೆವಿ ಕುಟುಂಬವಾಗಿದೆ. ಉಲ್ಲೇಖಗಳು ಬೊಲ್ಲೊಬಾಸ್ (ಸಂಪಾದಕ). ಸಂಭವನೀಯ ಸಂಯೋಜನೆ ಮತ್ತು ಅದರ ಅನ್ವಯಗಳು. ಅಮೆರಿಕನ್ ಮ್ಯಾಥಮೆಟಿಕಲ್ ಸೊಸೈಟಿ, 1991 (p63) ಗ್ರಾಫ್ ಕುಟುಂಬಗಳು