Radon's theorem
জ্যামিতিতে, 1921 সালে জোহান র্যাডন দ্বারা প্রকাশিত উত্তল সেটের উপর র্যাডনের উপপাদ্য বলে যেঃ Rd-তে d + 2 বিন্দুর যে কোনও সেটকে দুটি সেটে বিভক্ত করা যেতে পারে যার উত্তল হুলগুলি ছেদ করে। এই উত্তল হুলগুলির ছেদস্থলে একটি বিন্দুকে set.For উদাহরণের রেডন বিন্দু বলা হয়, d = 2-এর ক্ষেত্রে, ইউক্লিডীয় সমতলে চারটি বিন্দুর যে কোনও সেটকে দুটি উপায়ে ভাগ করা যেতে পারে। এটি একটি ট্রিপল এবং একটি সিঙ্গেলটন গঠন করতে পারে, যেখানে ট্রিপল (একটি ত্রিভুজ) এর উত্তল কাঠামোতে সিঙ্গেলটন থাকে; বিকল্পভাবে, এটি দুটি জোড়া বিন্দু গঠন করতে পারে যা দুটি ছেদকারী রেখা বিভাগের শেষ বিন্দু গঠন করে। প্রমাণ এবং নির্মাণ ডি-মাত্রিক স্থানে ডি + 2 বিন্দুর যে কোনও সেট বিবেচনা করুন। তারপরে a1,., ad + 2 গুণকের একটি সেট বিদ্যমান, যার সবগুলিই শূন্য নয়, রৈখিক সমীকরণের পদ্ধতিটি সমাধান করে কারণ সেখানে d + 2 অজানা (গুণক) রয়েছে তবে কেবল d + 1 সমীকরণ রয়েছে যা তাদের অবশ্যই সন্তুষ্ট করতে হবে (প্রতিটি বিন্দুর স্থানাঙ্কের জন্য একটি, একটি চূড়ান্ত সমীকরণের সাথে গুণকের যোগফল শূন্য হওয়া প্রয়োজন)। কিছু নির্দিষ্ট অ-শূন্য সমাধান a1,., ad + 2 ঠিক করুন। ধনাত্মক গুণক সহ পয়েন্টের সেট হতে দিন, এবং ঋণাত্মক বা শূন্য গুণক সহ পয়েন্টের সেট হতে দিন। তারপর পয়েন্টগুলির প্রয়োজনীয় বিভাজনকে দুটি উপসেটে ছেদকারী উত্তল হুলগুলির সাথে গঠন করুন। উত্তল হুলগুলি এবং অবশ্যই ছেদ করতে হবে, কারণ তাদের উভয়ই সেই বিন্দু ধারণ করে যেখানে সূত্রের বাম দিকটি এই বিন্দুটির উত্তল সংমিশ্রণ হিসাবে প্রকাশ করে এবং ডান দিকটি এটিকে বিন্দুর উত্তল সংমিশ্রণ হিসাবে প্রকাশ করে। অতএব, প্রমাণ সম্পূর্ণ করে উভয় উত্তল হুলের অন্তর্গত। এই প্রমাণ পদ্ধতিটি গুণকের সমীকরণের পদ্ধতি সমাধানের জন্য গাউসিয়ান নির্মূল বা অন্যান্য দক্ষ অ্যালগরিদম ব্যবহার করে মাত্রায় বহুপদী সময়ের মধ্যে একটি রেডন বিন্দুর দক্ষ নির্মাণের অনুমতি দেয়। টপোলজিক্যাল রেডন উপপাদ্য রেডনের উপপাদ্যের সমতুল্য সূত্রটি হ 'লঃ যদি f একটি (d + 1)-মাত্রিক সিম্প্লেক্স αd + 1 থেকে Rd পর্যন্ত কোনও অ্যাফিন ফাংশন হয়, তবে αd + 1 এর দুটি বিচ্ছিন্ন মুখ রয়েছে যার চিত্রগুলি α intersect.They এর অধীনে সমতুল্য কারণ একটি সিম্পলেক্সে যে কোনও অ্যাফিন ফাংশন তার শীর্ষগুলির চিত্র দ্বারা অনন্যভাবে নির্ধারিত হয়। আনুষ্ঠানিকভাবে, ধরা যাক f হল একটি অ্যাফিন ফাংশন Δd + 1 থেকে Rd পর্যন্ত। ধরা যাক Δd + 1-এর শীর্ষগুলি, এবং তাদের চিত্রগুলি f-এর নিচে থাকা উচিত। মূল সূত্র দ্বারা, দুটি বিচ্ছিন্ন উপসেটে বিভক্ত করা যেতে পারে, যেমন। (xi) i in I এবং (xj) j in J, ওভারল্যাপিং উত্তল হুল সহ। যেহেতু f হল অ্যাফিন, তাই I-তে (xi) i-এর উত্তল কাঠামো হল I-এর শীর্ষগুলি (vi) i দ্বারা বিস্তৃত মুখের চিত্র, এবং একইভাবে J-তে (xj) j-এর উত্তল কাঠামো হল j-এর শীর্ষগুলি (vj) j দ্বারা বিস্তৃত মুখের চিত্র। এই দুটি মুখ বিচ্ছিন্ন, এবং এফ-এর নিচে তাদের চিত্রগুলি ছেদ করে-যেমনটি নতুন সূত্র দাবি করেছে। টপোলজিক্যাল রেডন উপপাদ্য এই বিন্যাসকে সাধারণীকরণ করে। এটি f-কে যে কোনও অবিচ্ছিন্ন ফাংশন হতে দেয়-অগত্যা অধিভুক্ত নয়ঃ যদি f একটি (d + 1)-মাত্রিক সিম্প্লেক্স αd + 1 থেকে Rd পর্যন্ত কোনও অবিচ্ছিন্ন ফাংশন হয়, তবে αd + 1-এর দুটি বিচ্ছিন্ন মুখ রয়েছে যার চিত্রগুলি সাধারণত f intersect.More এর অধীনে থাকে, যদি K কোনও (d + 1)-মাত্রিক কম্প্যাক্ট উত্তল সেট হয় এবং φ হল K থেকে d-মাত্রিক স্থান পর্যন্ত কোনও অবিচ্ছিন্ন ফাংশন হয়, তবে একটি রৈখিক ফাংশন g বিদ্যমান থাকে যাতে কিছু বিন্দু যেখানে g তার সর্বোচ্চ মান অর্জন করে এবং অন্য কোনও বিন্দু যেখানে g তার ন্যূনতম মান অর্জন করে সেখানে f দ্বারা একই বিন্দুতে ম্যাপ করা হয়। যেখানে K একটি সিম্প্লেক্স, সেখানে g-এর সর্বোচ্চ এবং সর্বনিম্ন বিন্দু দ্বারা গঠিত দুটি সিম্প্লেক্স মুখ অবশ্যই দুটি বিচ্ছিন্ন মুখ হতে হবে যার চিত্রগুলির একটি অ-ফাঁকা ছেদ রয়েছে। এই একই সাধারণ বিবৃতি, যখন একটি সিম্প্লেক্সের পরিবর্তে একটি হাইপারস্ফিয়ারে প্রয়োগ করা হয়, তখন বোরসুক-উলাম উপপাদ্য দেয়, যে f-কে অবশ্যই গোলকের দুটি বিপরীত বিন্দুকে একই বিন্দুতে ম্যাপ করতে হবে। প্রমাণ টপোলজিক্যাল রেডনের উপপাদ্যটি মূলত বাজমোসি এবং বারানি দ্বারা নিম্নলিখিত উপায়ে প্রমাণিত হয়েছিলঃ Sd (d-মাত্রিক গোলক) থেকে αd + 1 পর্যন্ত একটি অবিচ্ছিন্ন মানচিত্র তৈরি করুন, যাতে গোলকের প্রতিটি বিন্দু x-এর জন্য, g (x) এবং g (-x) αd + 1-এর দুটি বিচ্ছিন্ন মুখের উপর থাকে। এই ফাংশনে বোরসুক-উলাম উপপাদ্য প্রয়োগ করুন, যা Sd থেকে Rd পর্যন্ত একটি অবিচ্ছিন্ন ফাংশন। উপপাদ্যটি বলে যে, এই ধরনের যে কোনও ফাংশনের জন্য, Sd-তে কিছু বিন্দু y বিদ্যমান, যেমন f (g (y)) = f (g (-y))। জি (ওয়াই) এবং জি (-ওয়াই) বিন্দুগুলি δd + 1-এর দুটি বিচ্ছিন্ন মুখের উপর রয়েছে এবং এগুলি আরডি-এর একই বিন্দুতে এফ দ্বারা ম্যাপ করা হয়েছে। এর থেকে বোঝা যায় যে এই দুটি বিচ্ছিন্ন মুখের চিত্রগুলি ছেদ করে। আরেকটি প্রমাণ দিয়েছেন লোভাস এবং শ্রিজভার। মাতৌসেক একটি তৃতীয় প্রমাণ দিয়েছেনঃ ধরা যাক K হল সিম্প্লেক্স Δd + 1, এবং K-এর নিজের সাথে মুছে ফেলা যোগসূত্র। এর জ্যামিতিক উপলব্ধি Sd + 1 গোলকের সমরূপ। অতএব, Z2-সূচকটি d + 1 এর সমান। টপোলজিক্যাল রেডন উপপাদ্যটি নিম্নলিখিত আরও সাধারণ উপপাদ্য থেকে অনুসরণ করা হয়েছে। যে কোনও সরল জটিল K-এর জন্য, যদি এর Z2-সূচকটি d-এর চেয়ে বড় হয়, তবে। |K।। থেকে Rd পর্যন্ত প্রতিটি অবিচ্ছিন্ন ম্যাপিংয়ের জন্য, K-এর দুটি বিচ্ছিন্ন মুখের চিত্রগুলি ছেদ করে। প্রয়োগ সমতলের যে কোনও চারটি বিন্দুর রেডন বিন্দু হল তাদের জ্যামিতিক মধ্যমা, যে বিন্দুটি অন্যান্য বিন্দুর দূরত্বের যোগফলকে সর্বনিম্ন করে। রেডনের উপপাদ্যটি উত্তল সেটগুলির ছেদগুলির উপর হেলির উপপাদ্যের একটি আদর্শ প্রমাণের একটি মূল পদক্ষেপ গঠন করে; এই প্রমাণটি রেডনের রেডনের উপপাদ্যের মূল আবিষ্কারের অনুপ্রেরণা ছিল। রেডনের উপপাদ্যটি রৈখিক পৃথকীকরণের ক্ষেত্রে ডি-মাত্রিক বিন্দুর ভিসি মাত্রা গণনা করতেও ব্যবহার করা যেতে পারে। ডি + 1 বিন্দুর সেট রয়েছে (উদাহরণস্বরূপ, একটি নিয়মিত সিম্প্লেক্সের পয়েন্ট) যাতে প্রতিটি দুটি অ-খালি উপসেটকে একটি হাইপারপ্লেন দ্বারা একে অপরের থেকে পৃথক করা যায়। যাইহোক, d + 2 বিন্দুর যে সেটই দেওয়া হোক না কেন, একটি রেডন বিভাজনের দুটি উপসেটকে রৈখিকভাবে পৃথক করা যায় না। অতএব, এই সিস্টেমের VC মাত্রা ঠিক d + 1। একটি র্যান্ডমাইজড অ্যালগরিদম যা বারবার ডি + 2 বিন্দুর সেটগুলিকে তাদের রেডন বিন্দু দ্বারা প্রতিস্থাপন করে, যে কোনও বিন্দু সেটের কেন্দ্রবিন্দুতে একটি আনুমানিক গণনা করতে ব্যবহার করা যেতে পারে, যা বিন্দুর সংখ্যা এবং মাত্রা উভয় ক্ষেত্রেই বহুপদী। সম্পর্কিত ধারণাগুলি জ্যামিতিক মধ্যমা। একটি এক-মাত্রিক স্থানে তিন বিন্দুর রেডন বিন্দু কেবল তাদের মধ্যমা। বিন্দুর একটি সেটের জ্যামিতিক মধ্যমা হল সেটের পয়েন্টগুলির দূরত্বের সমষ্টি হ্রাসকারী বিন্দু; এটি এক-মাত্রিক মধ্যমাটিকে সাধারণীকরণ করে এবং সুবিধার অবস্থান এবং শক্তিশালী পরিসংখ্যান উভয়ের দৃষ্টিকোণ থেকে অধ্যয়ন করা হয়েছে। সমতলে চারটি বিন্দুর সেটের জন্য, জ্যামিতিক মধ্যমা রেডন বিন্দুর সাথে মিলে যায়। টেভারবার্গের উপপাদ্য। আর সেটগুলিতে বিভাজনের জন্য একটি সাধারণীকরণ দ্বারা দেওয়া হয়েছিল এবং এটি এখন টেভারবার্গের উপপাদ্য হিসাবে পরিচিত। এতে বলা হয়েছে যে ইউক্লিডীয় ডি-স্পেসের যে কোনও বিন্দুর জন্য, r উপসেটগুলিতে একটি বিভাজন রয়েছে যার উত্তল হুলগুলি কমপক্ষে একটি সাধারণ বিন্দুতে ছেদ করে। ক্যারাথিওডোরির উপপাদ্য বলে যে কিছু বিন্দুর উত্তল কাঠামোর যে কোনও বিন্দু সর্বাধিক ডি + 1 বিন্দুর উপসেটের উত্তল কাঠামোর মধ্যে থাকে; অর্থাৎ, প্রদত্ত বিন্দুটি একটি রেডন বিভাজনের অংশ যেখানে এটি একটি এককটন। ক্যারাথিওডোরির উপপাদ্যের একটি প্রমাণ র্যাডনের উপপাদ্যের প্রমাণের মতো রৈখিক সমীকরণের পদ্ধতির সমাধানগুলি পরীক্ষা করার একটি কৌশল ব্যবহার করে, যতক্ষণ না সর্বাধিক d + 1 অবশিষ্ট থাকে। কনভেক্স জ্যামিতি। র্যাডনের উপপাদ্য সম্পর্কিত ধারণাগুলি উত্তল জ্যামিতির জন্যও বিবেচনা করা হয়েছে, সীমাবদ্ধ সেটগুলির পরিবারগুলির বৈশিষ্ট্য সহ যে পরিবারের যে কোনও দুটি সেটের ছেদ পরিবারে থাকে এবং খালি সেট এবং সমস্ত সেটের মিলন পরিবারের অন্তর্গত। এই আরও সাধারণ প্রসঙ্গে, একটি সেট S-এর উত্তল কাঠামো হল S ধারণকারী পরিবারের সদস্যদের ছেদ এবং একটি স্থানের রেডন সংখ্যা হল সবচেয়ে ছোট r যাতে যে কোনও r বিন্দুর দুটি উপসেট থাকে যার উত্তল কাঠামো ছেদ করে। একইভাবে, ইউক্লিডীয় স্থানে উত্তল সেটগুলির জন্য তাদের সংজ্ঞাগুলির সাথে সাদৃশ্য রেখে হেলি সংখ্যা এইচ এবং ক্যারাথিওডোরি সংখ্যা সি-কে সংজ্ঞায়িত করা যেতে পারে এবং এটি দেখানো যেতে পারে যে এই সংখ্যাগুলি এইচ <আর ≤ চ + 1-এর অসমতা পূরণ করে। গ্রাফের জন্য রেডনের উপপাদ্য। একটি নির্বিচারে অনির্দিষ্ট গ্রাফে, কেউ একটি উত্তল সেটকে শীর্ষগুলির একটি সেট হিসাবে সংজ্ঞায়িত করতে পারে যার মধ্যে সেটের এক জোড়া শীর্ষকে সংযুক্ত করার প্রতিটি প্ররোচিত পথ অন্তর্ভুক্ত থাকে। এই সংজ্ঞার সাহায্যে, গ্রাফের ω + 1 শীর্ষগুলির প্রতিটি সেটকে দুটি উপসেটে বিভক্ত করা যেতে পারে যার উত্তল হুলগুলি ছেদ করে এবং ω + 1 হল সর্বনিম্ন সংখ্যা যার জন্য এটি সম্ভব, যেখানে ω হল প্রদত্ত গ্রাফের চক্র সংখ্যা। প্ররোচিত পথের পরিবর্তে সংক্ষিপ্ততম পথ জড়িত সম্পর্কিত ফলাফলের জন্য এবং দেখুন। উল্লেখগুলি উল্লেখ করুন। । । যেমনটি উল্লেখ করা হয়েছে। । । । যেমনটি উল্লেখ করা হয়েছে। । । । । । । বিচ্ছিন্ন জ্যামিতিতে উপপাদ্য উত্তল জ্যামিতিতে উপপাদ্য কনভেক্স হলস জ্যামিতিক ট্রান্সভার্সাল তত্ত্ব