در 1850، توماس پنینگتون کرکمن، یک ریاضیدان در زمانی که مسئولیت اصلی خود را به عنوان نائب در کلیسای انگلستان انجام نمی داد، «مشکل دختر دانش آموزی» خود را اینگونه توصیف کرد: «پانزده بانوی جوان در یک مدرسه به مدت هفت روز متوالی سه پشت سر هم از خانه بیرون می روند: لازم است ترتیبی داده شود. آنها هر روز، به طوری که هیچ دو نفر دو بار پشت سر هم راه نخواهند رفت.»
برای یک ریاضیدان مدرن، این نوع مسئله به بهترین وجه به صورت هایپرگراف تصور می شود - مجموعه ای از گره ها که در گروه های سه تایی یا بیشتر جمع آوری شده اند. 15 دختر دانش آموز گره هستند، و هر گروه از "سه کنار هم" را می توان به عنوان یک مثلث، با سه خط یا لبه، که سه گره را به هم متصل می کند، در نظر گرفت.
مشکل کرکمن اساساً این سؤال را مطرح می‌کند که آیا ترتیبی از این مثلث‌ها وجود دارد که همه دختران مدرسه‌ای را به یکدیگر متصل می‌کند، اما با این محدودیت اضافه شده که هیچ دو مثلثی دارای یک لبه نیستند. اشتراک لبه نشان می دهد که دو دختر مدرسه ای باید بیش از یک بار با هم راه بروند. این محدودیت به این معنی است که هر دختر به مدت یک هفته هر روز با دو دوست جدید راه می رود، به طوری که هر جفت ممکن دقیقاً یک بار دور هم جمع شوند.
این مشکل و موارد دیگر مانند آن تقریباً دو قرن از زمانی که کرکمن سؤال خود را مطرح کرد، ریاضیدانان را فریب داده است. در سال 1973، ریاضیدان افسانه‌ای پل اردوس، مشابهی را مطرح کرد. او پرسید که آیا می توان یک هایپرگراف با دو ویژگی ظاهراً ناسازگار ساخت؟ اول، هر جفت گره باید دقیقاً با یک مثلث به هم متصل شوند، مانند دختران مدرسه. این ویژگی نمودار را با مثلث ها متراکم می کند. شرط دوم مثلث ها را مجبور می کند که به روشی بسیار دقیق باز شوند. (به طور خاص، مستلزم آن است که برای هر گروه کوچکی از مثلث ها، حداقل سه گره بیشتر از مثلث ها وجود داشته باشد.) گفت: "شما این رفتار کمی متناقض را دارید که در آن یک جسم کلی متراکم دارید که قسمت های متراکمی ندارد." دیوید کانلون، ریاضیدان مؤسسه فناوری کالیفرنیا.
ژانویه امسال، در یک مدرک پیچیده 50 صفحه ای، چهار ریاضیدان ثابت کردند که همیشه می توان چنین هایپرگراف را ساخت تا زمانی که گره های کافی داشته باشید. گفت: "میزان فنی که [آنها] از سر گذراندند، فقط برای به دست آوردن این، شگفت انگیز بود." آلن لو، ریاضیدان دانشگاه بیرمنگام. کانلون موافقت کرد: "این یک کار واقعاً تأثیرگذار است."
تیم تحقیقاتی سیستمی را ساخت که با شروع یک فرآیند تصادفی برای انتخاب مثلث ها و مهندسی آن با دقت بسیار برای مطابقت با نیازهای Erdős، نیازهای شیطانی Erdős را برآورده کرد. کانلون گفت: «تعداد اصلاحات دشواری که در اثبات وجود دارد در واقع به نوعی حیرت‌انگیز است.
استراتژی آنها این بود که با دقت هایپرگراف را از مثلث های منفرد بسازند. به عنوان مثال، 15 دختر مدرسه ای ما را تصور کنید. بین هر جفت یک خط بکشید.
هدف در اینجا ردیابی مثلث ها در بالای این خطوط است به طوری که مثلث ها دو شرط را برآورده کنند: اول اینکه هیچ دو مثلثی دارای یک یال نیستند. (سیستم هایی که این نیاز را برآورده می کنند، سیستم های سه گانه Steiner نامیده می شوند.) و دوم، اطمینان حاصل کنید که هر زیرمجموعه کوچکی از مثلث ها از تعداد زیادی گره استفاده می کند.
روشی که محققان این کار را انجام دادند شاید با یک قیاس به بهترین وجه قابل درک باشد.
بگویید که به جای اینکه از لبه ها مثلث بسازید، خانه هایی را با آجر لگو می سازید. چند ساختمان اولی که می سازید فوق العاده هستند، با تقویت های ساختاری و تزئینات استادانه. پس از اتمام کار، آنها را کنار بگذارید. آنها به عنوان یک "جاذب" عمل خواهند کرد - نوعی انبار ساختار یافته.
اکنون شروع به ساختن ساختمان از آجرهای باقیمانده خود کنید و بدون برنامه ریزی زیاد ادامه دهید. وقتی تعداد لگوهای شما کم می شود، ممکن است خود را با آجرهای سرگردان یا خانه هایی بیابید که از نظر ساختاری نامناسب هستند. اما از آنجایی که ساختمان‌های جاذب بسیار زیاد و تقویت شده‌اند، می‌توانید برخی از آجرها را از اینجا و آنجا بچینید و از آنها استفاده کنید بدون اینکه به فاجعه‌ای دچار شوید.
در مورد سیستم سه گانه اشتاینر، شما در حال تلاش برای ایجاد مثلث هستید. جذب کننده شما، در این مورد، مجموعه ای از لبه ها است که با دقت انتخاب شده اند. اگر متوجه شدید که نمی توانید بقیه سیستم را به صورت مثلث مرتب کنید، می توانید از برخی از لبه هایی که به جذب کننده منتهی می شوند استفاده کنید. سپس، هنگامی که این کار را انجام دادید، خود جاذب را به مثلث تقسیم می کنید.
جذب همیشه کار نمی کند. اما ریاضیدانان با این فرآیند دستکاری کرده اند و راه های جدیدی برای دور زدن موانع پیدا کرده اند. به عنوان مثال، یک نوع قدرتمند به نام جذب تکراری، لبه ها را به دنباله ای تو در تو از مجموعه ها تقسیم می کند، به طوری که هر یک به عنوان یک جاذب برای بزرگ ترین بعدی عمل می کند.
کانلون می‌گوید: «در حدود یک دهه گذشته پیشرفت‌های گسترده‌ای صورت گرفته است. "این چیزی شبیه به یک شکل هنری است، اما آنها واقعاً آن را تا سطح هنر عالی در این مرحله رسانده اند."
مشکل Erdős حتی با جذب تکراری مشکل بود. گفت: "خیلی سریع مشخص شد که چرا این مشکل حل نشده است." مهتاب ساوهنی، یکی از چهار محققی که آن را حل کردند، همراه با اشوین سه، که همراه با Sawhney دانشجوی کارشناسی ارشد در موسسه فناوری ماساچوست است. مایکل سیمکین، عضو فوق دکتری در مرکز علوم ریاضی و برنامه های کاربردی در دانشگاه هاروارد. و متیو کوان، ریاضیدان مؤسسه علم و فناوری اتریش. کارهای فنی بسیار جالب و بسیار دشواری وجود داشت.»
به عنوان مثال، در سایر کاربردهای جذب تکراری، هنگامی که پوشش یک مجموعه را تمام کردید - چه با مثلث، برای سیستم های سه گانه اشتاینر، یا با ساختارهای دیگر برای مشکلات دیگر - می توانید آن را حل شده و فراموش کنید. با این حال، شرایط Erdős، چهار ریاضیدان را از انجام این کار باز داشت. یک خوشه مشکل ساز از مثلث ها می تواند به راحتی گره هایی از مجموعه جاذب های متعدد را درگیر کند.
Sawhney گفت: "مثلثی را که 500 قدم پیش انتخاب کردید، باید به نوعی به یاد داشته باشید که چگونه در مورد آن فکر کنید."
چیزی که این چهار نفر در نهایت متوجه شدند این بود که اگر مثلث های خود را با دقت انتخاب کنند، می توانند نیاز به پیگیری هر چیز کوچک را دور بزنند. Sawhney گفت: "آنچه بهتر است انجام دهید این است که به هر مجموعه کوچکی از 100 مثلث فکر کنید و تضمین کنید که مجموعه مثلث ها با احتمال صحیح انتخاب شده اند."
نویسندگان مقاله جدید خوشبین هستند که تکنیک آنها می تواند فراتر از این یک مشکل گسترش یابد. آنها دارند در حال حاضر استراتژی خود را اعمال کرده اند به یک مشکل در مورد مربع های لاتین، که مانند ساده سازی یک پازل سودوکو هستند.
کوان گفت: فراتر از آن، چندین سوال وجود دارد که ممکن است در نهایت به روش‌های جذب منجر شود. مشکلات زیادی در ترکیبات وجود دارد، به ویژه در تئوری طراحی، که در آن فرآیندهای تصادفی یک ابزار واقعا قدرتمند هستند. یکی از این مشکلات، حدس رایزر-بروالدی-اشتاین، نیز در مورد مربع های لاتین است و از دهه 1960 منتظر راه حل است.
اگرچه جذب ممکن است قبل از رفع این مشکل نیاز به توسعه بیشتری داشته باشد، اما از زمان شروع آن در 30 سال پیش راه زیادی را پیموده است. مایا استینمعاون مرکز مدل سازی ریاضی دانشگاه شیلی. "این چیزی است که واقعا عالی است برای دیدن، چگونه این روش ها تکامل می یابند."
