لینک کوتاه مطلب : https://hsgar.com/?p=6543

تلنگر تا زمانی که گم شوید

با هر مثلثی از یک چند ضلعی محدب شروع کنید، و سپس به طور مکرر یک مورب تصادفی انتخاب کنید و آن را برگردانید، و دو مثلثی که در حاشیه آن قرار دارد را با دو مثلث مختلف جایگزین کنید. در نهایت، این چرخش‌های تصادفی باعث می‌شوند که مثلث شما تقریباً به همان اندازه احتمال هر یک از مثلث‌سازی‌های احتمالی چند ضلعی را داشته باشد. اما “در نهایت” چقدر طول می کشد؟ دانش‌آموز من دانیل فریشبرگ در پیش‌چاپ ما پاسخ جدیدی دارد: «اختلاط بهبود یافته برای پیاده‌روی چرخشی مثلثی چندضلعی محدب» (arXiv:2207.09972).

مثلث های یک (n)-گون و چرخش های بین آنها رئوس و لبه های یک چند توپ محدب بعدی ((n-3)) را تشکیل می دهند که انجمن وجهی; مثال بالا که تلنگرهای یک شش ضلعی را نشان می دهد، مربوط به یک پست قدیمی است. انتقال تمام تقارن های چهاربعدی وابسته به هم وجهی (که نشان دهنده مثلث های یک هفت ضلعی است) در یک نقشه مسطح دشوار است، اما در اینجا حداقل به صورت نمودار است:

چرخش نمودار یک هفت ضلعی

تعداد گام‌ها تا زمانی که یک پیاده‌روی تصادفی به نزدیکی آن همگرا شود توزیع پایدار آن نامیده می شود زمان اختلاط. بنابراین راه دیگری برای بیان نتایج در پیش چاپ این است که یک کران جدید در زمان اختلاط associahedra ارائه کنیم. مقاله ای از مک شاین و تتالی در سال 1997 نشان می‌دهد که این زمان اختلاط (O(n^5log n)) است، و ما توان را اندکی به (O(n^{4.75})) بهبود می‌دهیم. که خیلی به نظر نمی رسد، اما این اولین پیشرفت در ۲۵ سال گذشته است!

این بخشی از خط تحقیقاتی است که دانیل در مورد زمان های اختلاط دنبال کرده است، پهنای درخت، و گسترش فضاهای حالت بزرگ، از جمله گراف های هانوی و مجموعه های مستقل در نمودارهای با پهنای درخت محدود. مانند آن مقالات دیگر، از ارتباطات شناخته شده بین زمان اختلاط، پهنای درخت، گسترش، و جریان چند کالایی برای فرمول‌بندی مسئله به‌عنوان یکی از یافتن سیستمی از مسیرها بین هر جفت رئوس در هم‌وجهی به‌گونه‌ای که هر یال از هم‌وجهی فقط برای بخش کوچکی از این مسیرها استفاده شود. ساخت این مسیرها از تجزیه بازگشتی associahedra به محصولات associahedra کوچکتر استفاده می کند، که با بریدن یک مثلث مرکزی از هر چند ضلعی مثلثی و استفاده از associahedra برای توصیف مثلث بندی قطعات باقی مانده به دست می آید.

همین مقاله همچنین شامل کران ضعیف تری بر روی مثلث شبکه های مستطیلی نقاط است. چند ضلعی های محدب دارای a شماره کاتالان از مثلث‌ها، اما برای شبکه‌ها، نمی‌توانیم به طور دقیق بگوییم که چند مثلث وجود دارد. این عدد (N) هر چه باشد، نشان می‌دهیم که این فضاهای حالت دارای پهنای درخت (N^{1-o(1)} هستند)، با استفاده از انتخاب ثابتی از مورب‌ها برای تقسیم کردن شبکه به شبکه‌های کوچک‌تر، مثلث کردن هر کدام. شبکه کوچکتر به طور مستقل، و نشان می دهد که بسیاری از این مثلث های پارتیشن بندی شده وجود دارد و ساختار محصول آنها گسترش بالایی به آنها می دهد. اما این نتیجه هنوز تا حدودی رضایت بخش نیست زیرا همه مثلث ها را در نظر نمی گیرد و به دلیل اینکه قسمت (N^{o(1)}) کران در اندازه شبکه چند جمله ای نیست. آیا مثلث های شبکه ها زمان اختلاط چند جمله ای دارند؟

(بحث در مورد Mastodon)

لینک منبع

ارسال یک پاسخ

آدرس ایمیل شما منتشر نخواهد شد.