Quasirandom group
গণিতে, একটি কোয়াসিরান্ডম গ্রুপ এমন একটি গ্রুপ যা একটি বড় পণ্য-মুক্ত উপসেট ধারণ করে না। এই ধরনের গোষ্ঠীগুলি সুনির্দিষ্টভাবে একটি ছোট অ-তুচ্ছ অপরিবর্তনীয় উপস্থাপনা ছাড়া। এই গোষ্ঠীগুলির নামগুলি গ্রাফ তত্ত্বের সাথে তাদের সংযোগ থেকে উদ্ভূত হয়ঃ একটি কোয়াসিরান্ডম গোষ্ঠীর যে কোনও উপসেটের উপর দ্বিদলীয় কেলি গ্রাফগুলি সর্বদা দ্বিদলীয় কোয়াসিরান্ডম গ্রাফ হয়। অনুপ্রেরণা গোষ্ঠীগুলির উপসেটগুলি বিবেচনা করার সময় কোয়াসিরান্ডম গোষ্ঠীর ধারণাটি উদ্ভূত হয় যার জন্য উপসেটের কোনও দুটি উপাদানের উপসেটে কোনও পণ্য নেই; এই ধরনের উপসেটগুলিকে পণ্য-মুক্ত বলা হয়। লাস্লো বাবাই এবং ভেরা সোস একটি ধ্রুবকের অস্তিত্ব সম্পর্কে জিজ্ঞাসা করেছিলেন যার জন্য অর্ডার সহ প্রতিটি সীমাবদ্ধ গোষ্ঠীর কমপক্ষে আকার সহ একটি পণ্য-মুক্ত উপসেট থাকে। পূর্ণসংখ্যার সমষ্টি-মুক্ত সেট সম্পর্কে পল এরদোসের একটি সুপরিচিত ফলাফল প্রমাণ করতে ব্যবহার করা যেতে পারে যে আবেলিয়ান গোষ্ঠীর জন্য যথেষ্ট, তবে দেখা যাচ্ছে যে অ-আবেলিয়ান গোষ্ঠীর জন্য এই ধরনের ধ্রুবক বিদ্যমান নেই। অ-তুচ্ছ নিম্ন এবং উপরের সীমানা উভয়ই এখন অর্ডার সহ একটি গোষ্ঠীর বৃহত্তম পণ্য-মুক্ত উপসেটের আকারের জন্য পরিচিত। একটি নিম্ন সীমা প্রমাণ করা যেতে পারে পর্যাপ্ত সংখ্যক কোসেটগুলির একটি বৃহৎ উপসেট গ্রহণ করে, এবং যে কোনও মৌলিকের জন্য প্রজেক্টিভ বিশেষ রৈখিক গোষ্ঠী বিবেচনা করে একটি উপরের সীমা দেওয়া হয়। উপরের সীমা প্রমাণের প্রক্রিয়ায়, টিমোথি গাওয়ারস পণ্য-মুক্ত অবস্থাকে অন্তর্ভুক্ত করার জন্য একটি কোয়াসিরান্ডম গোষ্ঠীর ধারণাকে সংজ্ঞায়িত করেছিলেন এবং গ্রাফ তত্ত্বে কোয়াসিরান্ডমনেসের সাথে জড়িত সমতুল্য প্রমাণ করেছিলেন। গ্রাফ কোয়াসিরান্ডোমনেস আনুষ্ঠানিকভাবে, একটি একক গোষ্ঠী কোয়াসিরান্ডম কিনা তা নিয়ে কথা বলার কোনও মানে হয় না। কোয়াসিরান্ডোমনেসের কঠোর সংজ্ঞাটি গোষ্ঠীগুলির ক্রমের ক্ষেত্রে প্রযোজ্য হবে, তবে প্রথম দ্বিদলীয় গ্রাফ কোয়াসিরান্ডোমনেসকে অবশ্যই সংজ্ঞায়িত করতে হবে। গোষ্ঠীগুলির ক্রম বিবেচনা করার প্রেরণা গ্রাফনের সাথে এর সংযোগ থেকে উদ্ভূত হয়, যা একটি নির্দিষ্ট অর্থে গ্রাফের সীমা হিসাবে সংজ্ঞায়িত করা হয়। একটি বাস্তব সংখ্যা ঠিক করুন দ্বিদলীয় গ্রাফের একটি ক্রম (এখানে যতক্ষণ পর্যন্ত অসীমের দিকে থাকে ততক্ষণ পূর্ণসংখ্যা এড়িয়ে যাওয়ার অনুমতি দেওয়া হয়েছে) শীর্ষ, শীর্ষ অংশ এবং প্রান্তের সাথে যদি নিম্নলিখিত সমতুল্য শর্তগুলির মধ্যে কোনওটি থাকে তবে প্রান্তগুলি কোয়াসিরান্ডম হয়ঃ শীর্ষ অংশ সহ প্রতিটি দ্বিদলীয় গ্রাফের জন্য এবং এম্বেড করা এবং এম্বেড করা লেবেলযুক্ত অনুলিপিগুলির সংখ্যা এখানে, ফাংশনটিকে নির্ভর করার অনুমতি দেওয়া হয়। এই ধরনের গ্রাফগুলিকে কোয়াসিরান্ডম বলা হয় কারণ প্রতিটি শর্ত দাবি করে যে বিবেচনা করা হচ্ছে যে পরিমাণটি প্রায় যা কেউ আশা করবে যদি দ্বিদলীয় গ্রাফটি এরদোস-রেনি র্যান্ডম গ্রাফ মডেল অনুসারে তৈরি করা হয়; অর্থাৎ, সম্ভাবনার সাথে এবং স্বাধীনভাবে প্রতিটি সম্ভাব্য প্রান্তকে অন্তর্ভুক্ত করে তৈরি করা হয় যদিও কোয়াসিরান্ডোমনেস শুধুমাত্র গ্রাফের ক্রমের জন্য সংজ্ঞায়িত করা যেতে পারে, তবে-কোয়াসিরান্ডোমনেসের একটি ধারণা একটি নির্দিষ্ট গ্রাফের জন্য সংজ্ঞায়িত করা যেতে পারে গ্রাফ কোয়াসিরান্ডোমনেসের উপরের যে কোনও সংজ্ঞায় ত্রুটি সহনশীলতার অনুমতি দিয়ে। সুনির্দিষ্টভাবে বলতে গেলে, কোয়াসিরান্ডোমনেসের যে কোনও সমতুল্য সংজ্ঞা দেওয়া হলে, শব্দটি একটি ছোট ধ্রুবক দ্বারা প্রতিস্থাপিত হতে পারে এবং সেই নির্দিষ্ট পরিবর্তিত শর্তকে সন্তুষ্ট করে এমন যে কোনও গ্রাফকে-কোয়াসিরান্ডম বলা যেতে পারে। দেখা যাচ্ছে যে কোনও শর্তে-কোয়াসিরান্ডোমনেস কিছু পরম ধ্রুবকের জন্য অন্য কোনও শর্তে-কোয়াসিরান্ডোমনেসের সমতুল্য গ্রুপ কোয়াসিরান্ডোমনেস সংজ্ঞায়িত করার পরবর্তী ধাপ হল কেলি গ্রাফ। দ্বিপক্ষীয় কাইলি গ্রাফগুলি গ্রাফ-তাত্ত্বিক সেটিংয়ে কোয়াসিরান্ডোমনেসকে গ্রুপ-তাত্ত্বিক সেটিংয়ে অনুবাদ করার একটি উপায় দেয়। একটি সীমাবদ্ধ গোষ্ঠী এবং একটি উপসেট দেওয়া হলে, দ্বিদলীয় কাইলি গ্রাফ হল ভার্টেক্স সেট সহ দ্বিদলীয় গ্রাফ এবং প্রতিটি উপাদান দ্বারা লেবেলযুক্ত, যার প্রান্তগুলি শীর্ষগুলির মধ্যে থাকে যার অনুপাত সংজ্ঞার একটি উপাদান উপরে সংজ্ঞায়িত সরঞ্জামগুলির সাথে, এখন গ্রুপ কোয়াসিরান্ডোমনেসকে সংজ্ঞায়িত করা যেতে পারে। (আবার, পূর্ণসংখ্যা এড়িয়ে যাওয়ার অনুমতি দেওয়া হয়) সহ গোষ্ঠীগুলির একটি ক্রমকে কোয়াসিরান্ডম বলা হয় যদি প্রতিটি বাস্তব সংখ্যা এবং উপসেটগুলির পছন্দের জন্য, গ্রাফগুলির ক্রম কোয়াসিরান্ডম হয়। যদিও কোয়াসিরান্ডোমনেস শুধুমাত্র গোষ্ঠীগুলির ক্রমের জন্য সংজ্ঞায়িত করা যেতে পারে, নির্দিষ্ট গোষ্ঠীগুলির জন্য-কোয়াসিরান্ডোমনেসের ধারণাটি নির্দিষ্ট গ্রাফের জন্য-কোয়াসিরান্ডোমনেসের সংজ্ঞা ব্যবহার করে গোষ্ঠীগুলিতে প্রসারিত করা যেতে পারে। গুণাবলী যেমন গাওয়ারস দ্বারা প্রমাণিত হয়েছে, গ্রুপ কোয়াসিরান্ডোমনেস বেশ কয়েকটি বিভিন্ন অবস্থার সমতুল্য বলে প্রমাণিত হয়েছে। সুনির্দিষ্টভাবে বলতে গেলে, গোষ্ঠীগুলির একটি ক্রম দেওয়া হলে, নিম্নলিখিতগুলি সমতুল্যঃ কোয়াসিরান্ডম; অর্থাৎ, দ্বারা সংজ্ঞায়িত কেলি গ্রাফের সমস্ত ক্রম কোয়াসিরান্ডম। এর ক্ষুদ্রতম অ-তুচ্ছ উপস্থাপনার মাত্রা সীমাহীন। এর বৃহত্তম পণ্য-মুক্ত উপসেটের আকার হল এর ক্ষুদ্রতম অ-তুচ্ছ ভাগফলের আকার সীমাহীন। ছদ্মবেশী গোষ্ঠী থেকে উৎপন্ন কাইলি গ্রাফগুলির শক্তিশালী মিশ্রণ বৈশিষ্ট্য রয়েছে; অর্থাৎ, শূন্যের দিকে ঝোঁক থাকা এবং অনন্তের দিকে ঝোঁক থাকা কিছু লোকের জন্য এটি একটি দ্বিদলীয় গ্রাফ। (মনে রাখবেন যে একটি গ্রাফ শীর্ষযুক্ত একটি গ্রাফ, যার প্রতিটি ডিগ্রি সহ, যার সংলগ্ন ম্যাট্রিক্সের সর্বাধিক দ্বিতীয় বৃহত্তম আইগেনভ্যালু রয়েছে) প্রকৃতপক্ষে, এটি দেখানো যেতে পারে যে যে কোনও-কোয়াসিরান্ডম গ্রুপের জন্য, সমাধানের সংখ্যা সহ, এবং এলোমেলোভাবে নির্বাচিত হলে কেউ যা আশা করতে পারে তার প্রায় সমান; অর্থাৎ, প্রায় সমান এই ফলাফলটি এক্সপ্যান্ডার মিক্সিং লেম্মার সরাসরি প্রয়োগ থেকে অনুসরণ করা হয়। উদাহরণস্বরূপ, কোয়াসিরান্ডম গোষ্ঠীর বেশ কয়েকটি উল্লেখযোগ্য পরিবার রয়েছে। প্রতিটি ক্ষেত্রে, কোয়াসিরান্ডোমনেস বৈশিষ্ট্যগুলি তার ক্ষুদ্রতম অ-তুচ্ছ উপস্থাপনার মাত্রা পরীক্ষা করে সবচেয়ে সহজেই যাচাই করা হয়। মৌলিকের জন্য প্রজেক্টিভ বিশেষ রৈখিক গোষ্ঠীগুলি কোয়াসিরান্ডম গোষ্ঠীগুলির একটি ক্রম গঠন করে, যেহেতু ফ্রোবেনিয়াসের একটি ক্লাসিক ফলাফল বলে যে এর ক্ষুদ্রতম অ-তুচ্ছ উপস্থাপনার কমপক্ষে মাত্রা রয়েছে। বিকল্প গোষ্ঠীগুলি হল কোয়াসিরান্ডম, যেহেতু এর ক্ষুদ্রতম অ-তুচ্ছ উপস্থাপনার মাত্রা রয়েছে ক্রমবর্ধমান ক্রম সহ অ-চক্রাকার সহজ গোষ্ঠীগুলির যে কোনও ক্রম কোয়াসিরান্ডম, কারণ এর ক্ষুদ্রতম অ-তুচ্ছ উপস্থাপনার কমপক্ষে মাত্রা রয়েছে, যেখানে গোষ্ঠীর ক্রমটি কোথায়। তথ্যসূত্র গ্রাফ তত্ত্ব গোষ্ঠী তত্ত্ব