هندسه ترکیبیاتی

*مسأله‌ی سیلوستر: تعدادی نقطه در صفحه داریم می‌شود همیشه خطی پیدا کرد که دقیقاً از ۲ تا نقطه بگذرد؟ (فرض کنید همه روی یک خط نیستند)

بله، اثبات: برهان خلف:

به ازای هر سه نقطه غیر هم خط فاصله‌ی یکی را از دو نقطه‌ی دیگر در نظر می‌گیریم و مینیمم این مجموعه را نقطه r و پاره‌خط pq می‌نامیم. نقطه‌ی دیگری که روی خط گذرنده از p و q است را s می‌نامیم. (چون می‌دانیم هر خطی طبق فرض خلف از دقیقاً دو نقطه نمی‌گذرد و اینجا p و q روی خط هستند پس از حداقل ۳ نقطه می‌گذرد.)

اگر پای عمود رسم شده از r روی pq بیفتد طبق نامساوی مثلث فاصله‌ی رأس نزدیک‌تر به s از rs کمتر از فاصله‌ی مینیمم است که این تناقض است.

اگر پای عمود رسم شده از r بیرون pq بیفتد طبق نامساوی مثلث فاصله‌ی رأس نزدیک‌تر به s از خط گذرنده از r و نقطه‌ی دورتر به s کمتر از فاصله‌ی مینیمم است که تناقض است.

*مسأله‌ی هاپکرافت: n نقطه و n خط داریم، حداکثر تعداد incidence ها چندتا است؟ (یعنی نقطه روی خط بیفتد و اگر یک نقطه روی تقاطع چند خط باشد چند بار شمرده می‌شود.)

کران ساده: خطوط را به m دسته‌ی n/m تایی تقسیم کنیم و در هر کدام می‌دانیم تعداد تقاطع‌ها حداکثر تعداد خط‌ها به توان ۲ است. از اینجا m طوری به دست می‌آید که O(n^3/2) وقوع (incidence) داریم. از روی جمع درجات=تعداد یالها*۲ می‌فهمیم چون هر وقوع معادل عبور یک خط از یک نقطه است که درجه آن نقطه را ۲ تا زیاد می‌کند.

کران بهتر:

O(n+x) که x تعداد تقاطع‌ها است. طبق crossing lemma (لم تقاطع)‌ تعداد یالهای O(n+n^2/3 x^1/3) است. با جایگذاری O(n^4/3) به دست می‌آید.

*مسأله‌ی اردوش: n نقطه داریم چند تا فاصله‌شان از هم دقیقاً ۱ است؟

دور هر نقطه دایره به شعاع ۱ می‌زنیم. همان اثبات مسأله‌ی هاپکرافت را می‌توانیم برای این مسأله به کار ببریم چون از خط بودن هیچ استفاده‌ای نکرده‌ایم.