قضیه هیلز–جووت
در ریاضیات قضیهٔ هیلز-جووت یکی از نتایج اصلی نظریه رمزی می‌باشد، اسم این قضیه برگرفته از اسم دو شخص به نام‌های و R. I. Jewett می‌باشد. این دو نفر می‌خواستند نشان دهند که اشیاء با ابعاد بالا، باید ساختار ترکیبیاتی قانونمندی داشته باشند و ممکن نیست که خواص چنین اشیائی به‌طور کامل رندوم و تصادفی باشد.
یک توصیف نادقیق هندسی از قضیه این است که برای هر دو عدد صحیح مثبت مانند formula_1 و formula_2 عددی مانند formula_3 وجود دارد که، اگر خانه‌های یک شبکهٔ مکعبی formula_3 بعدی formula_5، با formula_2 رنگ، رنگ شوند، باید سطر، ستون یا قطری وجود داشته باشد که همهٔ خانه‌های آن یکرنگ هستند. به بیانی دیگر، برای نسخهٔ تعمیم یافته از بازی ایکس-او formula_1 تایی، عدد formula_3 وجود دارد که اگر این بازی در مکعب formula_3 بعدی formula_5 انجام شود، بازی هرگز مساوی نخواهد شد! مهم نیست که formula_1 چقدر بزرگ باشد یا این که چند بازیکن در بازی شرکت می‌کنند و کدام یک از در کدام نوبت بازی خواهد کرد! فقط کافی است که بازی در یک صفحه با بعد formula_3 مناسب انجام شود. با استفاده از ، شاید کسی فکر کند که اگر دو بازیکن یکی درمیان بازی کنند، آنگاه نفر اول برای formula_3های به اندازهٔ کافی بزرگ، استراتژی برد خواهد داشت، با این حال تا به الان الگوریتمی عملی برای اجرای این استراتژی شناخته نشده‌است!
برای توصیف دقیق تر، formula_14 را مجموعهٔ کلمات به طول formula_3 روی یک الفبای formula_1 حرفی تعریف می‌کنیم که این الفبا همان مجموعهٔ formula_17 می‌باشد، و با این تعریف تمام کلمات formula_3 حرفی این الفبا عضو formula_14 هستند! این مجموعه، ابرمکعبی که موضوع قضیه است را شکل می‌دهد .(در واقع اینطور تصور می‌کنیم که هر کلمه آدرس یک خانه از این ابر مکعب است) یک کلمهٔ متغیر مانندformula_20 روی formula_14 کلمه‌ای است که در جای حداقل یکی از حروف آن متغیر formula_22 قرار دارد. به‌طور مثال formula_23 کلمه‌ای با ۴ حرف است! کلمات formula_24 یک خط ترکیبیاتی را در فضای formula_14 تشکیل می‌دهند، خطوط ترکیبیاتی شامل سطرها، ستون‌ها و بعضی از اقطار ابرمکعب می‌باشند، قضیه هیلز جووت بیان می‌کند که برای اعداد داده شدهٔ formula_1 و formula_2، عدد مثبت وصحیح formula_3 وجود دارد که وابسته به formula_2 و formula_1 است و برای هر افراز formula_14 به formula_2 دسته، حداقل یک دسته وجود دارد که یک خط ترکیبیاتی به‌طور کامل عضو آن دسته است!
برای مثال قرار می‌دهیم: n=3, c=2,H=۳، ابر مکعب formula_14 به دست آمده در این حالت خاص، در واقع همان صفحهٔ بازی معروف ایکس-او است!
۱۱ ۱۲ ۱۳
۲۱ ۲۲ ۲۳
۳۱ ۳۲ ۳۳
به‌طور مثال کلمهٔ formula_34 را در نظر بگیرید، با قرار دادن ۱٬۲،۳ به جای متغیر formula_22 خط ۲۱ ۲۲ ۲۳ به دست می‌آید. یا برای مثال کلمهٔ متغیر formula_36 را در نظر بگیرید، به قرار دادن ۱٬۲،۳ به جای formula_22، خط ترکیبیاتی یا همان قطر ۱۱ ۲۲ ۳۳ به دست می‌آید.(توجه کنید که در بازی ایکس-او، اگر تمام قطر ۱۳ ۲۲ ۳۱ توسط یکی از بازیکنان علامت گذاری شود، آن بازیکن برنده می‌شود، اما این خط، یک خط ترکیبیاتی نیست. در این حالت خاص formula_38، قضیه هیلز–جووت برقرار نیست. در این حالت امکان‌پذیر است که خانه‌ها را به دو دسته افراز کنیم (به‌طور مثال {۱۱٬۲۲٬۲۳٬۳۱} و {۱۲٬۱۳٬۲۱٬۳۲٬۳۳}) که هیچکدام از دسته‌ها شامل یک خط ترکیبیاتی نباشند.(در واقع در این حالت بازی مساوی می‌شود!) از طرف دیگر اگر H را به عدد ۸ افزایش دهیم ،(دقت کنید که تعداد خانه‌های زمین بازی در این حالت برابر با ۳۸ = ۶۵۶۱ می‌شود!) و این زمین بازی را به دو دسته تقسیم کنیم (همان "ضربدر" و" دایره"های مشهور که در بازی استفاده می‌شود!)، یکی از دسته‌ها حتماً شامل یک خط ترکیبیاتی است .(یا به عبارتی بازی مساوی نمی‌شود!) برای اثبات پایین را نگاه کنید.
اکنون به اثبات قضیه هیلز–جووت در حالت خاص formula_39 که در بالا بحث شد می‌پردازیم. ایده این است که این حکم را به اثبات حالات ساده‌تر قضیه هیلز–جووت کاهش دهیم.(در این حالت خاص منظور formula_40 و formula_41 است.) حالت کلی قضیه هیلز–جووت را می‌توان با روشی مشابه با استفاده از استقرای ریاضی اثبات کرد.
هر عضو ابرمکعب formula_42 رشته‌ای از هشت عدد از ۱ تا ۳ است مثلاً ۱۳۲۱۱۳۲۱ یک عضو ابرمکعب است. ما فرض می‌کنیم که ابر مکعب کاملاً از "دایره" و "ضربدر" پر شده باشد. ما برای اثبات از برهان خلف استفاده می‌کنیم و فرض می‌کنیم که نه دسته دایره‌ها و نه دسته ضربدرها شامل خط ترکیبیاتی نیستند. اگر ما ۶ عضو اینچنین رشته‌ای را ثابت بگیریم و ۲ عضو اخر را متغیر فرض کنیم یک صفحه بازی ایکس-او عادی خواهیم داشت برای مثال ??۱۳۲۱۱۳ چنین صفحه‌ای را به ما می‌دهد. برای صفحه‌ای مانند ??abcdef، حالت‌های abcdef11 ,adcdef12, abcdef22 را در نظر می‌گیریم. هر یک از این حالت‌ها باید یا با دایره یا با ضربدر پر شوند پس طبق اصل لانه کبوتری ۲ تا از آن‌ها باید با علامت مشابه پر شوند. از آن جهت که هر یک از این حالت‌ها قسمتی از خطوط ترکیبیاتی ما هستند، عضو سوم باید با علامت مخالف پر شود (زیرا ما فرض کردیم که هیچ‌کدام از خطوط ترکیبیاتی، ۳ عضو پر شده با علامت مشابه را ندارد). به عبارت دیگر، برای هر یک از انتخاب‌های abcdef (که می‌توان آن را به عنوان عضو ابر مکعب ۶ بعدی در نظر گرفت) ۶ حالت می‌توان در نظر گرفت:
از این رو ما می‌توانیم ابر مکعب ۶ بعدی formula_43 را با توجه به حالت‌های بالا به ۶ دسته تقسیم بندی کنیم.(اگر یک عضو از چند دسته پیروی کند می‌توانیم یک حالت قرار دادی در نظر بگیریم مثلاً بالاترین دسته در دسته بندی بالا). حال هفت عضو ۱۱۱۱۱۱، ۱۱۱۱۱۲ ،۱۱۱۱۲۲، ۱۱۱۲۲۲، ۱۱۲۲۲۲، ۱۲۲۲۲۲ ،۲۲۲۲۲۲ را در formula_43 در نظر بگیرید. طبق قضیه لانه کبوتری ۲ تا از این عضوها باید در یک دسته قرار بگیرند. برای مثال فرض کنید ۱۱۱۱۱۲ و ۱۱۲۲۲۲ در یک دسته قرار بگیرند، پس ۱۱۱۱۱۲۱۱، ۱۱۱۱۱۲۲۲، ۱۱۲۲۲۲۱۱، ۱۱۲۲۲۲۲۲ دارای علامت ضربدر و ۱۱۱۱۱۲۳۳، ۱۱۲۲۲۲۳۳ دارای علامت دایره هستند. اما حال، حالت ۱۱۳۳۳۲۳۳، که باید یا با دایره یا با ضربدر پر شود را در نظر می‌گیریم اگر با ضربدر پر شود، پس خط ترکیبیاتی 11xxx2xx کاملاً با ضربدر پر می‌شود که با فرض ما در تضاد است. برعکس اگر با دایره پر شود خط ترکیبیاتی کاملاً با دایره پر شده‌است که دو باره با فرض ما در تضاد است. این وضعیت برای هر یک از دو عضو از هفت عضو بالا از formula_43 که در یک دسته مشابه قرار گیرند مشابه است. از آن جهت که ما برای همه دسته‌ها تضاد داریم، پس فرض اولیه ما غلط بوده، پس باید حداقل یک خط ترکیبیاتی وجود داشته باشد که کاملاً از دایره یا ضربدر تشکیل شده باشد.
بحث بالا به گونه‌ای یک کار بی‌فایده بود، در حقیقت این قضیه برای formula_46 نیز برقرار است. اگر کسی بحث بالا را برای مقادیر عمومی formula_1 و formula_2 گسترش دهد، formula_3 به سرعت رشد خواهد کرد، حتی زمانی که formula_50 است (که به ۲ بازیکن بازی ایکس او بر می‌گردد) formula_3ای که از روابط بالا محاسبه شود حتی سریع تر از تابع اکرمن formula_3 رشد خواهد کرد. اولین کران به دست آمده از formula_3 مربوط به است، که با استفاده از توابع اصلی بازگشتی به دست آمد، و همچنان، در حالت کلی، بهترین کران برای عدد هالس-جووت،formula_54 می‌باشد.
دقت کنید که استدلال بالا نتیجهٔ روبه رو را نیز می‌دهد :اگر فرض کنیم که formula_55 مجموعه تمام اعداد ۸ رقمی با ارقام ۱٬۲،۳ باشد،(برای مثال A شامل ۱۱۳۳۳۲۳۳ نیز می‌باشد) اگر مجموعهٔ formula_55 را با دو رنگ، رنگ کنیم، دنباله‌ای حسابی به طول ۳ وجود دارد که همهٔ اعضای آن یک رنگ هستند، چرا که تمام خطوط ترکیبیاتی که در اثبات قضیه هیلز–جووت ظاهر می‌شوند، دنبالهٔ حسابی نیز هستند. با حالت کلی تر این استدلال، می‌توان نشان داد که قضیه هیلز–جووت ، را تعمیم می‌دهد! در واقع، قضیهٔ هیلز-جووت ذاتاً قضیه‌ای قوی تر است!
همچنین قضیهٔ هیلز-جووت نسخهٔ قوی تری نیز در مبحث چگالی دارد که در مطرح می‌شود، در این نسخهٔ قوی تر شده، به جای رنگ کردن ابر مکعب با formula_2 رنگ، ابر مکعب formula_14 و زیر مجموعه‌ای از آن به اسم formula_55 با چگالی δ بین صفر و یک داده شده‌است، این قضیه می‌گوید که برای formula_3 به اندازهٔ کافی بزرگ، که وابسته به formula_1 وδ است، مجموعهٔ formula_55 باید شامل یک خط ترکیبیاتی باشد به طوری که کل اعضای این خط در formula_55 قرار دارند. شماره‌ای از مجلهٔ نیویورک تایمز که در تاریخ ۱۳ دسامبر ۲۰۰۹ منتشر شد از پروژه‌ای گزارش داد که توسط آقای ، استاد دانشگاه کمبریج و دارندهٔ مدال فیلدز، انجام شد. این پروژه شامل اثبات آسان تری از قضیه هیلز–جووت در صورت چگالی این قضیه بود. این مقاله با نام مستعار D.H.J. Polymath منتشر شد.(اینجا را ببینید: http://arxiv.org/abs/0910.3926)